Merge pull request #2928 from dcw803/master

imported my solutions, two nice easy puzzles, I enjoyed the magic matrix

3 files changed, 229 insertions, 44 deletions

diff --git a/challenge-089/duncan-c-white/README b/challenge-089/duncan-c-white/README
index decc181333..a5b283e113 100644
--- a/challenge-089/duncan-c-white/README
+++ b/challenge-089/duncan-c-white/README
@@ -1,63 +1,44 @@
-Task 1: "Array of Product
+Task 1: "GCD Sum
 
-You are given an array of positive integers @N.
-
-Write a script to return an array @M where $M[i] is the product of all elements of @N except the index $N[i].
+You are given a positive integer $N.
+Write a script to sum GCD of all possible unique pairs between 1 and $N.
 
 Example 1:
 
-Input:
-    @N = (5, 2, 1, 4, 3)
-Output:
-    @M = (24, 60, 120, 30, 40)
+	Input: 3
+	Output: 3
 
-    $M[0] = 2 x 1 x 4 x 3 = 24
-    $M[1] = 5 x 1 x 4 x 3 = 60
-    $M[2] = 5 x 2 x 4 x 3 = 120
-    $M[3] = 5 x 2 x 1 x 3 = 30
-    $M[4] = 5 x 2 x 1 x 4 = 40
+	gcd(1,2) + gcd(1,3) + gcd(2,3)
 
 Example 2:
 
-Input:
-    @N = (2, 1, 4, 3)
-Output:
-    @M = (12, 24, 6, 8)
+	Input: 4
+	Output: 7
 
-    $M[0] = 1 x 4 x 3 = 12
-    $M[1] = 2 x 4 x 3 = 24
-    $M[2] = 2 x 1 x 3 = 6
-    $M[3] = 2 x 1 x 4 = 8
+	gcd(1,2) + gcd(1,3) + gcd(1,4) + gcd(2,3) + gcd(2,4) + gcd(3,4)
 "
 
-My notes: clearly defined.  So M[i] is product(all elements)/M[i]
-Hang on! unless M[i]==0 in which it's product(all other elements)
-
+My notes: very clearly defined.  Haven't used GCDs for a while:-)
 
-Task 2: "Spiral Matrix
 
-You are given m x n matrix of positive integers.
+Task 2: "Magical Matrix
 
-Write a script to print a spiral path throught the matrix as list.
+Write a script to display matrix as below with numbers 1 - 9. Please make sure numbers are used once.
 
-Example 1:
+[ a b c ]
+[ d e f ]
+[ g h i ]
 
-Input:
-    [ 1, 2, 3 ]
-    [ 4, 5, 6 ]
-    [ 7, 8, 9 ]
-Ouput:
-    [ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]
-
-Example 2:
+So that it satisfies the following:
 
