imported my solutions for this week's tasks..

3 files changed, 338 insertions, 41 deletions

diff --git a/challenge-056/duncan-c-white/README b/challenge-056/duncan-c-white/README
index 35d999c58b..d8c3c6d88b 100644
--- a/challenge-056/duncan-c-white/README
+++ b/challenge-056/duncan-c-white/README
@@ -1,57 +1,57 @@
-Task 1: "Flip Binary
+Task 1: "Diff-K
 
-You are given a binary number B, consisting of N binary digits 0 or 1: s0, s1
-.. s(N-1).
+You are given an array @N of positive integers (sorted) and another non
+negative integer k.
 
-Choose two indices L and R such that 0 <= L <= R < N and flip the digits s(L),
-s(L+1) .... s(R). By flipping, we mean change 0 to 1 and vice-versa.
+Write a script to find if there exists 2 indices i and j such that A[i]
+- A[j] = k and i != j.
 
-For example, given the binary number 010, the possible flip pair results
-are listed below:
+It should print the pairs of indices, if any such pairs exist.
 
-    L=0, R=0 the result binary: 110
-    L=0, R=1 the result binary: 100
-    L=0, R=2 the result binary: 101
-    L=1, R=1 the result binary: 000
-    L=1, R=2 the result binary: 001
-    L=2, R=2 the result binary: 011
+Example:
 
-Write a script to find the indices (L,R) that results in a binary number
-with maximum number of 1s. If you find more than one maximal pair L,R
-then print all of them.
+    @N = (2, 7, 9)
+    $k = 2
 
-Continuing our example, note that we had three pairs (L=0, R=0), (L=0,
-R=2), and (L=2, R=2) that resulted in a binary number with two 1s,
-which was the maximum. So we would print all three pairs.
+Output : 2,1"
 
-My notes: sounds interesting.  Do we need to first compute the maximum
-numbers of 1s and then compute all (L,R) pairs having that value? Hopefully
-not.
+My notes: sounds entirely straightforward.
 
 
-Task 2: "Wave Array
+Task 2: "Path Sum
 
-Any array N of non-unique, unsorted integers can be arranged into a
-wave-like array such that n1 >= n2 <= n3 >= n4 <= n5 and so on.
+You are given a binary tree and a sum, write a script to find if the tree
+has a path such that adding up all the values along the path equals the
+given sum. Only complete paths (from root to leaf node) may be considered
+for a sum.
 
-For example, given the array [1, 2, 3, 4], possible wave arrays include
-[2, 1, 4, 3] or [4, 1, 3, 2], since 2 >= 1 <= 4 >= 3 and 4 >= 1 <= 3 >= 2.
-This is not a complete list.
+Example
 
-Write a script to print all possible wave arrays for an integer array
-N of arbitrary length.
+Given the below binary tree and sum = 22,
 
-Notes:
+          5
+         / \
+        4   8
+       /   / \
+      11  13  9
+     /  \      \
+    7    2      1
 
-When considering N of any length, note that the first element is always greater than or equal to the second, and then the >=, <=, >= sequence alternates until
-the end of the array.
+For the given binary tree, the partial path sum 5 - 8 - 9 = 22 is not valid.
+
+The script should return the path 5 - 4 - 11 - 2 whose sum is 22.
 "
 
