laurent_r

These are some answers to the Week 89 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Task 1: GCD Sums

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)

GCD Sums in Raku

Raku has the infix gcd operator which computes the GCD for us. Thus, chaining the compinations, gcd, map, and sum built-in routines yields a solution fitting in just one code line:

use v6;

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

We could also use the [] reduction metaoparator with the + operator:

say (1..$_).combinations(2).map({[gcd] $_[0,1]}).sum for 1..1..@*ARGS[0];

Both solutions lead to the following output

$ raku gcd-sum.raku 10
0
1
3
7
11
20
26
38
50
67

GCD Sums in Perl

We first implement a gcd subroutine that uses the Euclidean algorithm to compute the GCD of two numbers. We then use a doubly nested for loop to generate all pairs of numbers between 1 and the input ceiling parameter:

use strict;
use warnings;
use feature "say";

sub gcd {
        my ($i, $j) = sort { $a <=> $b } @_;
        while ($j) {
                ($i, $j) = ($j, $i % $j);
        }
        return $i;
}
my $n = shift;
my $sum = 0;
for my $i (1..$n) {
    for my $j ($i+1..$n) {
        $sum += gcd $i, $j;
    }
}
say $sum;

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

This is more commonly known as a magic square. A square array of numbers, usually positive integers, is called a magic square if the sums of the numbers in each row, each column, and both main diagonals are the same. Albrecht Dürer’s famous engraving Melencolia I (1514) includes an order 4 square with magic sum 34.

Magic Square in Raku

