diff options
| -rwxr-xr-x | challenge-089/wlmb/perl/ch-1.pl | 39 | ||||
| -rwxr-xr-x | challenge-089/wlmb/perl/ch-2.pl | 130 |
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] +# ] |