added my (dcw803) solutions to challenge 18

4 files changed, 250 insertions, 33 deletions

diff --git a/challenge-018/duncan-c-white/README b/challenge-018/duncan-c-white/README
index 37c8c6c8c7..0220538063 100644
--- a/challenge-018/duncan-c-white/README
+++ b/challenge-018/duncan-c-white/README
@@ -1,43 +1,33 @@
-Challenge 1: "Create a script to demonstrate Ackermann function. The
-Ackermann function is defined as below, m and n are positive number:
-
-      A(m, n) = n + 1                  if m = 0
-      A(m, n) = A(m - 1, 1)            if m > 0 and n = 0
-      A(m, n) = A(m - 1, A(m, n - 1))  if m > 0 and n > 0
-
-eg. A(1, 2) = A(0, A(1, 1))
-         = A(0, A(0, A(1, 0)))
-         = A(0, A(0, A(0, 1)))
-         = A(0, A(0, 2))
-         = A(0, 3)
-         = 4
+Challenge 1: "Write a script that takes 2 or more strings as command
+line parameters and print the longest common substring. For example,
+the longest common substring of the strings "ABABC", "ABCA" 
+and "BCBA" is string "BC" of length 3.
 "
 
 My notes:
 
-Clearly described.  I seem to recall that the Ackermann function is
-tremendously inefficient to calculate recursively, but that memoization
-really helps.  So, before writing a line of code, I think "use Memoize"
-is going to help..
+Very clearly described.  No obvious clever way of solving this, but the
+basic method is simple.
 
 
-Challenge 2: "Create a script to parse URL and print the components of
-URL. According to the Wiki page https://en.wikipedia.org/wiki/URL, the URL
-syntax is as below:
+Challenge 2: "Write a script to implement Priority Queue. It is like
+regular queue except each element has a priority associated with it. In a
+priority queue, an element with high priority is served before an element
+with low priority. It should serve the following operations:
 
-    scheme:[//[userinfo@]host[:port]]path[?query][#fragment]
+1) is_empty: check whether the queue has no elements.
 
-eg.  jdbc://user:password@localhost:3306/pwc?profile=true#h1
+2) insert_with_priority: add an element to the queue with an associated
+   priority.
 
-      scheme:   jdbc
-      userinfo: user:password
-      host:     localhost
-      port:     3306
-      path:     /pwc
-      query:    profile=true
-      fragment: h1
+3) pull_highest_priority_element: remove the element from the queue that
+   has the highest priority, and return it. If two elements have the same
+   priority, then return element added first.
 