I originally started to write a recursive subroutine to populate the square with all possible combinations of integers between 1 and 9 (or 1 and 126 for order 4 squares. This turned out to be a bit clumsy. I changed my mind and decided to use the permutations built-in routine to generate all possible lists of 9 integers (between 1 and 9) and only after that to transform them into squares of numbers and check whether they form a magic square.

use v6;
constant \SIZE = 3;
constant \MAX = SIZE - 1;
constant \SUM = (([+] 1..SIZE*SIZE)/SIZE).Int;

my ($count-perm, $count-mat) = 0, 0;

sub print-matrix (@matrix) {
    for @matrix -> @row {
        say '[', @row.fmt("%2i").join(" "), ' ]';
    }
    say " ";
}
sub col-sum (@matrix, Int $j) {
    my $sum = 0;
    $sum += @matrix[$_][$j] if defined @matrix[$_][$j] for 0..MAX;
    return $sum;
}
sub cross_sum (@matrix) {
    my $nw2se = 0;
    $nw2se += @matrix[$_][$_] for 0..MAX;
    my $ne2sw = 0;
    $ne2sw += @matrix[$_][MAX-$_] for 0..MAX;
    return $nw2se, $ne2sw;
}
sub is-valid (@matrix) {
    for (0..MAX) -> $k {
        return False if (col-sum @matrix, $k) != SUM;
    }
    return True if SUM == all cross_sum @matrix;
    return False;
}

sub find-matrices {
    my @int-list = 1..9;
    OUT: for @int-list.permutations -> $perm {
        $count-perm++;
        my @matrix = gather {
            for $perm.Array -> $i, $j, $k {
                next OUT unless $i + $j + $k == SUM;
                take [ $i, $j, $k ];
            }
        }
        $count-mat++;
        next unless is-valid @matrix; 
        print-matrix @matrix;
        # last;
    }
}

find-matrices;   
say "Counters: $count-perm $count-mat";

Note that, for performance improvement, the find-matrices routine skips early on any matrix in which any line sum if not equal to the target sum. This way, instead of having to check 362,880 (9!) matrices, we need to verify only 2,592 of them (less than 1% of the total).

This is the output displayed by this program:

$ raku magic-square2.raku
[ 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 ]

Counters: 362880 2592

The implementation above is still way too complicated. It would be better to work all the way with one-dimension arrays, and to transform them into squares at the last moment. I don’t have time to refactor this program now, but the Perl implementation below uses this much simpler implementation (despite having no permutations built-in).

Magic Square in Perl

As noted above, this implementation does all the work on flat arrays of 9 integers, and transforms them into squares only when it is needed at the latest moment for the purpose of printing the squares that have been found to be magic.

use strict;
use warnings;
use feature "say";
use constant SUM => 15;

my @in = 1..9;
my @permutations;

sub print_matrix {
    my @matrix = ( [@{$_}[0..2]], [@{$_}[3..5]], [@{$_}[6..8]] );
    for my $row (@matrix)  {
        say "[", (map { sprintf "% 2i", $_ } @$row), " ]"; # for @$row;
    }
    say " ";
}

sub sum {
    my $sum = 0;
    $sum += $_ for @_;
    return $sum;
}

sub permute {
    my ($in, $left) = @_;
    if (scalar @$left == 0) {
        return 
            # lines
            if sum( @{$in}[0..2]) != SUM
            or sum( @{$in}[3..5]) != SUM
            or sum( @{$in}[6..8]) != SUM
            # columns
            or sum( @{$in}[0, 3, 6]) != SUM
            or sum( @{$in}[1, 4, 7]) != SUM
            or sum( @{$in}[2, 5, 8]) != SUM 
            # diagonals
            or sum( @{$in}[0, 4, 8]) != SUM 
            or sum( @{$in}[2, 4, 6]) != SUM;
        push @permutations, $in;
        return;
    }
    for my $candidate (@$left) {
        my @vals = @$in;
        push @vals, $candidate;
        permute(\@vals, [grep $_ != $candidate, @$left]);
    }
}

permute [], \@in;
print_matrix \$_ for @permutations;

This displays the following:

$ perl magic-square.pl
[ 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 ]

Perl Weekly Challenge # 89 in Scala

As I mentioned elsewhere, what I like in Scala is the ability to combine the object-oriented and functional programming paradigms, like Raku and to a lesser degree Perl. Please note that I am a beginner in Scala, don’t look here for idionmatic Scala or for good practices.

GCD Sum

The Scala math BigInt library has a gcd routine, but I decided to implement the gcd function (using the Euclidean algorithm) myself because I wasn’t keen on using big integers for this task. This is essentially a port to Scala of my GCD program in Perl.

object Main {
  def main(args: Array[String]): Unit = {
    val in: Int = if (args.size == 1) args(0).toInt else 10
    var sum = 0
    for (m <- 1 to in) {
      for (n <- m + 1 to in) {
        sum += gcd(m, n)
      }
    }
    println(s"Sum of GCD to $in is $sum")
  }
  def gcd(a: Int, b: Int): Int = {
    var (i, j) = (a, b)
    while (j > 0) {
      var t = i
      i = j
      j = t % j
    }
    return i
  }
}

This prints out the following output:

Sum of GCD to 10 is 67

Magic Square in Scala

This is again essentially a port to Scala of my Perl program.

import Array._
object Main {
  def main(args: Array[String]): Unit = {
    var mat = range(1, 10)
    var in = Array.empty[Int]
    permute(in, mat)
  }
  def print_matrix(a: Array[Int]): Unit = {
    println(s"[ ${a(0)} ${a(1)} ${a(2)} ]")
    println(s"[ ${a(3)} ${a(4)} ${a(5)} ]")
    println(s"[ ${a(6)} ${a(7)} ${a(8)} ]")
    println(" ")
  }
  def permute(in: Array[Int], left: Array[Int]): Unit = {
    val sum = 15
    if (left.size == 0) {
      if (
        in.slice(0, 3).sum != sum ||
        in.slice(3, 6).sum != sum ||
        in.slice(6, 9).sum != sum ||
        in(0) + in(3) + in(6) != sum ||
        in(1) + in(4) + in(7) != sum ||
        in(2) + in(5) + in(8) != sum ||
        in(0) + in(4) + in(8) != sum ||
        in(2) + in(4) + in(6) != sum 
      ) {
        return
      }
      print_matrix(in)
      return
    }
    for (candidate <- left) {
      val values: Array[Int] = in.appended(candidate)
      val newleft: Array[Int] = left.filter(_ != candidate)
      permute(values, newleft)
    }
  }
}

This program displays the following output:

[ 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 ]

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, December 13, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.