This is my response to the Perl Weekly Challenge #089.
@N.
1 and
$N.
Input: 3
Output: 3
gcd(1,2) + gcd(1,3) + gcd(2,3)
Input: 4
Output: 7
gcd(1,2) + gcd(1,3) + gcd(1,4) + gcd(2,3) + gcd(2,4) + gcd(3,4)
Raku does not have a built-in function for this, but I did in fact implement a procedure for this in my Centenary Sequences with Raku - Part 5: Divisors and Factors article. We can reuse it, as is.
#! /usr/bin/env raku
subset PositiveInt of Int where * > 0; # [1]
unit sub MAIN (PositiveInt $N, :v(:$verbose)); # [1]
say (1..$N).combinations(2).map( *.&gcd ).sum; # [2]
sub gcd (@numbers) # [3]
{
my %common = divisors(@numbers[0]) (&) divisors(@numbers[1]); # [3a]
my @common = %common.keys.sort; # [3b]
my $gcd = @common[* -1]; # [3c]
say ":: GCD(@numbers[0], @numbers[1]) -> $gcd" if $verbose;
return $gcd; # [3d]
}
sub divisors ($number, :$not-self, :$not-one) # [4]
{
my @divisors;
for ($not-one ?? 2 !! 1) .. $number/2 -> $candidate
{
@divisors.push: $candidate if $number %% $candidate;
}
@divisors.push: $number unless $not-self;
return @divisors;
}
[1] Positive integers only.
[2] Take all the combinations of two numbers among the numbers
1 to $N, and apply the «gcd» procedure on those
combinations (with map. Note the .& syntax for calling
a procedure with a method invocation look-alike syntax. This in effect reduces
the list of pairs to a list of single values. And finally we apply .sum
to add those values together.
[3] Get the list of divisors from both
numbers, and get the intersection of them (the values present in both lists) [3a].
The result is a hash-like structure, so we must use .keys to get
the actual values. The keys are unsorted, so we remedy that with .sort
[3b]. The last value in the array is the largest, and thus the greatest common
divisor [3c, 3d].
[4] Copied verbatim, as said in the preamble.
See
docs.raku.org/language/operators#methodop_.&
for more information about the special procedure invocation syntax .&.
See
docs.raku.org/routine/(&), infix ∩
for more information about the intersection operator (&), also
available as the Unicode character ∩.
Running it:
$ ./gcd-sum 3
3
$ ./gcd-sum 4
7
With verbose mode:
$ ./gcd-sum -v 3
:: GCD(1, 2) -> 1
:: GCD(1, 3) -> 1
:: GCD(2, 3) -> 1
3
$ ./gcd-sum -v 4
:: GCD(1, 2) -> 1
:: GCD(1, 3) -> 1
:: GCD(1, 4) -> 1
:: GCD(2, 3) -> 1
:: GCD(2, 4) -> 2
:: GCD(3, 4) -> 1
7
#! /usr/bin/env perl
use strict;
use feature 'say';
use feature 'signatures';
no warnings qw(experimental::signatures);
use Algorithm::Combinatorics 'combinations';
use List::MoreUtils 'duplicates';
use Getopt::Long;
my $verbose = 0;
GetOptions("verbose" => \$verbose);
my $N = $ARGV[0] // die "Please specify an integer > 0";
die "Please specify an integer > 0" unless $N =~ /^[1-9]\d*$/;
my @all = (1 .. $N);
my $sum = 0;
for my $pair (combinations(\@all, 2))
{
$sum += gcd(@$pair);
}
say $sum;
sub gcd ($a, $b)
{
my @a = divisors($a);
my @b = divisors($b);
my @common = duplicates(@a, @b); # [1]
my $gcd = $common[$#common]; # [1a]
say ":: GCD($a, $b) -> $gcd" if $verbose;
return $gcd;
}
sub divisors ($number)
{
my @divisors = (1);
for my $candidate (2 .. $number/2)
{
push(@divisors, $candidate) if $number % $candidate == 0;
}
push(@divisors, $number);
return @divisors;
}
[1] Instead of the Intersection (in Raku), I use «List::MoreUtils::duplicates» which gives the values that occur more than once. The order of the values is left as is, so the largest value is at the end [1a].
The program above crashed for me, as Perl was unable to locate «duplicates»:
./gcd-sum-perl 4
Could not find sub 'duplicates' exported by List::MoreUtils at
./gcd-sum-perl line 9.
BEGIN failed--compilation aborted at ./gcd-sum-perl line 9.
I have no idea why it failed. But a workaround is to remove the «use» line, and add the procedure to the program.
A version of the program («gcd-sum-perl-errorfix») doing just that, is included in the zip file.
Note that I had the excact same problem in my article Two Triplets with Raku and Perl.
Running it gives the same result as the Raku version:
$ ./gcd-sum-perl-errorfix 3
3
$ ./gcd-sum-perl-errorfix 4
4
$ ./gcd-sum-perl-errorfix -v 3
:: GCD(1, 2) -> 1
:: GCD(1, 3) -> 1
:: GCD(2, 3) -> 1
3
$ ./gcd-sum-perl-errorfix -v 4
:: GCD(1, 2) -> 1
:: GCD(1, 3) -> 1
:: GCD(1, 4) -> 1
:: GCD(2, 3) -> 1
:: GCD(2, 4) -> 2
:: GCD(3, 4) -> 1
7
1 - 9. Please make
sure numbers are used once.
[ a b c ]
[ d e f ]
[ g h i ]
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
#! /usr/bin/env raku
unit sub MAIN (:v(:$verbose), :a(:$all)); [1]
for (1..9).permutations -> @candidate [1]
{
say ":: @candidate[]" if $verbose;
my ($a, $b, $c, $d, $e, $f, $g, $h, $i) = @candidate; # [2]
next unless $a + $b + $c == 15; # [2a]
next unless $d + $e + $f == 15;
next unless $g + $h + $i == 15;
next unless $a + $d + $g == 15;
next unless $b + $e + $h == 15;
next unless $c + $f + $i == 15;
next unless $a + $e + $i == 15;
next unless $c + $e + $g == 15;
say "[ { @candidate[0..2] } ]"; # [3]
say "[ { @candidate[3..5] } ]";
say "[ { @candidate[6..8] } ]";
say "" if $all;
last unless $all; # [4]
}
[1] This is a brute force approach. I generate all the possible permutations of the numbers 1 to 9 (with the three matrix rows laid out after each other in a single list).
[2] Then I assign the values to the variables given in the equations in the challenge, and check that they are satisfied [2a].
[3] If they are, we have a match.
[4] Stop after the first match, unless asked for all of them.
Running it:
$ ./magical-matrix
[ 2 7 6 ]
[ 9 5 1 ]
[ 4 3 8 ]
Running it with verbose mode will generate a lot of output, so I'll refrain from showing it. The «-a» (all) option shows all the matches, and not just the first:
$ ./magical-matrix -a
[ 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 ]
#! /usr/bin/env perl
use strict;
use feature 'say';
use Getopt::Long;
use Algorithm::Combinatorics 'permutations';
my $verbose = 0;
my $all = 0;
GetOptions("verbose" => \$verbose,
"all" => \$all);
my @source = 1..9;
for my $list (permutations(\@source))
{
my @candidate = @$list;
say ":: " . join(@candidate, ", ") if $verbose;
my ($a, $b, $c, $d, $e, $f, $g, $h, $i) = @candidate;
next unless $a + $b + $c == 15;
next unless $d + $e + $f == 15;
next unless $g + $h + $i == 15;
next unless $a + $d + $g == 15;
next unless $b + $e + $h == 15;
next unless $c + $f + $i == 15;
next unless $a + $e + $i == 15;
next unless $c + $e + $g == 15;
say "[ " . join(" ", @candidate[0..2]) . " ]";
say "[ " . join(" ", @candidate[3..5]) . " ]";
say "[ " . join(" ", @candidate[6..8]) . " ]";
say "" if $all;
last unless $all;
}
Running it gives the same result as the Raku version:
$ ./magical-matrix-perl
[ 2 7 6 ]
[ 9 5 1 ]
[ 4 3 8 ]
$ ./magical-matrix-perl -a
[ 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 ]
And that's it.