Add solutions by E. Choroba to 089: GCD Sum & Magical Matrix

GCD Sum shows both the naive slow algorithm and the fast one based on
Euler's totient function (studied at
https://www.geeksforgeeks.org/summation-gcd-pairs-n/).

2 files changed, 132 insertions, 0 deletions

diff --git a/challenge-089/e-choroba/perl/ch-1.pl b/challenge-089/e-choroba/perl/ch-1.pl
new file mode 100755
index 0000000000..bd079d650a
--- /dev/null
+++ b/challenge-089/e-choroba/perl/ch-1.pl
@@ -0,0 +1,81 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+
+use List::Util qw{ sum };
+
+sub gcd {
+    my ($i, $j) = @_;
+    while ($j != 0) {
+        ($i, $j) = ($j, $i) if $j < $i;
+        my $d = int($j / $i);
+        $j -= $d * $i;
+    }
+    return $i
+}
+
+sub gcd_sum_naive {
+    my ($n) = @_;
+    my $s = 0;
+    for my $i (2 .. $n) {
+        for my $j (1 .. ($i - 1) / 2) {
+            my $g = gcd($i, $j);
+            $s += 2 * $g;  # Include also gcd($i, $i - $j) == gcd($i, $j)
+        }
+        $s += gcd($i, $i / 2) unless $i % 2;
+    }
+    return $s
+}
+
+{   my @totients;
+    sub totients {
+        my ($n) = @_;
+        @totients = (0 .. $n);
+        for my $p (2 .. $n) {
+            if ($totients[$p] == $p) {
+                $totients[$p] = $p - 1;
+                for (my $i = 2 * $p; $i <= $n; $i += $p) {
+                    $totients[$i] = ($totients[$i] / $p) * ($p - 1);
+                }
+            }
+        }
+    }
+
+    sub gcd_sum {
+        my ($n) = @_;
+        totients($n);
+        my @sums = (0) x $n;
+        for my $i (1 .. $n) {
+            for (my $j = 2; $i * $j <= $n; ++$j) {
+                $sums[ $i * $j ] += $i * $totients[$j];
+            }
+        }
+        for my $i (2 .. $n) {
+            $sums[$i] += $sums[$i - 1];
+        }
+        return $sums[$n]
+    }
+}
+
+use Test::More tests => 8;
+
+is gcd_sum_naive(3), 3, 'Example 1 (naive)';
+is gcd_sum_naive(4), 7, 'Example 2 (naive)';
+is gcd_sum_naive(12), 105, 'Twelve (naive)';
+is gcd_sum_naive(5000), 61_567_426, 'Large (naive)';
+
+is gcd_sum(3), 3, 'Example 1';
+is gcd_sum(4), 7, 'Example 2';
+is gcd_sum(12), 105, 'Twelve';
+is gcd_sum(5000), 61_567_426, 'Large';
+
+use Benchmark qw{ cmpthese };
+cmpthese(-3, {
+    naive    => sub { gcd_sum_naive(1000) },
+    totients => sub { gcd_sum(1000) },
+});
+
+__END__
+           Rate    naive totients
+naive    1.71/s       --    -100%
+totients  570/s   33146%       --
diff --git a/challenge-089/e-choroba/perl/ch-2.pl b/challenge-089/e-choroba/perl/ch-2.pl
new file mode 100755
index 0000000000..1ee69a4daa
--- /dev/null
+++ b/challenge-089/e-choroba/perl/ch-2.pl
@@ -0,0 +1,51 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+use feature qw{ say };
+
+use constant SUM => 15;
+
+sub still_valid {
+    my ($matrix) = @_;
+
+  COORD:
+    for my $coords ([0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6],
+                    [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]) {
+        $matrix->[$_] or next COORD for @$coords;
+        return unless SUM == $matrix->[ $coords->[0] ]
+                           + $matrix->[ $coords->[1] ]
+                           + $matrix->[ $coords->[2] ];
+    }
+    return 1
+}
+
+{   my @solutions;
+    sub fill {
+        my ($matrix, @unused) = @_;
+        unless (@unused) {
+            push @solutions, [@$matrix];
+            return
+        }
+        my $i = 0;
+        ++$i until $i > $#$matrix || $matrix->[$i] == 0;
+        for my $u (0 .. $#unused) {
+            $matrix->[$i] = $unused[$u];
+            fill($matrix, @unused[0 .. $u - 1, $u + 1 .. $#unused])
+                if still_valid($matrix);
+        }
+        $matrix->[$i] = 0;
+    }
+
+    sub magical_matrix {
+        fill([(0) x 9], 1 .. 9);
+        return @solutions
+    }
+}
+
+my @s = magical_matrix();
+for my $m (@s) {
+    say "@$m[0, 1, 2]";
+    say "@$m[3, 4, 5]";
+    say "@$m[6, 7, 8]";
+    say "---";
+}