Perl Weekly Challenge: Week 89

In the computing world, the beginning of December is marked by numerous Advent Calendars which contain 25 days of articles or programming challenges. One of my favorites is the Advent of Code which is about increasingly difficult puzzles with a Christmas theme which require a good knowledge of algorithms to solve. Usually I do it in C++ but this year, this blog post by Daniel 'codesections' Sockwell, an entry in the Raku Advent Calendar, convinced me to use Raku instead (or along with; I'll probably go back and do all the problems in C++ later.) Six days in, I must say I'm very impressed by how versatile Raku has been. I usually complete both of each days puzzles in under an hour which is much faster than I ever managed with cumbersome C++. Daniel has made a git repo for sharing solutions; you can find mine here.

The Weekly Challenge also has an Advent Calendar which showcases solutions from previous weeks which caught Mohammeds interest. My solution to PWC 42 challenge 1 is day 1.

Lastly if you look at my full code, you will notice that I now use the .raku extension on my scripts and start them with #!/usr/bin/raku. Partly it is because I finally upgraded to Rakudo 2020.10 and fixed my system and editor etc. so they don't use /usr/bin/perl6 and the .p6 extension anymore but also because it is important for the advancement of Raku. Andrew Shitov explains why.

On to this weeks challenges...

Challenge 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)

Raku has a builtin method for gcd and one for finding all 2-element combinations so we can aolve the challenge with a one liner.

say [+] (1 .. @*ARGS[0]).combinations(2).map({ [gcd] @_ });

(Full code on Github.)

Unfortunately Perl does not have such amenities so we have to roll our own.

The combinations() routine is one I wrote a long time ago and have used in many previous weeks challenges.

To replace .gcd() I wrote this function based on this.

sub gcd {
    my ($a, $b) = @_;

    return 0 == $b ? $a : gcd($b, $a % $b);
}

We don't have [+] in Perl either but it can be simulated by an accumulating variable like $sum. The end result is this:

my $sum = 0;

for my $combo (combinations([1 .. $N], 2)) {
    $sum += gcd($combo->[0], $combo->[1]);
}

say $sum;

(Full code on Github.)

Challenge 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

There is probably a smarter algorithm for solving this but the problem space is small enough to use brute force. This is the Raku version.

sub MAIN() {

The .permutations() method gives us all possible combinations of the range 1 - 9. For each permutation, we fill a 2d array called @matrix.

    for (1 .. 9).permutations -> @permutation {

        my @matrix;
        for @permutation.batch(3) -> @row {
            @matrix.push(@row);
        }

Now we just test...

every row:

        ([+] @matrix[0]) == 15 || next;
        ([+] @matrix[1]) == 15 || next;
        ([+] @matrix[2]) == 15 || next;

every column:

        ([+] @matrix[*;0]) == 15 || next;
        ([+] @matrix[*;1]) == 15 || next;
        ([+] @matrix[*;2]) == 15 || next;

And the two diagonals:

        ([+] (@matrix[0;0], @matrix[1;1], @matrix[2;2])) == 15 || next;
        ([+] (@matrix[0;2], @matrix[1;1], @matrix[2;0])) == 15 || next;

In each test we see if the sum is 15 and if it is not, it is pointless to test further so we skip to the next permutation.

Note the elegant way we can specify slices of a 2d array.

If we pass all the tests, we have the correct answer and we can print out @matrix.

        for 0 ..^ @matrix.elems -> $row {
            say q{[ }, @matrix[$row].join(q{ }), q{ ]};
        }

And then we quit checking permutations.

        last;
    }
}

(Full code on Github.)

When solving the challenge in Perl, we once again have to deal mainly with replacing missing functionality.

For permutions, I used a routine called permute() which is taken from the perlfaq4 POD page.

To replace [+] I wrote this function:

sub sum {
    my @arr = @_;
    my $sum = 0; 
    for my $i (@arr) {
        $sum += $i;
    }

    return $sum;
}

Now the body of the script looks like this:

my @permutations;
permute { push @permutations, \@_; } (1 .. 9);

for my $permutation (@permutations) {

Unlike with Raku, I made @matrix a one dimensional array this time. It makes the next parts slightly easier.

    my @matrix = @{$permutation};

    sum( @matrix[0, 1, 2] ) == 15 || next;
    sum( @matrix[3, 4, 5] ) == 15 || next;
    sum( @matrix[6, 7, 8] ) == 15 || next;
    sum( @matrix[0, 3, 6] ) == 15 || next;
    sum( @matrix[1, 4, 7] ) == 15 || next;
    sum( @matrix[2, 5, 8] ) == 15 || next;
    sum( @matrix[0, 4, 8] ) == 15 || next;
    sum( @matrix[2, 4, 6] ) == 15 || next;

However calculating how to print rows of three becomes slightly harder.

    for my $row (0 .. 2) {
        say q{[ }, (join q{ }, @matrix[$row * 3 .. $row * 3 + 2]), q{ ]};
    }

    last;
}

(Full code on Github.)