Merge pull request #4717 from dcw803/master

imported my solutions to this week's challenge - both quite tricky

3 files changed, 338 insertions, 38 deletions

diff --git a/challenge-125/duncan-c-white/README b/challenge-125/duncan-c-white/README
index ab825e9e01..366395c261 100644
--- a/challenge-125/duncan-c-white/README
+++ b/challenge-125/duncan-c-white/README
@@ -1,49 +1,74 @@
-Task 1: "Write a script to print the Venus Symbol, international gender
-symbol for women. Please feel free to use any character.
-
-    ^^^^^
-   ^     ^
-  ^       ^
- ^         ^
- ^         ^
- ^         ^
- ^         ^
- ^         ^
-  ^       ^
-   ^     ^
-    ^^^^^
-      ^
-      ^
-      ^
-    ^^^^^
-      ^
-      ^
-"
+Task 1: "Pythagorean Triples
 
-My notes: sounds like a print statement to reproduce the given input.
+You are given a positive integer $N.
 
+Write a script to print all Pythagorean Triples containing $N as a
+member. Print -1 if it can't be a member of any. i
 
-Task 2: "Tug of War
+Triples with the same set of elements are considered the same, i.e. if
+your script has already printed (3, 4, 5), (4, 3, 5) should not be
+printed.
 
-You are given a set of $n integers (n1, n2, n3, ...).
+The famous Pythagorean theorem states that in a right angle triangle,
+the length of the two shorter sides and the length of the longest
+side are related by a2+b2 = c2.
 
-Write a script to divide the set in two subsets of n/2 sizes each so
-that the difference of the sum of two subsets is the least. If $n is
-even then each subset must be of size $n/2 each. In case $n is odd then
-one subset must be ($n-1)/2 and other must be ($n+1)/2.
+A Pythagorean triple refers to the triple of three integers whose lengths
+can compose a right-angled triangle.
 
 Example
 
-  Input:        Set = (10, 20, 30, 40, 50, 60, 70, 80, 90, 100)
-  Output:  Subset 1 = (30, 40, 60, 70, 80)
-           Subset 2 = (10, 20, 50, 90, 100)
+    Input: $N = 5
+    Output:
+        (3, 4, 5)
+        (5, 12, 13)
+
+    Input: $N = 13
+    Output:
+        (5, 12, 13)
+        (13, 84, 85)
+
+    Input: $N = 1
+    Output:
+        -1
+"
+
+My notes: the tricky part here is knowing how to generate all Pythagorean
+triples that MIGHT contain $N, i.e. when to stop generating triples..
+
+
+Task 2: "Binary Tree Diameter
+
+You are given binary tree as below:
+
+    1
+   / \
+  2   5
+ / \ / \
+3  4 6  7
+       / \
+      8  10
+     /
+    9
+
+Write a script to find the diameter of the given binary tree.
+
+    The diameter of a binary tree is the length of the longest path between any two nodes in a tree. It doesn't have to pass through the root.
+
+For the above given binary tree, possible diameters (6) are:
+
+3, 2, 1, 5, 7, 8, 9
+
+or
+
+4, 2, 1, 5, 7, 8, 9
+
+
+UPDATE (2021-08-10 17:00:00 BST): Jorg Sommrey corrected the example.
 
-  Input:        Set = (10, -15, 20, 30, -25, 0, 5, 40, -5)
-           Subset 1 = (30, 0, 5, -5)
-           Subset 2 = (10, -15, 20, -25, 40)
+The length of a path is the number of its edges, not the number of the vertices it connects. So the diameter should be 6, not 7.
 "
 
