imported my solutions to this week's tasks (and imported a few historic improvements to code comments in earlier solutions of mine)

3 files changed, 242 insertions, 33 deletions

diff --git a/challenge-151/duncan-c-white/README b/challenge-151/duncan-c-white/README
index 4c7c2d807d..b4889e4611 100644
--- a/challenge-151/duncan-c-white/README
+++ b/challenge-151/duncan-c-white/README
@@ -1,48 +1,74 @@
-TASK #1 - Fibonacci Words
+TASK #1 - Binary Tree Depth
 
-You are given two strings having same number of digits, $a and $b.
+You are given binary tree.
 
-Write a script to generate Fibonacci Words by concatenation of the
-previous two strings. Finally print 51st digit of the first term having
-at least 51 digits.
+Write a script to find the minimum depth.
 
-Example:
+The minimum depth is the number of nodes from the root to the nearest
+leaf node (node without any children).
 
-    Input: $a = '1234' $b = '5678'
-    Output: 7
+Example 1:
 
-    Fibonacci Words:
+  Input: '1 | 2 3 | 4 5'
 
-    '1234'
-    '5678'
-    '12345678'
-    '567812345678'
-    '12345678567812345678'
-    '56781234567812345678567812345678'
-    '1234567856781234567856781234567812345678567812345678'
+                1
+               / \
+              2   3
+             / \
+            4   5
 
-    The 51st digit in the first term having at least 51 digits
-    '1234567856781234567856781234567812345678567812345678' is 7.
+  Output: 2
 
-MY NOTES: Pretty easy.  Fibonacci words == append two previous strings.
-Use -d (debug mode) to see all the above explanatory info.
+Example 2:
 
+  Input: '1 | 2 3 | 4 *  * 5 | * 6'
 
-TASK #2 - Square-free Integer
+                1
+               / \
+              2   3
+             /     \
+            4       5
+             \
+              6
+  Output: 3
 
-Write a script to generate all square-free integers <= 500.
+MY NOTES: well, if I built a binary tree from the input, it would be quite
+simple to find the minimum depth.  But there must be a way to solve the
+problem using only the input syntax.  Something like: split into rows on '|'.
+Each row has 2 * (rowno-1) elements (starting at row 1).  If a row hasn't
+got that many elements, pad it with '*'s.  Now, find the first non-full row,
+ie. with one or more '*'s.  Take the row a pair of elements at a time. If
+any pair are both '*'s, then the min depth is rowno-1.  Otherwise proceed
+to the next row, and keep going down the rows.
 
-In mathematics, a square-free integer (or squarefree integer) is an
-integer which is divisible by no perfect square other than 1. That is,
-its prime factorization has exactly one factor for each prime that
-appears in it. For example, 10 = 2 * 5 is square-free, but 18 = 2 *
-3 * 3 is not, because 18 is divisible by 9 = 3**2.
 
-Example
+TASK #2 - Rob The House
 
-The smallest positive square-free integers are
-    1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, ...
+You are planning to rob a row of houses, always starting with the first
+and moving in the same direction. However, you can't rob two adjacent
+houses.
 