-My notes: sounds cute.  How to get started? possible values of n1 are any
-value in the array APART FROM THE SMALLEST ONE, eg given 1..4, n1=2..4
-Then n2 is any other value of the array <= n1; given n1 and n2 and list of
-unused elements @u, n3 is any element in @u that is >= n2.
-eg given 1..4, and n1=2, n2=1, n3 is 3 or 4.  Some sort of recursion should
-do the trick (initially I thought 2 mutually recursive functions, one to
-extend with a value LESS than or equal, the other to extend with a value
-GREATER than or equal, but then I collapsed that via the parameter $less).
+My notes: Obvious question: how to represent binary tree.  Let's go with..
+a traditional Perl OO self-printing package inline in the main program.
+
+Second question: we'll need to parse a binary tree from the command line,
+so what text format do we want to represent a parsable binary tree on the command line?
+After some thought, decided on (5,(4,(11,l7,l2),n),(8,l13,(9,n,1))) where
+(N,L,R) represents a node with value N, left tree L and right tree R;
+lN represents a leaf with value N
+n represents nil
+
+There's a lot more code for this task 2 than for many, I don't know if
+there's some simpler way of doing it that I'm missing?  Perhaps there's
+a more concrete way of representing a binary tree that supports path summing?
diff --git a/challenge-056/duncan-c-white/perl/ch-1.pl b/challenge-056/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..f255505cc4
--- /dev/null
+++ b/challenge-056/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,39 @@
+#!/usr/bin/perl
+#
+# Task 1: "Diff-K
+#
+# You are given an array @N of positive integers (sorted) and another non
+# negative integer k.
+# 
+# Write a script to find if there exists 2 indices i and j such that A[i]
+# - A[j] = k and i != j.
+# 
+# It should print the pairs of indices, if any such pairs exist.
+# 
+# Example:
+# 
+#     @N = (2, 7, 9)
+#     $k = 2
+# 
+# Output : 2,1"
+# 
+# My notes: sounds entirely straightforward.
+#
+
+use feature 'say';
+use strict;
+use warnings;
+
+die "Usage: diff-k K ARRAY_OF_INTEGERS\n" unless @ARGV > 1;
+
+my $k = shift;
+my @n = @ARGV;
+
+foreach my $i (0..$#n)
+{
+	foreach my $j (0..$#n)
+	{
+		next if $i==$j;
+		say "$i,$j" if $n[$i]-$n[$j]==$k;
+	}
+}
diff --git a/challenge-056/duncan-c-white/perl/ch-2.pl b/challenge-056/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..bc707a8e66
--- /dev/null
+++ b/challenge-056/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,258 @@
+#!/usr/bin/perl
+# 
+# Task 2: "Path Sum
+# 
+# You are given a binary tree and a sum, write a script to find if the tree
+# has a path such that adding up all the values along the path equals the
+# given sum. Only complete paths (from root to leaf node) may be considered
+# for a sum.
+# 
+# Example
+# 
+# Given the below binary tree and sum = 22,
+# 
+#           5
+#          / \
+#         4   8
+#        /   / \
+#       11  13  9
+#      /  \      \
+#     7    2      1
+# 
+# For the given binary tree, the partial path sum 5 - 8 - 9 = 22 is not valid.
+# 
+# The script should return the path 5 - 4 - 11 - 2 whose sum is 22.
+# "
+# 
+# My notes: First obvious question is: how do we represent a binary tree.  Let's go with..
+# a traditional Perl OO self-printing package inline in the main program.
+# Second question: we'll need to parse a binary tree from the command line,
+# so what text format do we want to represent a parsable binary tree on the command line?
+#
+# Haskell style would be the incredibly verbose:
+# node(5,node(4,node(11,leaf(7),leaf(2)),nil),node(8,leaf(13),node(9,nil,leaf(1))))
+#
+# A simplified style, with node() abbreviated to (),
+# leaf abbreviated to 'l', and nil to 'n', would be
+# (5,(4,(11,l(7),l(2)),n),(8,l(13),(9,n,l(1))))
+#
+# or a still simpler form, removing the () on leaves..
+# (5,(4,(11,l7,l2),n),(8,l13,(9,n,1)))
+#
+# So here:
+# (N,L,R) represents a node with value N, left tree L and right tree R;
+# lN represents a leaf with value N
+# n represents nil
+#
+# let's go with that form..  of course, you'll need to single quote the command line arguments
+# as () are treated specially by Unix shells.
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+
+die "Usage: path-sum sum bin-tree\n" unless @ARGV==2;
+my $sum = shift;
+my $treestr = shift;
+
+
+package BinTree;
+
+# Part 1 of the problem: being able to represent a Bin Tree,
+# and parsing a string representation of one.
+
+use overload '""' => \&as_string;
+
+#
+# my $bintree = BinTree->node( $n, $l, $r );
+#	create a BinTree node with number $n, left tree $l and right tree $r.
+#
+method node($class: $n, $l, $r )
+{
+	return bless [
+		'node', $n, $l, $r
+	], $class;
+}
+
+#
+# my $bintree = BinTree->leaf( $n );
+#	create a BinTree leaf with number $n.
+#
+method leaf($class: $n )
+{
+	return bless [
+		'leaf', $n
+	], $class;
+}
+
+#
+# my $bintree = BinTree->nil();
+#	create a BinTree nil.
+#
+method nil($class:)
+{
+	return bless [
+		'nil'
+	], $class;
+}
+
+#
+# my $bintree = BinTree->parse( $str );
+#	Build a new BinTree by parsing the whole of $str.
+#	An example binary tree string might be:
+#		(5,(4,(11,l7,l2),n),(8,l13,(9,n,1)))
+#	die if $str is not a valid representation of the a BinTree.
+#
+method parse( $str )
+{
+	my( $bintree, $leftover ) = BinTree->parse_rec( $str );
+	die "BinTree->parse( $str ): '$leftover' left over at end\n" if $leftover;
+	return $bintree;
+}
+
+#
+# my( $bintree, $leftover ) = BinTree->parse_rec( $str );
+#	Build a new BinTree by parsing $str, telling us what suffix of $str is leftover (in $leftover).
+#	die if $str is not a valid representation of the a BinTree.
+#
+method parse_rec( $str )
+{
+	return ( BinTree->nil(), $str ) if $str =~ s/^n//;
+	return ( BinTree->leaf($1), $str ) if $str =~ s/^l(\d+)//;
+
+	# node: format (\d+,tree,tree)
+	die "BinTree->parse_rec( $str ): 'n', 'l', or '(' expected\n" unless $str =~ s/^\(//;
+
+	# what's left: \d+,tree,tree)
+	die "BinTree->parse_rec( $str ): digit expected\n" unless $str =~ s/^(\d+)//;
+	my $n = $1;
+
+	# what's left: ,tree,tree)
+	die "BinTree->parse( $str ): ',' expected (after number)\n" unless $str =~ s/^,//;
+
+	# what's left: tree,tree)
+	my( $l, $leftover ) = BinTree->parse_rec( $str );
+
+	# what's left: ,tree)
+	die "BinTree->parse( $leftover ): ',' expected (after left sub tree)\n" unless $leftover =~ s/^,//;
+
+	# what's left: tree)
+	my( $r, $rest ) = BinTree->parse_rec( $leftover );
+
+	die "BinTree->parse( $str ): ')' expected\n" unless $rest =~ s/\)//;
+
+	return ( BinTree->node( $n, $l, $r ), $rest );
+}
+
+#
+# my( $kind, @pieces ) = $bintree->breakapart();
+#	Break the given $bintree apart into it's "kind" (node,left or nil),
+#	and it's array of pieces..
+#
+method breakapart()
+{
+	die "bintree->breakapart: given bintree not an array; actually ", Dumper($self) unless ref($self) eq "BinTree";
+	return @$self;
+}
+
+#
+# my $str = $bintree->as_string();
+#	return the given $bintree as a nice printable string.
+#
+sub as_string($)
+{
+	my( $self ) = @_;
+
+	die "bintree->as_string: given bintree not an array; actually ", Dumper($self) unless ref($self) eq "BinTree";
+	my @x = @$self;
+	my $kind = shift @x;
+	if( $kind eq "node" )
+	{
+		my( $n, $l, $r ) = @x;
+		$l = $l->as_string();
+		$r = $r->as_string();
+		return "($n,$l,$r)";
+	} elsif( $kind eq "leaf" )
+	{
+		my( $n ) = @x;
+		return "l$n";
+	} elsif( $kind eq "nil" )
+	{
+		return "n";
+	} else
+	{
+		die "bintree->as_string: given bintree has impossible kind $kind\n";
+	}
+}
+
+
+package main;
+
+my $bintree = BinTree->parse( $treestr );
+say "tree is $bintree";
+
+# Part 2 of the problem: finding a particular path sum in the tree
+my( $found, @list ) = find_sum( $bintree, $sum );
+if( $found )
+{
+	say "$sum found: ", join(',',@list);
+} else
+{
+	say "$sum not found";
+}
+
+
+#
+# my( $found, @list ) = find_sum( $bintree, $sum );
+#	Sum up the values (leaf values and node values)
+#	along a path from the root to each leaf, and find
+#	one (if possible) that sums to $sum.
+#	Return (1, list_values_from_root_to_leaf ) if
+#	you find one such path, or (0) if no such path exists.
+#
+fun find_sum( $bintree, $sum )
+{
+	return find_sum_rec( $bintree, $sum, () );
+}
+
+#
+# my( $found, @list ) = find_sum_rec( $bintree, $sum, @listsofar );
+#	Given a bintree $bintree, a sum $sum to aim for, and a @listsofar
+#	of values on the path above this point, Sum up the values (leaf and node values)
+#	along a path from the root to each leaf, and find the first such path that sums to $sum.
+#	Return (1, list_values_from_root_to_leaf ) if you find one such path,
+#	or (0) if no such path exists.
+#
+fun find_sum_rec( $bintree, $sum, @listsofar )
+{
+	my( $kind, @pieces ) = $bintree->breakapart();
+	if( $kind eq "node" )
+	{
+		my( $n, $l, $r ) = @pieces;
+		return ( 0 ) if $sum<$n;
+		$sum -= $n;
+		push @listsofar, $n;
+		my( $found, @list ) = find_sum_rec( $l, $sum, @listsofar );
+		return( $found, @list ) if $found;
+
+		( $found, @list ) = find_sum_rec( $r, $sum, @listsofar );
+		return( $found, @list );
+
+	} elsif( $kind eq "leaf" )
+	{
+		my( $n ) = @pieces;
+		return ( 0 ) if $sum != $n;
+		push @listsofar, $n;
+		return( 1, @listsofar );
+	} elsif( $kind eq "nil" )
+	{
+		return ( 0 );
+	} else
+	{
+		die "bintree->find_sum: given bintree has impossible kind $kind: ", Dumper($bintree);
+	}
+}