-My notes: sounds like a "generate and test" problem.  Easy to do inefficiently,
-	  challenging to try to make efficient.
-	  Let's start by counting from 0 to 2^n-1 and using the bits
-	  to select which subset to put each value into.
+My notes: Looks quite tricky.  We can use generate and test - if we can
+generate all paths, then we could do a "max" test.  Also, how to represent
+the binary tree?  let's hard-code it for now.
diff --git a/challenge-125/duncan-c-white/perl/ch-1.pl b/challenge-125/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..82bec3f1dd
--- /dev/null
+++ b/challenge-125/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,81 @@
+#!/usr/bin/perl
+# 
+# Task 1: "Pythagorean Triples
+# 
+# You are given a positive integer $N.
+# 
+# Write a script to print all Pythagorean Triples containing $N as a
+# member. Print -1 if it can't be a member of any. i
+# 
+# Triples with the same set of elements are considered the same, i.e. if
+# your script has already printed (3, 4, 5), (4, 3, 5) should not be
+# printed.
+# 
+# The famous Pythagorean theorem states that in a right angle triangle,
+# the length of the two shorter sides and the length of the longest
+# side are related by a2+b2 = c2.
+# 
+# A Pythagorean triple refers to the triple of three integers whose lengths
+# can compose a right-angled triangle.
+# 
+# Example
+# 
+#     Input: $N = 5
+#     Output:
+#         (3, 4, 5)
+#         (5, 12, 13)
+# 
+#     Input: $N = 13
+#     Output:
+#         (5, 12, 13)
+#         (13, 84, 85)
+# 
+#     Input: $N = 1
+#     Output:
+#         -1
+# "
+# 
+# My notes: the tricky part here is knowing how to generate all Pythagorean
+# triples that MIGHT contain $N, i.e. when to stop generating triples..
+# I think, when you've checked a + b, if int(sqrt(a*a+b*b))==b then stop
+# considering bigger b values.
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+#use Data::Dumper;
+
+my $debug=0;
+die "Usage: pythagorean triples N\n" unless
+	GetOptions( "debug"=>\$debug ) && @ARGV==1;
+my $n = shift;
+die "pt: N ($n) must be > 0\n" unless $n>0;
+
+my $found = 0;
+foreach my $a (1..$n)
+{
+	my $a2 = $a * $a;
+	for( my $b = $a+1; ; $b++ )
+	{
+		last if $a < $n && $b > $n;	# fallen off
+
+		#say "trying a=$a, b=$b";
+		my $b2 = $b * $b;
+		my $sum = $a2 + $b2;
+		my $c = int(sqrt($sum));
+
+	if( $c == $b )				# fallen off
+	{
+		say "found upper limit for a=$a: b=$b" if $debug;
+		last;
+	}
+
+		next unless $sum == $c * $c;
+		next unless $a==$n || $b==$n || $c==$n;
+		say "found $a $b $c";
+		$found++;
+	}
+}
+say "-1" unless $found;
diff --git a/challenge-125/duncan-c-white/perl/ch-2.pl b/challenge-125/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..c6c3c41d31
--- /dev/null
+++ b/challenge-125/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,194 @@
+#!/usr/bin/perl
+# 
+# Task 2: "Binary Tree Diameter
+# 
+# You are given binary tree as below:
+# 
+#     1
+#    / \
+#   2   5
+#  / \ / \
+# 3  4 6  7
+#        / \
+#       8  10
+#      /
+#     9
+# 
+# Write a script to find the diameter of the given binary tree.
+# 
+# The diameter of a binary tree is the length of the longest path between
+# any two nodes in a tree. It doesn't have to pass through the root.
+# 
+# For the above given binary tree, possible diameters (6) are:
+# 
+# 3, 2, 1, 5, 7, 8, 9
+# 
+# or
+# 
+# 4, 2, 1, 5, 7, 8, 9
+# 
+# 
+# UPDATE (2021-08-10 17:00:00 BST): Jorg Sommrey corrected the example.
+# 
+# The length of a path is the number of its edges, not the number of
+# the vertices it connects. So the diameter should be 6, not 7.
+# "
+# 
+# My notes: Looks quite tricky.  We can use generate and test - if we can
+# generate all paths, then we could do a "max" test.  Also, how to represent
+# the binary tree?  let's hard-code it for now.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+my $debug = 0;
+
+die "Usage: tree-diameter [hard code in program]\n" unless @ARGV==0;
+
+
+# ======================= Tree building routines ====================
+
+
+#
+# my $t = l( $v );
+#	Generate a tree leaf with value $v, and empty parent.
+#
+fun l( $v )
+{
+	return { tag => 'l', v => $v, parent => undef };
+}
+
+
+#
+# my $t = n( $v );
+#	Generate a tree node with empty left tree, empty right tree,
+#	empty parent and value $v.
+#
+fun n( $v )
+{
+	return { tag => 'n', l => undef, v => $v, r => undef, parent => undef };
+}
+
+
+#
+# setleft( $parent, $child );
+#	Mark $child as the left child of $parent and vice versa
+#
+fun setleft( $parent, $child )
+{
+	$parent->{l} = $child;
+	$child->{parent} = $parent;
+}
+
+
+#
+# setright( $parent, $child );
+#	Mark $child as the right child of $parent and vice versa
+#
+fun setright( $parent, $child )
+{
+	$parent->{r} = $child;
+	$child->{parent} = $parent;
+}
+
+
+#     1
+#    / \
+#   2   5
+#  / \ / \
+# 3  4 6  7
+#        / \
+#       8  10
+#      /
+#     9
+my $one = n( 1 );
+my $two = n( 2 );
+my $three = l( 3 );
+my $four = l( 4 );
+
+setleft( $one, $two );
+setleft( $two, $three );
+setright( $two, $four );
+
+my $five = n( 5 );
+setright( $one, $five );
+
+my $six = l( 6 );
+setleft( $five, $six );
+my $seven = n( 7 );
+setright( $five, $seven );
+my $eight = n( 8 );
+setleft( $seven, $eight );
+
+my $nine = l( 9 );
+setleft( $eight, $nine );
+my $ten = l( 10 );
+setright( $seven, $ten );
+
+#die Dumper( $one );
+
+
+# ======================= Pathfinding routines ====================
+
+
+#
+# findallpaths( $t, $pathfunc );
+#	Find all complete paths through tree $t - and call
+#	$pathfunc->( @nodes ) for each one.
+#
+fun findallpaths( $t, $pathfunc )
+{
+	say "find all paths starting at $t->{v}" if $debug>1;
+	follow( $t, [$t->{v}], {}, $pathfunc );
+
+	if( $t->{tag} eq 'n' )
+	{
+		findallpaths( $t->{l}, $pathfunc ) if $t->{l};
+		findallpaths( $t->{r}, $pathfunc ) if $t->{r};
+	}
+}
+
+
+#
+# follow( $t, $been, $used, $pathfunc );
+#	Follow all paths from $t (with elements we've visited @$been)
+#	and used set %$used, calling $pathfunc->( @$been ) for each
+#	complete path found.
+#
+fun follow( $t, $been, $used, $pathfunc )
+{
+	my $tv = $t->{v};
+	my $edges = 0;
+	foreach my $edge (qw(parent l r))
+	{
+		my $e = $t->{$edge};
+		next unless defined $e;
+		my $ev = $e->{v};
+		next if $used->{$ev};
+		$edges++;
+		say "follow: go along $edge from $tv to $ev" if $debug>1;
+		my @newb = @$been;
+		push @newb, $ev;
+		follow( $e, \@newb, { %$used, $tv=>1 }, $pathfunc );
+	}
+	$pathfunc->( @$been ) if $edges==0;
+}
+
+
+my $maxlen = 0;
+my @longpath = ();
+findallpaths( $one,
+	fun(@p) {
+		say "poss path: ", join( ',', @p ) if $debug;
+		my $len = @p-1;
+		if( $len > $maxlen )
+		{
+			$maxlen = $len;
+			@longpath = @p;
+		}
+		} );
+say "$maxlen: ", join(',',@longpath);