-Input:
-    [  1,  2,  3,  4 ]
-    [  5,  6,  7,  8 ]
-    [  9, 10, 11, 12 ]
-    [ 13, 14, 15, 16 ]
-Output:
-    [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
+a + b + c = 15
+d + e + f = 15
+g + h + i = 15
+a + d + g = 15
+b + e + h = 15
+c + f + i = 15
+a + e + i = 15
+c + e + g = 15
 "
 
-My notes: clearly defined.  Is "a spiral path" clear?  Think so.
+My notes: clearly defined.  Constraint problem.
diff --git a/challenge-089/duncan-c-white/perl/ch-1.pl b/challenge-089/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..dffd760515
--- /dev/null
+++ b/challenge-089/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,62 @@
+#!/usr/bin/perl
+#
+# Task 1: "GCD Sum
+# 
+# You are given a positive integer $N.
+# Write a script to sum GCD of all possible unique pairs between 1 and $N.
+# 
+# Example 1:
+# 
+# 	Input: 3
+# 	Output: 3
+# 
+# 	gcd(1,2) + gcd(1,3) + gcd(2,3)
+# 
+# Example 2:
+# 
+# 	Input: 4
+# 	Output: 7
+# 
+# 	gcd(1,2) + gcd(1,3) + gcd(1,4) + gcd(2,3) + gcd(2,4) + gcd(3,4)
+# "
+# 
+# My notes: very clearly defined.  Haven't used GCDs for a while:-)
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+
+#
+# my $gcd = gcd( $a, $b );
+#	Compute and return the GCD (Greatest Common Denominator) of $a and $b.
+#
+sub gcd ($$)
+{
+	my( $a, $b ) = @_;
+	while( $b != 0 )
+	{
+		( $a, $b ) = ( $b, $a % $b );
+	}
+	return $a;
+}
+
+
+my $debug = 0;
+die "Usage: gcd-sum [--debug] N\n" unless
+	GetOptions( "debug" => \$debug ) &&
+	@ARGV==1;
+my $n = shift;
+
+my $sum = 0;
+foreach my $a (1..$n-1)
+{
+	foreach my $b ($a+1..$n)
+	{
+		my $gcd = gcd($a,$b);
+		say "sum += gcd($a,$b):$gcd" if $debug;
+		$sum += $gcd;
+	}
+}
+say $sum;
diff --git a/challenge-089/duncan-c-white/perl/ch-2.pl b/challenge-089/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..ac8e75e00a
--- /dev/null
+++ b/challenge-089/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,142 @@
+#!/usr/bin/perl
+#
+# Task 2: "Magical Matrix
+#
+# Write a script to display matrix as below with numbers 1 - 9. Please make sure numbers are used once.
+# 
+# [ a b c ]
+# [ d e f ]
+# [ g h i ]
+# 
+# So that it satisfies the following:
+# 
+# a + b + c = 15
+# d + e + f = 15
+# g + h + i = 15
+# a + d + g = 15
+# b + e + h = 15
+# c + f + i = 15
+# a + e + i = 15
+# c + e + g = 15
+# "
+# 
+# My notes: clearly defined.  Constraint problem.
+# 
+
+use strict;
+use warnings;
+use Data::Dumper;
+use Function::Parameters;
+use feature 'say';
+use Getopt::Long;
+
+my $debug = 0;
+die "Usage: magic-square [--debug]\n" unless
+	GetOptions( "debug" => \$debug ) &&
+	@ARGV==0;
+
+
+#
+# thirdrow( $a, $b, $c, $d, $e, $f, %used );
+#	Given consistent values $a..$f which satisfy all constraints for the
+#	first two rows, and %used, the set of all values $a..$f, try to
+#	find values of the third row ($g, $h and $i) which work, printing
+#	any solutions we find.  Of course, all of $h, $h and $i are forced
+#	by the earlier values..
+#
+fun thirdrow( $a, $b, $c, $d, $e, $f, %used )
+{
+	my $g=15-$a-$d;		# g is forced
+
+	# now check $g
+	if( $g>=1 && $g<=9 && ! $used{$g} )
+	{
+		$used{$g} = 1;
+		say "$a $b $c\n$d $e $f\n$g ? ?\n" if $debug;
+
+		my $h = 15-$b-$e;	# h is forced
+
+		# now check $h
+		if( $h>=1 && $h<=9 && ! $used{$h} )
+		{
+			$used{$h} = 1;
+			say "$a $b $c\n$d $e $f\n$g $h ?\n" if $debug;
+
+			my $i=15-$g-$h;		# $i is forced
+
+			# now check $i
+			if( $i>=1 && $i<=9 && ! $used{$i} && $a+$e+$i==15 && $c+$f+$i==15 )
+			{
+				say "solution:\n$a $b $c\n$d $e $f\n$g $h $i";
+			}
+
+			delete $used{$h};
+		}
+		delete $used{$g};
+	}
+}
+
+
+#
+# secondrow( $a, $b, $c, %used );
+#	Given a consistent first row of a magic square $a, $b and $c,
+#	which satisfy first row constraints (i.e. are distinct values in the
+#	range 1..9 which sum to 15), and %used (the set of $a, $b and $c),
+#	find all possible magic squares by finding all possible values for
+#	the second and third rows..  print out all solutions found.
+#
+fun secondrow( $a, $b, $c, %used )
+{
+	foreach my $d (1..9)
+	{
+		next if $used{$d} || $a+$d>14;
+		$used{$d} = 1;
+		foreach my $e (1..9)
+		{
+			next if $used{$e} || $a+$e>14 || $b+$e>14 || $d+$e>14;
+			$used{$e} = 1;
+
+			my $f = 15-$d-$e;			# f is forced
+			if( $f>=1 && $f<=9 && ! $used{$f} )
+			{
+				$used{$f} = 1;
+
+				thirdrow( $a, $b, $c, $d, $e, $f, %used );
+
+				delete $used{$f};
+			}
+			delete $used{$e};
+		}
+		delete $used{$d};
+	}
+}
+
+
+#
+# allsquares();
+#	Try all magic squares, printing out all solutions found.
+#
+fun allsquares(  )
+{
+	# first the top row $a, $b and $c:
+	foreach my $a (1..9)
+	{
+		my %used = ($a=>1);
+		foreach my $b (1..9)
+		{
+			next if $used{$b} || $a+$b>14;
+			$used{$b} = 1;
+			my $c = 15-$a-$b;			 # c is forced
+			if( $c>=1 && $c<=9 && ! $used{$c} )
+			{
+				$used{$c} = 1;
+				secondrow( $a, $b, $c, %used );
+				delete $used{$c};
+			}
+			delete $used{$b};
+		}
+	}
+}
+
+
+allsquares();