imported my solutions to this week's challenge.. task 1: trivial, task 2: only did the naive recursive form cos I got bogged down..

3 files changed, 165 insertions, 31 deletions

diff --git a/challenge-096/duncan-c-white/README b/challenge-096/duncan-c-white/README
index b4f84102f4..332493400e 100644
--- a/challenge-096/duncan-c-white/README
+++ b/challenge-096/duncan-c-white/README
@@ -1,49 +1,58 @@
-Task 1: "Palindrome Number
+Task 1: "Reverse Words
 
-You are given a number $N.
-Write a script to figure out if the given number is Palindrome.
-Print 1 if true otherwise 0.
+You are given a string $S.
+
+Write a script to reverse the order of words in the given string. The
+string may contain leading/trailing spaces. The string may have more
+than one space between words in the string. Print the result without
+leading/trailing spaces and there should be only one space between words.
 
 Example 1:
 
-	Input: 1221
-	Output: 1
+	Input: $S = "The Weekly Challenge"
+	Output: "Challenge Weekly The"
 
 Example 2:
 
-	Input: -101
-	Output: 0, since -101 and 101- are not the same.
+	Input: $S = "    Perl and   Raku are  part of the same family  "
+	Output: "family same the of part are Raku and Perl"
+"
+
+My notes: looks straightforward.
 
-Example 3:
 
-	Input: 90
-	Output: 0
-"
+Task 2: "Edit Distance
 
-My notes: sounds trivial.  N == join(reverse(split(N)))
+You are given two strings $S1 and $S2.
 
+Write a script to find out the minimum operations required to convert
+$S1 into $S2. The operations can be insert, remove or replace a
+character. Please check out 
+https://en.wikipedia.org/wiki/Edit_distance
+for more information.
 
-Task 2: "Demo Stack
+Example 1:
+
+	Input: $S1 = "kitten"; $S2 = "sitting"
+	Output: 3
 
-Write a script to demonstrate Stack operations like below:
+	Operation 1: replace 'k' with 's'
+	Operation 2: replace 'e' with 'i'
+	Operation 3: insert 'g' at the end
 
-push($n) - add $n to the stack
-pop() - remove the top element
-top() - get the top element
-min() - return the minimum element
+Example 2:
 
-Example:
+	Input: $S1 = "sunday"; $S2 = "monday"
+	Output: 2
 
-my $stack = Stack->new;
-$stack->push(2);
-$stack->push(-1);
-$stack->push(0);
-$stack->pop;       # removes 0
-print $stack->top; # prints -1
-$stack->push(0);
-print $stack->min; # prints -1
+	Operation 1: replace 's' with 'm'
+	Operation 2: replace 'u' with 'o'
 "
 
-My notes: ok so by "script" we mean "Perl class".  Very easy to do,
-but I wonder what ch-2.pl does - contains the above example I guess.
-On second thought, let's inline the Stack module into ch-2.pl..
+My notes: reading the Wikipedia page, the naive recursive implementation
+sounds good enough to me, even though it's hideously inefficent.
+The various iterative versions sound clever, especially the one which
+only stores two rows, but I can't be bothered.
+
+(note that there are several CPAN modules which do this, but solving a
+Perl Challenge by "use Text::Levenshtein" seems like cheating).
diff --git a/challenge-096/duncan-c-white/perl/ch-1.pl b/challenge-096/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..0b8f9d2a58
--- /dev/null
+++ b/challenge-096/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,37 @@
+#!/usr/bin/perl
+#
+# Task 1: "Reverse Words
+# 
+# You are given a string $S.
+# 
+# Write a script to reverse the order of words in the given string. The
+# string may contain leading/trailing spaces. The string may have more
+# than one space between words in the string. Print the result without
+# leading/trailing spaces and there should be only one space between words.
+# 
+# Example 1:
+# 
+# 	Input: $S = "The Weekly Challenge"
+# 	Output: "Challenge Weekly The"
+# 
+# Example 2:
+# 
+# 	Input: $S = "    Perl and   Raku are  part of the same family  "
+# 	Output: "family same the of part are Raku and Perl"
+# "
+# 
+# My notes: looks straightforward.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Data::Dumper;
+
+die "Usage: reverse-words S\n" if @ARGV==0;
+my $s = join(' ', @ARGV);
+
+$s =~ s/^\s+//;
+$s =~ s/\s+$//;
+my @rw = reverse( split(/\s+/, $s ) );
+say join(' ', @rw);
diff --git a/challenge-096/duncan-c-white/perl/ch-2.pl b/challenge-096/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..90187b85cb
--- /dev/null
+++ b/challenge-096/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,88 @@
+#!/usr/bin/perl
+# 
+# Task 2: "Edit Distance
+# 
+# You are given two strings $S1 and $S2.
+# 
+# Write a script to find out the minimum operations required to convert
+# $S1 into $S2. The operations can be insert, remove or replace a
+# character. Please check out https://en.wikipedia.org/wiki/Edit_distance
+# for more information.
+# 
+# Example 1:
+# 
+# 	Input: $S1 = "kitten"; $S2 = "sitting"
+# 	Output: 3
+# 
+#	Operation 1: replace 'k' with 's'
+#	Operation 2: replace 'e' with 'i'
+#	Operation 3: insert 'g' at the end
+# 
+# Example 2:
+# 
+# 	Input: $S1 = "sunday"; $S2 = "monday"
+# 	Output: 2
+# 
+# 	Operation 1: replace 's' with 'm'
+# 	Operation 2: replace 'u' with 'o'
+# "
+# 
+# My notes: reading the Wikipedia page, the naive recursive implementation
+# sounds good enough to me, even though it's hideously inefficent.
+# The various iterative versions sound clever, especially the one which
+# only stores two rows, but I can't be bothered.
+#
+# (note that there are several CPAN modules which do this, but solving a
+# Perl Challenge by "use Text::Levenshtein" seems like cheating).
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+use Data::Dumper;
+use List::Util qw(min);
+
+my $debug=0;
+die "Usage: edit-distance [--debug] A B\n" unless
+	GetOptions( "debug" => \$debug ) && @ARGV==2;
+my( $a, $b ) = @ARGV;
+
+my $ed = lev($a, $b);
+say $ed;
+
+#
+# my $ed = lev($a, $b);
+#	Calculate and return the Levenshtein edit distance between $a and $b.
+#	Naive recursive implmentation, basically:
+#		len(a), if len(b)==0
+#		len(b), if len(a)==0
+#		lev(tail(a),tail(b), if a[0]==b[0]
+#		else 1 + min(
+#			lev(tail(a),b),
+#			lev(a,tail(b)),
+#			lev(tail(a),tail(b)) )
+#
+fun lev( $a, $b )
+{
+	return length($a) if length($b)==0;
+
+	return length($b) if length($a)==0;
+
+	# if a[0]==b[0]: lev(tail(a),tail(b)
+	if( substr($a,0,1) eq substr($b,0,1) )
+	{
+		return lev( substr($a,1), substr($b,1) );
+	}
+
+	# 1 + min(
+	#	lev(tail(a),b),
+	#	lev(a,tail(b)),
+	#	lev(tail(a),tail(b)) )
+	return 1 + min(
+		lev(substr($a,1), $b),
+		lev($a,substr($b,1)),
+		lev(substr($a,1), substr($b,1))
+	);
+}