Merge pull request #3597 from dcw803/master

imported my solutions to ch#100, and also did a lot more work on ch#99s..

4 files changed, 236 insertions, 265 deletions

diff --git a/challenge-100/duncan-c-white/README b/challenge-100/duncan-c-white/README
index 1b476ca4de..75645a7654 100644
--- a/challenge-100/duncan-c-white/README
+++ b/challenge-100/duncan-c-white/README
@@ -1,93 +1,73 @@
-Task 1: "Pattern Match
+Task 1: "Fun Time
 
-You are given a string $S and a pattern $P.
+You are given a time (12 hour / 24 hour).
 
-Write a script to check if given pattern validate the entire string. Print
-1 if pass otherwise 0.
+Write a script to convert the given time from 12 hour format to 24 hour
+format and vice versa.
 
-The patterns can also have the following characters:
-? - Match any single character.
-* - Match any sequence of characters.
+Ideally we expect a one-liner.
 
 Example 1:
-	Input: $S = "abcde" $P = "a*e"
-	Output: 1
+	Input: 05:15 pm or 05:15pm
+	Output: 17:15
 
 Example 2:
-	Input: $S = "abcde" $P = "a*d"
-	Output: 0
+	Input: 19:15
+	Output: 07:15 pm or 07:15pm
+"
 
-Example 3:
-	Input: $S = "abcde" $P = "?b*d"
-	Output: 0
+My notes: very simple, I like one liners.  In ch-1.sh, you'll see 2 slightly
+different versions, both with decent error checking.
 
-Example 4:
-	Input: $S = "abcde" $P = "a*c?e"
-	Output: 1
-"
 
-My notes: oh, cool, simpler than regexes, but nice.  Two basic ways of
-doing this: 1). translate it into a regex and use Perl's regex matching,
-2). figure out a from-scratch mechanism to solve this problem.
+Task 2: "Triangle Sum
 
-Initially, I did (1) in a few minutes, worked fine.  See ch-1.pl as usual.
+You are given a triangle array.
 
-After doing task 2, I came back to task 1, and starting to think how to do
-(2) - doing it from scratch, and I decided it should be able to extract the
-text matching each wildcard ('?' and '*') as well.  See ch-1a.pl (and API.pm
-and PosExpr.pm modules) for an incomplete (and much much bigger) attempt:
+Write a script to find the minimum path sum from top to bottom.
 
-I defined a set of simple Abstract Pattern Instructions, in API.pm.
-For example, a single API might be written as "M'hello'->l", which means:
-"Fail unless you can match the literal string "hello" at the End of $s,
-assuming you can: store the position at which the trailing "hello" started
-in $s into a variable called l".  Another API might be "T l>2", meaning
-"only succeed if the value of l is > 2".  Captures are handled by APIs like
-"C0 1 l-1", meaning "capture into matchedtext[0] the part of $s from char
-pos 1 to char pos l-1".
+When you are on index i on the current row then you may move to either
+index i or index i + 1 on the next row.
 
-Then I wrote an API-interpreter for them.  Of course, this has to handle
-the general match API (see API.pm and ch-1a.pl for details) which can match
-in multiple places - requiring us to try each possible place, and backtrack.
+Example 1:
+	Input: Triangle = [ [1], [2,4], [6,4,9], [5,1,7,2] ]
+	Output: 8
 
-The API-interpreter successfully does pattern matching, as shown by
-"./ch-1a.pl -t" passing all tests.  So this is a successful proof of concept.
+Explanation: The given triangle
 
-But as yet I have not attempted to translate our patterns such as 'a*c?e'
-into lists of API calls.
+            1
+           2 4
+          6 4 9
+         5 1 7 2
 
+The minimum path sum from top to bottom:  1 + 2 + 4 + 1 = 8
 
-Task 2: "Unique Subsequence
+             [1]
+           [2]  4
+           6 [4] 9
+          5 [1] 7 2
 
-You are given two strings $S and $T.
+Example 2:
 
