diff options
| -rw-r--r-- | challenge-018/duncan-c-white/README | 56 | ||||
| -rw-r--r-- | challenge-018/duncan-c-white/perl5/PQ.pm | 101 | ||||
| -rwxr-xr-x | challenge-018/duncan-c-white/perl5/ch-1.pl | 76 | ||||
| -rwxr-xr-x | challenge-018/duncan-c-white/perl5/ch-2.pl | 50 |
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"; +} |