-MY NOTES: also pretty easy.  The second definition above suggests using prime
-numbers, which is easy enough, especially as I have a prime generating module,
-but actually it's simpler to do it without primes as the first definition hints.
+Write a script to find the highest possible gain that can be achieved.
+
+Example 1:
+
+  Input: @valuables = (2, 4, 5);
+  Output: 7
+
+If we rob house 0 we get 2 and then the only house we can rob is house
+2 where we have 5.  So the total valuables in this case is (2 + 5) = 7.
+
+
+Example 2:
+
+  Input: @valuables = (4, 2, 3, 6, 5, 3);
+  Output: 13
+
+The best choice would be to first rob house 0 then rob house 3 then finally
+house 5.  This would give us 4 + 6 + 3 =13.
+
+
+MY NOTES: Hmm.. some sort of recursive "find all paths" method.
+It always helps to pick the right function purpose and name.
+I think the recursive function we need is: 
+my $maxvaluables = maxrobbery( startpos ), invoked as my $max=maxrobbery(0)?
diff --git a/challenge-151/duncan-c-white/perl/ch-1.pl b/challenge-151/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..e0ad0e559a
--- /dev/null
+++ b/challenge-151/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,94 @@
+#!/usr/bin/perl
+# 
+# TASK #1 - Binary Tree Depth
+# 
+# You are given binary tree.
+# 
+# Write a script to find the minimum depth.
+# 
+# The minimum depth is the number of nodes from the root to the nearest
+# leaf node (node without any children).
+# 
+# Example 1:
+# 
+#   Input: '1 | 2 3 | 4 5'
+# 
+#                 1
+#                / \
+#               2   3
+#              / \
+#             4   5
+# 
+#   Output: 2
+# 
+# Example 2:
+# 
+#   Input: '1 | 2 3 | 4 *  * 5 | * 6'
+# 
+#                 1
+#                / \
+#               2   3
+#              /     \
+#             4       5
+#              \
+#               6
+#   Output: 3
+# 
+# MY NOTES: well, if I built a binary tree from the input, it would be quite
+# simple to find the minimum depth.  But there must be a way to solve the
+# problem using only the input syntax.  Something like: split into rows on '|'.
+# Each row should have 2 * (rowno-1) elements (starting at row 1).  If a row hasn't
+# got that many elements, pad it with '*'s.  Now, find the first non-full row,
+# ie. with one or more '*'s.  Take the row a pair of elements at a time. If
+# any pair are both '*'s, then the min depth is rowno-1.  Otherwise proceed
+# to the next row, and keep going down the rows.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+#use Data::Dumper;
+
+my $debug=0;
+die "Usage: min-tree-depth [--debug] 'binary tree in rows with *s for missing entries]\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV==1;
+my $input = shift;
+
+#
+# my $mindepth = mindepth( $treeinput );
+#	Given an encoded binary tree, with '|' separating rows, spaces
+#	separating elements, and '*' representing missing elements not
+#	at the end of a row, find and return the minimum depth of the tree.
+#
+sub mindepth ($)
+{
+	my( $treeinput ) = @_;
+
+	my @row = split( /\s*\|\s*/, $treeinput );
+
+	my $expectednel = 1;		# how many elements the row is expected
+					# to have: it doubles each time
+
+	foreach my $rowno (1..@row)
+	{
+		my $row = $row[$rowno-1];
+		my @el = split( /\s+/, $row );
+
+		# pad the elements out with '*'s if too few..
+		push @el, ( '*' ) x ($expectednel - @el);
+
+		#say "row $rowno has *s: ", Dumper \@el;
+		# Consider each pair of elements (a,b):
+		while( (my $a, my $b, @el) = @el )
+		{
+			# If they're BOTH '*' the mindepth is rowno-1
+			return $rowno-1 if $a eq '*' && $b eq '*';
+		}
+		$expectednel *= 2;
+	}
+	return scalar(@row);
+}
+
+my $mindepth = mindepth( $input );
+say $mindepth;
diff --git a/challenge-151/duncan-c-white/perl/ch-2.pl b/challenge-151/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..87720291ec
--- /dev/null
+++ b/challenge-151/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,89 @@
+#!/usr/bin/perl
+# 
+# TASK #2 - Rob The House
+# 
+# You are planning to rob a row of houses, always starting with the first
+# and moving in the same direction. However, you can't rob two adjacent
+# houses.
+# 
+# Write a script to find the highest possible gain that can be achieved.
+# 
+# Example 1:
+# 
+#   Input: @valuables = (2, 4, 5);
+#   Output: 7
+# 
+# If we rob house 0 we get 2 and then the only house we can rob is house
+# 2 where we have 5.  So the total valuables in this case is (2 + 5) = 7.
+# 
+# Example 2:
+# 
+#   Input: @valuables = (4, 2, 3, 6, 5, 3);
+#   Output: 13
+# 
+# The best choice would be to first rob house 0 then rob house 3
+# then finally house 5.  This would give us 4 + 6 + 3 =13.
+# 
+# MY NOTES: Hmm.. some sort of recursive "find all paths" method.
+# It always helps to pick the right function purpose and name.
+# I think the recursive function we need is: 
+# my $maxvaluables = maxrobbery( startpos ), invoked as
+# my $max=maxrobbery(0)?
+#
+# Extra note: if you want to which the house numbers and corresponding
+# valuables that make up the maximum robbery, run this with the -d flag.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+#use Data::Dumper;
+
+my $debug=0;
+
+die "Usage: rob-houses [--debug] house_values\n" unless
+	GetOptions( "debug"=>\$debug ) && @ARGV>0;
+
+my @valuables = @ARGV;
+
+
+#
+# my( $maxvaluables, @robhouses ) = maxrobbery( $starthouseno, @valuables );
+#	Given a list of valuables @valuables, and a starting house number
+#	$starthouseno, try all combinations of houses to rob, always robbing
+#	house $starthouseno, not robbing house $starthouseno+1 and considering
+#	whether or not to rob each subsequent house, and return the
+#	( maximum sum of valuables, and list of robbed house numbers that
+#	gave the maximum sum of valuables).
+#
+fun maxrobbery( $starthouseno, @valuables )
+{
+	my @besth;
+	my $besttotal = 0;
+	foreach my $hno ($starthouseno+2..$#valuables)
+	{
+		# find the best partial solution starting by robbing house $hno
+		my( $mv2, @rh2 ) = maxrobbery( $hno, @valuables );
+
+		# then find the best of all those partial solutions
+		if( $mv2 > $besttotal )
+		{
+			$besttotal = $mv2;
+			@besth = @rh2;
+		}
+	}
+	# then the overall best solution involves adding starthouseno
+	# to the best partial solution..
+	return ( $valuables[$starthouseno]+$besttotal, $starthouseno, @besth );
+}
+
+
+my( $maxvaluables, @robhouses ) = maxrobbery( 0, @valuables );
+say "max valuables is $maxvaluables";
+say "got by robbing house numbers ",
+	join(', ',
+		map { "$robhouses[$_] (value $valuables[$robhouses[$_]])" }
+		       0..$#robhouses
+	) if $debug;