-My notes: sounds pretty trivial for regexes, if the lexical syntax of
-each component is defined clearly.  Ok, reading the above wiki page
-doesn't make it 100% clear, but let's hack it up, that's probably good
-enough for most cases.
+"
+
+My notes: At last, a nicely specified problem to implement a nice data
+type.  meat and drink to me!  I've split out the Priority Queue
+implementation into the module PQ.pm, minimally-OO in order to
+get free magic PQ printing via interpolation and the magic of
+stringification.
diff --git a/challenge-018/duncan-c-white/perl5/PQ.pm b/challenge-018/duncan-c-white/perl5/PQ.pm
new file mode 100644
index 0000000000..bd086ebb96
--- /dev/null
+++ b/challenge-018/duncan-c-white/perl5/PQ.pm
@@ -0,0 +1,101 @@
+package PQ;
+
+# 
+# Priority Queue module.
+# each element has a priority associated with it. an element with high
+# priority is served before an element with low priority.
+# Has the following operations:
+# 
+# 1) is_empty: check whether the queue has no elements.
+# 
+# 2) insert_with_priority: add an element to the queue with an associated
+#    priority.
+# 
+# 3) pull_highest_priority_element: remove the element from the queue that
+#    has the highest priority, and return it. If two elements have the same
+#    priority, then return element added first.
+# 
+# "
+# 
+# My notes: At last, a nicely specified problem to implement a nice data
+# type.  meat and drink to me!
+
+use strict;
+use warnings;
+use Function::Parameters;
+use Data::Dumper;
+
+# ok, a priority queue can be an array of pairs, each pair
+# is [priority, item]
+
+use overload '""' => \&as_string;
+
+#
+# my $pq = PQ->new();
+#	Create an empty priority Queue.
+#
+method new( $class: )
+{
+	return bless( [], 'PQ' );
+}
+
+
+#
+# my $isempty = $pq->isempty();
+#	Check whether or not the given Priority Queue is empty.
+#	Return boolean - true iff $pq is empty, else false
+#
+method isempty(  )
+{
+	return @$self == 0 ? 1 : 0;
+}
+
+
+#
+# $pq->enqueue( $priority, $item );
+#	Modify the Priority Queue $pq, adding the given $item with
+#	the given $priority.
+#
+method enqueue( $priority, $item )
+{
+	my $pair = [ $priority, $item ];
+	if( @$self == 0 )
+	{
+		@$self = $pair;
+	} else
+	{
+		# find insertion point, the largest pos $p 
+		# whose priority is less than or equal to $priority
+		my $p;
+		for( $p=0; $p<@$self && $self->[$p][0]<=$priority; $p++ )
+		{
+		}
+		splice( @$self, $p, 0, $pair );
+	}
+}
+
+
+#
+# my( $item, $priority ) = $pq->dequeue();
+#	Dequeue the item with the lowest priority from $pq.
+#
+method dequeue(  )
+{
+	die if @$self==0;
+	my $pair = shift @$self;
+	return @$pair;
+}
+
+
+#
+# my $str = $pq->as_string();
+#	Generate the printable form of the priority queue.
+#
+method as_string( $x, $y )
+{
+	my $result = join(', ', map { "$_->[0]: $_->[1]" } @$self );
+	return "[$result]";
+}
+
+
+1;
diff --git a/challenge-018/duncan-c-white/perl5/ch-1.pl b/challenge-018/duncan-c-white/perl5/ch-1.pl
new file mode 100755
index 0000000000..c8f54bb8f5
--- /dev/null
+++ b/challenge-018/duncan-c-white/perl5/ch-1.pl
@@ -0,0 +1,76 @@
+#!/usr/bin/perl
+#
+# Challenge 1: "Write a script that takes 2 or more strings as command
+# line parameters and print the longest common substring. For example,
+# the longest common substring of the strings "ABABC", "ABCA" 
+# and "BCBA" is string "BC" of length 3.
+# "
+# 
+# My notes:
+# 
+# Very clearly described.  No obvious clever way of solving this, but the
+# basic method is simple.
+
+use strict;
+use warnings;
+use Function::Parameters;
+use Data::Dumper;
+
+die "Usage: ch-1.pl STR1 STR2 [STR3...]N\n" unless @ARGV>1;
+
+#
+# my $is = substr_of_all( $s, @str );
+#	Calculate whether or not $s is a substr of every string in @str.
+#	Return true iff it is; false otherwise.
+#
+fun substr_of_all( $s, @str )
+{
+	foreach my $str (@str)
+	{
+		return 0 unless $str =~ /$s/i;
+	}
+	return 1;
+}
+
+
+#
+# my $longestsubstr = find_longest_substr( @str );
+#	Find and return the longest substring of an array of strings @str.
+#
+fun find_longest_substr( @str )
+{
+	# find the shortest string
+	my $shortest;
+	my $shortlen = length($str[0])+1;
+	foreach my $str (@str)
+	{
+		my $l = length($str);
+		if( $l < $shortlen )
+		{
+			$shortlen = $l;
+			$shortest = $str;
+		}
+	}
+	#print "found shortest string: $shortest\n";
+	return $shortest if substr_of_all( $shortest, @str );
+
+	# otherwise try, in order of length, each substring of $shortest
+	for( my $l=$shortlen-1; $l>0; $l-- )
+	{
+		#print "trying length $l substrings of $shortest\n";
+		for( my $pos=$shortlen-$l; $pos>=0; $pos-- )
+		{
+			my $sub = substr($shortest,$pos,$l);
+			#print " checking whether $sub is a substring of all\n";
+			my $is = substr_of_all( $sub, @str );
+			return $sub if $is;
+		}
+	}
+
+	return "";
+}
+
+
+my @str = @ARGV;
+my $longestsubstr = find_longest_substr( @str );
+print "longest sub string of strings is $longestsubstr\n";
diff --git a/challenge-018/duncan-c-white/perl5/ch-2.pl b/challenge-018/duncan-c-white/perl5/ch-2.pl
new file mode 100755
index 0000000000..2cdf49ed29
--- /dev/null
+++ b/challenge-018/duncan-c-white/perl5/ch-2.pl
@@ -0,0 +1,50 @@
+#!/usr/bin/perl
+
+# 
+# Challenge 2: "Write a script to implement Priority Queue. It is like
+# regular queue except each element has a priority associated with it. In a
+# priority queue, an element with high priority is served before an element
+# with low priority. It should serve the following operations:
+# 
+# 1) is_empty: check whether the queue has no elements.
+# 
+# 2) insert_with_priority: add an element to the queue with an associated
+#    priority.
+# 
+# 3) pull_highest_priority_element: remove the element from the queue that
+#    has the highest priority, and return it. If two elements have the same
+#    priority, then return element added first.
+# 
+# "
+# 
+# My notes: At last, a nicely specified problem to implement a nice data
+# type.  meat and drink to me!  I've split out the Priority Queue
+# implementation into the module PQ.pm, minimally-OO in order to
+# get free magic PQ printing via interpolation and the magic of
+# stringification.
+
+use strict;
+use warnings;
+use Function::Parameters;
+use Data::Dumper;
+
+use lib qw(.);	# I hate this!
+use PQ;
+
+my $pq = PQ->new();
+
+foreach my $arg (@ARGV)
+{
+	if( $arg =~ /^(\d+):(.+)$/ )
+	{
+		$pq->enqueue( $1, $2 );
+	}
+	print "pq: $pq\n";
+}
+
+while( ! $pq->isempty() )
+{
+	my( $item, $priority ) = $pq->dequeue();
+	print "item $item, priority $priority\n";
+	print "pq: $pq\n";
+}