-Write a script to find out count of different unique subsequences
-in $S matching $T without changing the position of characters.  UPDATE:
-2021-02-08 09:00AM (UK TIME) suggested by Jonas Berlin, missing entry [5].
+	Input: Triangle = [ [3], [3,1], [5,2,3], [4,3,1,3] ]
+	Output: 7
 
-Example 1:
+Explanation: The given triangle
 
-Input: $S = "littleit', $T = 'lit'
-Output: 5
+            3
+           3 1
+          5 2 3
+         4 3 1 3
 
-    1: [lit] tleit
-    2: [li] t [t] leit
-    3: [li] ttlei [t]
-    4: litt [l] e [it]
-    5: [l] ittle [it]
+The minimum path sum from top to bottom: 3 + 1 + 2 + 1 = 7
+
+             [3]
+            3  [1]
+           5 [2] 3
+          4 3 [1] 3
 
-Example 2:
 
-Input: $S = "london', $T = 'lon'
-Output: 3
 
-    1: [lon] don
-    2: [lo] ndo [n]
-    3: [l] ond [on]
 "
 
-My notes: nice question.  Of course one could do this by translating $T
-into a Task-1-style pattern, so lit becomes *l*i*t* and figuring out
-how many different ways that pattern can apply.  But as $T has no meta-chars,
-an easy approach may be possible (locate all positions in $S where head($T)
-appears, for each of them recursively match subtr($S,pos+1) against tail($T))
+My notes: nice question.
diff --git a/challenge-100/duncan-c-white/perl/ch-1.sh b/challenge-100/duncan-c-white/perl/ch-1.sh
new file mode 100755
index 0000000000..e4cf5d1591
--- /dev/null
+++ b/challenge-100/duncan-c-white/perl/ch-1.sh
@@ -0,0 +1,29 @@
+#!/bin/sh -
+#
+# shell script to invoke Perl one-liner.
+#
+# Task 1: "Fun Time
+# 
+# You are given a time (12 hour / 24 hour).
+# 
+# Write a script to convert the given time from 12 hour format to 24 hour
+# format and vice versa.
+# 
+# Ideally we expect a one-liner.
+# 
+# Example 1:
+# 	Input: 05:15 pm or 05:15pm
+# 	Output: 17:15
+# 
+# Example 2:
+# 	Input: 19:15
+# 	Output: 07:15 pm or 07:15pm
+# "
+# 
+# My notes: very simple, I like one liners.  Here are two versions:
+# 
+# first: input (h,m,s), error checking, output (h,m,t)
+#perl -E '$_=join(" ",@ARGV); /^(\d+):(\d\d)\s*([ap]m)$/||die "bad $_"; ($h,$m,$s)=($1,$2,$3); $h+=12 if $s eq "pm" && $h<12; $t=$s ? "":($h>11?"pm":"am");$h-=12 if ! $s && $h>12;say "$h:$m$t"' $*
+
+# second: reuse s, same amount of error checking, modal "if", 2 chars longer
+perl -E '$_=join(" ",@ARGV); /^(\d+):(\d\d)\s*([ap]m)$/||die "bad $_"; ($h,$m,$s)=($1,$2,$3); if( $s ) {$h+=12 if $s eq "pm" && $h<12;$s=""}else{$s=$h>11?"pm":"am";$h-=12 if $h>12} say "$h:$m$s"' $*
diff --git a/challenge-100/duncan-c-white/perl/ch-2.pl b/challenge-100/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..d0dc285a93
--- /dev/null
+++ b/challenge-100/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,162 @@
+#!/usr/bin/perl
+# 
+# Task 2: "Triangle Sum
+# 
+# You are given a triangle array.
+# 
+# Write a script to find the minimum path sum from top to bottom.
+# 
+# When you are on index i on the current row then you may move to either
+# index i or index i + 1 on the next row.
+# 
+# Example 1:
+# 	Input: Triangle = [ [1], [2,4], [6,4,9], [5,1,7,2] ]
+# 	Output: 8
+# 
+# Explanation: The given triangle
+# 
+#             1
+#            2 4
+#           6 4 9
+#          5 1 7 2
+# 
+# The minimum path sum from top to bottom:  1 + 2 + 4 + 1 = 8
+# 
+#              [1]
+#            [2]  4
+#            6 [4] 9
+#           5 [1] 7 2
+# 
+# Example 2:
+# 
+# 	Input: Triangle = [ [3], [3,1], [5,2,3], [4,3,1,3] ]
+# 	Output: 7
+# 
+# Explanation: The given triangle
+# 
+#             3
+#            3 1
+#           5 2 3
+#          4 3 1 3
+# 
+# The minimum path sum from top to bottom: 3 + 1 + 2 + 1 = 7
+# 
+#              [3]
+#             3  [1]
+#            5 [2] 3
+#           4 3 [1] 3
+# "
+# 
+# My notes: nice question.  Superficially: try all paths, keep
+# track of the smallest score.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+use Data::Dumper;
+
+my $debug=0;
+die "Usage: triangle-sum [--debug] 'triangle string'\n"
+	unless GetOptions( "debug" => \$debug )
+	    && @ARGV==1;
+
+my $tristr = shift @ARGV;
+
+my @row = parsetristr( $tristr );
+
+say "Input: $tristr";
+#say Dumper( \@row );
+
+my( $min, $minpath ) = minimumtrisum( @row );
+chop $minpath;
+say "Output: $min";
+say " (Path $minpath)";
+
+#
+# my @row = parsetristr( $tristr );
+#	Parse a triangle string, as shown above in
+#	the various example, lots of []..  Returns
+#	a triangular 2-d array.
+#
+fun parsetristr( $str )
+{
+	$str =~ s/^\s*\[\s*//;
+	$str =~ s/^\s*\[\s*//;
+	$str =~ s/\s*\]\s*$//;
+	$str =~ s/\s*\]\s*$//;
+
+	my @rowstr = split( /\s*\]\s*, \[\s*/, $str );
+	my @result;
+	my $row;
+	for( my $rn=0; $row = shift @rowstr; $rn++ )
+	{
+		my @onerow = split(/\s*,\s*/,$row);
+		my $nor = @onerow;
+		die "bad tristr $str, row $rn, row:$row, onerow:".
+			Dumper(\@onerow) unless $nor == $rn+1;
+		push @result, \@onerow;
+	}
+	return @result;
+}
+
+
+#
+# my( $minsum, $minpath ) = minimumtrisum( @m );
+#	Find the minimum triangle sum (and the path leading
+#	to that min sum ) in triangle matrix @m
+#
+fun minimumtrisum( @m )
+{
+	# start min off at sum( all elements in @m )
+	my $min = 0;
+	foreach my $row (@m)
+	{
+		$min += $_ for @$row;
+	}
+	#say "initial min: $min";
+
+	my $minpath = "";
+	path_rec( "", 0, 0, 0, \$min, \$minpath, @m );
+
+	return ( $min, $minpath );
+}
+
+
+#
+# path_rec( $path, $sum, $row, $col, $min, $bestpath, @m );
+#	Recursively search all possible paths from $row,$col downwards,
+#	finding the minimum of all of the paths' sums.  $sum is the
+#	sum of values above row $row to this point (along $path).  $$min
+#	is the minimum sum discovered so far (and $$bestpath is path leading
+#	to $$min, which we update as we find better ones.
+#
+fun path_rec( $path, $sum, $row, $col, $min, $bestpath, @m )
+{
+	my $nrows = @m;
+	my $el = $m[$row][$col];
+	say "entry: pr($path, ($row,$col): el:$el, m:$$min,s:$sum)" if $debug;
+	$sum += $el;
+	$path .= "$el-";
+	if( $row == $nrows-1 )
+	{
+		# ok, reached bottom of triangle
+		say "pr: ($row,$col): reached bottom row, path=$path, sum=$sum"
+			if $debug;
+		if( $sum < $$min )
+		{
+			$$min = $sum;
+			$$bestpath = $path;
+		}
+	} else
+	{
+		# onto next row
+		$row++;
+
+		# two paths to try: [col] and [col+1]
+		path_rec( $path, $sum, $row, $col, $min, $bestpath, @m );
+		path_rec( $path, $sum, $row, $col+1, $min, $bestpath, @m );
+	}
+}
diff --git a/challenge-100/duncan-c-white/perl/mkTypes b/challenge-100/duncan-c-white/perl/mkTypes
deleted file mode 100755
index c15c733c43..0000000000
--- a/challenge-100/duncan-c-white/perl/mkTypes
+++ /dev/null
@@ -1,200 +0,0 @@
-#!/usr/bin/perl
-
-use strict;
-use warnings;
-use lib qw(/homes/dcw/lib/perl5/DCW);
-use Datadec;
-
-my $posexpr = q(
-PosExpr = I( int n )	"$1"
-	or N( string name ) "$1"
-	or NO( string name, char op, int n ) "$1$2$3"
-);
-
-my $extra = q!
-
-my $debug = 0;
-sub setdebug { my($d) = @_; $debug = $d; }
-
-#
-# my($pe,$leftover) = parse($input);
-#	Parse $input, a string starting with a position expression,
-#	delivering the position expression in $pe and the leftover
-#	input in $leftover.  Die screaming if no well formed pos expr
-#	can be found at the start of $input.
-#	A position expression is either \d+ or name or name '+'|'-' \d+
-#	The internal form of a posexpr is ['I', int const] or ['N', name]
-#	or ['NO', name, +-, offset]
-#
-sub parse ($)
-{
-	my( $input ) = @_;
-	if( $input =~ s/^(\d+)\s*// )
-	{
-		return ( PosExpr->I($1), $input );
-	}
-	$input =~ s/^(\w+)\s*// ||
-		die "bad input in pos expr $input, name expected\n";
-	my $name = $1;
-	if( $input =~ s/^([\+-])\s*(\d+)\s*// )
-	{
-		return ( PosExpr->NO($name,$1,$2), $input );
-	}
-	return ( PosExpr->N($name), $input );
-}
-
-#
-# my $pos = $pe->eval($poshash);
-#	Evaluate the given PosExpr $pe, using %$poshash
-#	for name lookup.  Returns the actual position (a number).
-#
-sub eval ($$)
-{
-	my( $self, $poshash ) = @_;
-	if( $self->kind eq 'I' )
-	{
-		return $self->I;
-	} elsif( $self->kind eq 'N' )
-	{
-		my $name = $self->N;
-		die "error in PosExpr::eval($self): ".
-		    "no such name $name in poshash ". Dumper($poshash)
-			unless exists $poshash->{$name};
-		return $poshash->{$name};
-	} else    # if( $self->kind eq 'NO' )
-	{
-		my ($name, $op, $n) = $self->NO;
-		die "error in PosExpr::eval($self): ".
-		    "no such name $name in poshash ". Dumper($poshash)
-			unless exists $poshash->{$name};
-		die "error in PosExpr::eval($self): bad op $op\n" unless
-			$op eq '+' || $op eq '-';
-		$n = - $n if $op eq '-';
-		return $poshash->{$name} + $n;
-	}
-}
-
-
-
-!;
-
-open( my $fh, '>', "PosExpr.pm" ) || die;
-say $fh gen_datatype( $posexpr, $extra );
-
-close($fh);
-
-my $api = q(
-API = F( string lit, string name )	"F '$1' -> $2"
-    or L( string lit, string name )	"L '$1' -> $2"
-    or M( string lit, posexpr atorafter, string name )	"M '$1' $2 -> $3"
-    or T( posexpr pe1, string op, posexpr pe2 )		"T $1$2$3"
-    or C( int mn, posexpr pe1, posexpr pe2)		"C $1 $2 $3"
-);
-
-$extra = q%
-
-my $debug = 0;
-sub setdebug { my($d) = @_; $debug = $d; }
-
-#
-# my @api = parse( $input );
-#	Parse $input, a string containing a comma-separated sequence
-#	of Abstract Pattern Instructions, return the list of apis.
-#	Die screaming if parsing fails.
-#	For example, matching the pattern a*e is represented by the
-#	following api string:
-#	F'a'->pa,L'e'->plast,Tplast>pa-1,C0 pa+1 plast-1
-#	The individual api forms are:
-#		F'str'->name
-#		L'str'->name
-#		M'str' posexpr->name
-#		Tposexpr ('>'|'=') posexpr
-#		C\d+ posexpr [posexpr]
-#	where posexpr = \d+ or name or name '+'|'-' \d+
-#
-sub parse ($)
-{
-	my( $input ) = @_;
-	my @result;
-	while( $input )
-	{
-		# F'str'->name
-		if( $input =~ s/^F\s*// )
-		{
-			$input =~ s/^'([^']+)'\s*->\s*(\w+)// ||
-				die "bad input $input in F..\n";
-			my $api = API->F($1, $2);
-			say "debug: parsed api $api, rest input $input"
-				if $debug;
-			push @result, $api;
-		}
-		# L'str'->name
-		elsif( $input =~ s/^L\s*// )
-		{
-			$input =~ s/^'([^']+)'\s*->\s*(\w+)// ||
-				die "bad input $input in L..\n";
-			my $api = API->L($1, $2);
-			say "debug: parsed api $api, rest input $input"
-				if $debug;
-			push @result, $api;
-		}
-		# M'str' posexpr->name
-		elsif( $input =~ s/^M\s*// )
-		{
-			$input =~ s/^'([^']+)'\s+// ||
-				die "bad input $input in M..\n";
-			my $str = $1;
-			(my $pe,$input) = PosExpr::parse($input);
-			die "bad input $input in M$str $pe...\n"
-				unless $input =~ s/^\s*->\s*(\w+)//;
-			my $pname = $1;
-			my $api = API->M($str, $pe, $pname);
-			say "debug: parsed api $api, rest input $input"
-				if $debug;
-			push @result, $api;
-		}
-		# Tposexpr ('>'|'=') posexpr
-		elsif( $input =~ s/^T\s*// )
-		{
-			(my $pe,$input) = PosExpr::parse($input);
-			$input =~ s/^(>|=)// ||
-				die "bad input $input in T$pe, > or = expected\n";
-			my $op = $1;
-			(my $pe2,$input) = PosExpr::parse($input);
-			my $api = API->T($pe, $op, $pe2);
-			say "debug: parsed api $api, rest input $input"
-				if $debug;
-			push @result, $api;
-		}
-		# C\d+ posexpr [posexpr]
-		elsif( $input =~ s/^C\s*// )
-		{
-			$input =~ s/^(\d+)\s*// ||
-				die "bad input $input in C.. integer expected\n";
-			my $mn = $1;
-			(my $pe,$input) = PosExpr::parse($input);
-			$input =~ s/^\s*//;
-
-			# second posexpr is optional:
-			# present if next ch is not ','
-			my $pe2 = $pe;
-			if( $input ne '' && $input !~ /^,/ )
-			{
-				($pe2,$input) = PosExpr::parse($input);
-			}
-			my $api = API->C($mn, $pe, $pe2);
-			say "debug: parsed api $api, rest input $input"
-				if $debug;
-			push @result, $api;
-		}
-		$input =~ s/^\s*,\s*//;
-	}
-	die "bad input $input, non empty but not F|L|M|T|C..\n" if $input;
-	return @result;
-}
-%;
-
-
-open( $fh, '>', "API.pm" ) || die;
-say $fh gen_datatype( $api, $extra );
-close($fh);