Add answers to challenge 89 1 and 2

2 files changed, 169 insertions, 0 deletions

diff --git a/challenge-089/wlmb/perl/ch-1.pl b/challenge-089/wlmb/perl/ch-1.pl
new file mode 100755
index 0000000000..f91579a220
--- /dev/null
+++ b/challenge-089/wlmb/perl/ch-1.pl
@@ -0,0 +1,39 @@
+#!/usr/bin/env perl
+# Perl weekly challenge 89
+# Challenge 1.
+# Given $N, calculate the sum of the greatest common divisors of all
+# unique pairs of numbers between 1 and $N
+
+# Load packages
+use warnings;
+use strict;
+use v5.10;
+use List::Util qw(sum0);
+
+# I use a straight forward approach
+# First I define a recursive function for the gcd using Euclid's algorithm
+sub gcd {
+    # I assume that both arguments are non-negative
+    my ($a, $b)=@_;
+    return $a if $b==0;
+    return gcd($b, $a%$b);
+}
+# Now I generate recursively all unique pairs of numbers between $n
+# and $m
+sub pairs {
+    # I assume both arguments are integer and different
+    my ($n, $m)=@_;
+    return () if $n>=$m; #no more pairs
+    return ((map {[$n,$_]} ($n+1..$m)),  #pairs starting in $n
+	    pairs($n+1, $m));          # and the rest
+}
+sub sumgcd { # sum gcd for all pairs
+    # I assume $N is a positive integer
+    my $N=shift;
+    sum0 map {gcd($_->[0], $_->[1])} pairs(1,$N);
+}
+
+# Test a few cases:
+say join " ", map {sumgcd($_)} (2..20);
+# Answer:
+# 1 3 7 11 20 26 38 50 67 77 105 117 142 172 204 220 265 283 335
diff --git a/challenge-089/wlmb/perl/ch-2.pl b/challenge-089/wlmb/perl/ch-2.pl
new file mode 100755
index 0000000000..46f797c047
--- /dev/null
+++ b/challenge-089/wlmb/perl/ch-2.pl
@@ -0,0 +1,130 @@
+#!/usr/bin/env perl
+# Perl weekly challenge 89
+# Challenge 2.
+# Magical matrix. Build a 3x3 matrix so that the sums of all rows, columns and diagonals is 15
+
+# Load packages
+use warnings;
+use strict;
+use v5.10;
+
+# generate all permutations of a set using a callback function to test each
+# permutation. Stop when callback returns success (true) or when no more permutations
+# I use this technique to avoid storing all 9! permutations in
+# memory. With a callback I can generate them and test them one at a time.
+
+sub permutations {
+    my ($callback, $all_flag, @set)=@_;
+    permutations_ancillary($callback, $all_flag, [], [@set]); #use auxiliary function
+}
+
+# Append the permutations of @$rest to @$first and call the callback
+# when a permutation is completed. Continue generating permutations
+# until success or until no more  permutations. Returns success
+# The idea is to fix the first element and recursively permute the
+# rest. Then change the first element and iterate.
+sub permutations_ancillary {
+    my $callback=shift; # callback function
+    my $all_flag=shift; # flag to generate all magical matrices
+    my @first=@{shift @_}; # first elements
+    my @rest=@{shift @_};  # elements to permute
+    return $callback->($all_flag, @first) unless @rest; # finished?
+    foreach (0..$#rest){
+	# choose one element to add to first and permute the rest
+	my @new_first=@first;
+	my @new_rest=@rest;
+	push @new_first, splice @new_rest, $_, 1;
+	my $success=permutations_ancillary($callback, $all_flag, [@new_first], [@new_rest]);
+	return $success if $success;
+    }
+}
+
+# Test if a permutation of 1..9 corresponds to a Magic Square
+sub test_magic {
+    use PDL; #Use perl data language to simplify coding matrix operations
+    use PDL::NiceSlice;
+    my $all_flag=shift;
+    my $square=pdl(@_)->reshape(3,3); # turn array into pdl square matrix
+    my $ok=    all($square->sumover==15)                    # check sum of rows
+	    && all($square->transpose->sumover==15)         # of columns
+	    && $square->diagonal(0,1)->sumover==15          # of main diagonal
+            && $square->(-1:0)->diagonal(0,1)->sumover==15; # and of inverted diagonal
+    if($ok){
+	say $square;
+	return !$all_flag; # replace 1 by 0 to generate all magical matrices.
+    }
+    return 0;
+}
+
+# Test
+say "Generate one magical matrix";
+permutations(\&test_magic, 0, 1..9);
+
+say "Generate all magical matrices";
+permutations(\&test_magic, 1, 1..9);
+#Output
+
+# Generate one magical matrix
+#
+# [
+#  [2 7 6]
+#  [9 5 1]
+#  [4 3 8]
+# ]
+#
+# Generate all magical matrices
+#
+# [
+#  [2 7 6]
+#  [9 5 1]
+#  [4 3 8]
+# ]
+#
+#
+# [
+#  [2 9 4]
+#  [7 5 3]
+#  [6 1 8]
+# ]
+#
+#
+# [
+#  [4 3 8]
+#  [9 5 1]
+#  [2 7 6]
+# ]
+#
+#
+# [
+#  [4 9 2]
+#  [3 5 7]
+#  [8 1 6]
+# ]
+#
+#
+# [
+#  [6 1 8]
+#  [7 5 3]
+#  [2 9 4]
+# ]
+#
+#
+# [
+#  [6 7 2]
+#  [1 5 9]
+#  [8 3 4]
+# ]
+#
+#
+# [
+#  [8 1 6]
+#  [3 5 7]
+#  [4 9 2]
+# ]
+#
+#
+# [
+#  [8 3 4]
+#  [1 5 9]
+#  [6 7 2]
+# ]