Wherein we give the Witches the podium again, to combine and recombine the root elements contained in all of us…
THE WEEKLY CHALLENGE – PERL & RAKU #89
episode one:
“The Roots Beneath Our Feet”
TASK #1 › GCD Sum
Submitted by: Mohammad S Anwar
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)Method
There’s really nothing too complicated being asked here once we break it down — we have two parts to this somewhat mashed together task, and if we can solve each of them, then we can combine these together to get the desired result. In the first step we need to assemble a list of paired values from the range 1 to our input value. Once we have this, we produce the greatest common divisor for each pair and add these values together to yield our grand summed result.
We could, if we we sensible, reach for some modules to help us at each step along the way, but for now I think working in pure Perl and creating our own routines will be more informative and entertaining. We shall see.
For the first part of the task, we will compose our own pairs() function, with two loops to produce an array of arrays. If we always take the second value as incrementally larger than the first, then the resulting pairs will not repeat and be unique. Even though this is the simplest of combination problems, the number of results is still the binomial coefficient:
n! / k!(n–k)!
which for the case n = 2,
n(n-1) / 2
or for practical purposes the growth in complexity is O(n2). So things will begin to bog down as our input gets larger, but this will make an acceptable demonstration. We could use Algorithm::Combinatorics to give us a combination function tooled and tweaked in C, but two loops is a nice clear way to go about things.
In the second part of the puzzle, each unique pair is taken as a set of values for a greatest common divisor function, and we’ll establish an accumulator to gather these. The sum of the return values for the various combinations is what we are to going to output.
The Greatest Common Divisor between two numbers, or GCD, is the largest number that evenly divides both values. For numbers that share no factors this will simply be 1, as every number is evenly divisible by 1, or in the case of one number being a whole factor of the other, then the GCD is the value of that smaller number. There are a variety of ways of determining this value; the most rudimentary is to create lists of prime factors for both numbers by dividing out and determining commonalities between the sets, multiplying those to find the GCD. For example for the numbers 1050, which has factors {2,3,5,5,7}, and 1365, which reduces to the set {3,5,7,13}, the elements common to both sets are 3, one 5, and 7 — thus the GCD is 3 × 5 × 7 = 105. Working backwards, it’s easy to see 1050 ÷ 10 = 105 and (perhaps less easily seen, but look at the lists of factors) 1365 ÷ 13 = 105.
It should be clear that repeating this action over and over again is likely to take a lot of effort, and so we’ll use a different algorithm, the method invented by Euclid a few thousand years ago, instead. In this we capitalize on the fact that the GCD between two numbers will also divide the difference between these numbers. In the example above, 1365 – 1050 = 315, which is 3 × 105. Hmm. This can be intuitively visualized in that one number is 10 times the GCD, the other 13, so the difference should be the 3 missing times, which indeed it is. Substituting division for Euclid’s original multiple subtractions, we repeatedly use integer division to divide the larger value by the smaller, substituting the smaller value and the remainder for the original values and repeating the process until the remainder is 0. At this point the smaller value is the GCD. It’s a nice little algorithm and has been tweaked and improved for various cases over the years, but we will just use a simple and straightforward implementation here.
Another, faster way would be to import a proper math module like Math::GMP which provides a bgcd() “bigint”, or large integer value, version of a compiled GCD function. Yea, but we’re not going to do that. But that would, really, be the way to go here. And while we were at it, perhaps use map across the whole list of combinations, and grab sum from the core module List::Util to add them up.
Does it work? Sure thing. I took the time to wrap it up in a loop for the first couple of dozen values and plugged those into the Online Encyclopedia of Integer Sequences, and there it was: A178881 “Sum of all pairs of greater common divisors for (i,j) where i<j. “
Which is nice.
Perl Solution
Much of the practicalities of the Perl solution are covered in the method analysis above. The actual control flow is condensed into the single line:
$sum += gcd($_->@*) for pairs($input)->@*;The two routines do the heavy lifting. This whole method will bog down for larger input values, but I’ve decided not to worry too much about that. The real way to speed things up is to rewrite it in C.
use warnings;
use strict;
use feature ":5.26";
## ## ## ## ## MAIN:
my $input = shift @ARGV // 4100;
my $sum = 0 ;
$sum += gcd($_->@*) for pairs($input)->@*;
say "input $input";
say "sum $sum";
## ## ## ## ## SUBS:
sub gcd {
## Euclid's algorithm
my ($m, $n) = @_;
while ( $n != 0 ) {
$n > $m and ($m, $n) = ($n, $m);
my $r = $m - $n * ( int ($m/$n));
return $n if $r == 0;
($m, $n) = ($n, $r);
}
}
sub pairs {
## unique pairs among values 1 and $max
my ($max) = @_;
my @out;
for my $m ( 1..$max-1 ) {
for my $n ( $m+1..$max ) {
push @out, [$m, $n];
}
}
return \@out;
}
Raku Solution
In Raku things are remarkably clean, given the built-in combinations, gcd, and sum functions. The actual speed of those functions I leave as a problem to the development team. gcd seems to need some work, as my own humble efforts in Perl seem orders of magnitude faster. It’s pretty, I’ll give it that, but I find it a bit cruel to dangle such beauty in front of us only to find the results usable once the numbers get out of the hundreds. For what it’s worth, it does appear that gcd is the bottleneck here.
unit sub MAIN (Int $input where {$input > 0} = 1000) ;
my $out = (1..$input).combinations(2)
.map({[gcd] |$_})
.sum;
say "input $input";
say "sum $out";
episode two:
“Three by Three We Weave a Square”
TASK #2 ›
Magical Matrix
Submitted by: Mohammad S Anwar
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
Method
The puzzle outlined here is commonly known as a “magic square”. All the orthogonally and diagonals add to the same number, in this case 15.
It’s funny, but I never much considered this particular age-old math problem before. Not for any particular reason mind you; I’ve spent countless hours over the years on math puzzles. It’s just one of those things, you know? So walk with me and rather than research it, let’s look at things as a blank slate and see what we can find.
One thing, apparent straight off the bat, is the similarities to the sudoku puzzle a few weeks back. I mean, obviously. So the basic mechanics of guessing cells and advancing seems a reasonable way to start — guessing, using that data to constrain the possible values of the remaining cells, then picking from available choices for the next, continuing until either a contradiction is reached or the last cell is filled.
Studying the 3×3 matrix given, it’s apparent that not every cell is equal per se. The center, for example, is part of both two orthogonal and two diagonal lines, for a total of 4. The corners, on the other hand, are contained within two orthogonals and only one diagonal, for three lines, and the edges only affect two. So it stands to reason that if we are going to take a constrained tree branching approach then we should start in the center, progress to the corners, and then the edges, so our earlier choices have maximum effect.
Another consideration is the sum of each line. Once any two numbers have been placed, the third is determined by the other two and the required total. Any calculated value outside the boundaries is a contradiction.
Combining these facts, any possible configuration can be evaluated for magic behavior after choosing only three values: the center, any corner, and one of either adjacent corners to that picked. The center does not determine any other cell configuration on its own, but does constrain all 8 remaining cells surrounding it. The next, a corner (they are all equivalent so it does not matter which we pick) can be any value that is neither the center value nor a value that would require its complement across the line to be a number out-of-bounds. For example, with a center of 1, the top left cannot be 2 because the lower right would need to be 12 in order to sum to 15, which is not allowed. In this case the top left would need to be a value of 5 or more.
Once one corner is chosen, this act will determine its diagonally opposing corner. The final choice, of either adjacent corner, is any value not already determined, nor, like the corner before, a number that would require its opposite to be disallowed.
With the placement of the second corner all remaining edges are constrained to be the difference between the target value and the sum of the two placed cells. Once calculated, there will either be a contradiction found or the result will be determined to be a magic square. The contradictions will be either to require a value no longer available, or producing an invalid result across the relevant center orthogonal.
It occurred to me that because the outlying values, such as 1 or 9, are included in the least number of valid combinations to 15, all numbers in the list are not exactly weighted equally either, and perhaps reordering the numbers to emphasize the center values: (5,4,6,3,7,2,8,1,9), would maximize the odds of finding a solution quickly.
Using this method, it didn’t take me long at all to make the following square in my head, on the third try:
4 3 8 9 5 1 2 7 6
I started with 5 in the center, and 4 in a corner. This lead to the placement of 6. The pair (7,3) didn’t work out in the top right either way, but 8, and its complement 2, did. At this point the rest fell out.
So that’s nice. We know it’s sound.
Perl Solution
I’ve taken the time to heavily comment the code itself as I work through the algorithm outlined above. I wanted to examine the entire solution space so I chose not to reorder the numbers list in the end to anything optimized; in fact by using hashes to keep the number sets the lists are in unpredictable order anyways, but ultimately all patterns are tried and those that are validated are saved for output.
The actual output is 8 squares, which prove to be the same square positioned in 4 rotations and their chiral reflected counterparts. A quick look at the literature after the fact shows that this is indeed the unique solution, shown in its 8 equivalent translations.
use warnings;
use strict;
use feature ":5.26";
## ## ## ## ## MAIN:
our $target = 15;
my @output;
my %numbers = map { $_, undef } (1..9);
## place center value
for my $center (keys %numbers) {
## start possible solution with center placed
## and removed from remaining number list
my @sol_center;
$sol_center[4] = $center;
my %nums_center = %numbers;
delete $nums_center{$center};
## place top left value
for my $left (keys %nums_center) {
## new copy within loop
## for solution and remaining number list
my @sol_left = @sol_center;
my %nums_left = %nums_center;
next unless add_left($left, \@sol_left, \%nums_left);
## place top right value
## from this is can be determined whether
## the square can be comleted
for my $right (keys %nums_left) {
my $solution = add_right($right,
\@sol_left, \%nums_left );
push @output, $solution if defined $solution;
}
}
}
## reveal any squares identified
print_square($_) for @output;
## ## ## ## ## SUBS:
sub add_left {
## add single value to top left corner, triggering placement
## of value into bottom right corner
## returns 1 if successful, undef if complement outside bounds
my ($left, $sol, $nums) = @_;
$sol->[0] = $left;
delete $nums->{$left};
return undef unless fill_cell(8, 4, 0, $sol, $nums);
return 1;
}
sub add_right {
## add single value to top right corner
## this determines a list of other cells to be
my ($right, $sol, $nums) = @_;
## make a copy of the data for this solution
my @solution = $sol->@*;
my %numbers = $nums->%*;
$solution[2] = $right;
delete %numbers{$right};
## the remaining cells to be filled, in order
## the lists are the index, and the two other
## cells in the line that define it
## [cell index, line cell one, line cell two]
my @checks = ( [6,4,2],
[1,0,2],
[3,0,6],
[5,2,8],
[7,6,8] );
for my $next_cell ( @checks ) {
return undef unless fill_cell( $next_cell->@*,
\@solution, \%numbers );
}
## we really should do a check on the last remaining
## two central orthogonals before returning.
## knowing that the solution is unique, this isn't ever
## going to find anything, but we're going at this blind
## to start, to see what wefind. We leave it in for
## completeness
return undef if not check_center_lines(\@solution);
return \@solution;
}
sub fill_cell {
## given an index and two other indices,
## calculates the required value to sum to the target
my ($idx, $one, $two, $sol, $nums) = @_;
my $cell = $target - $sol->[$one] - $sol->[$two];
return undef unless exists $nums->{$cell};
$sol->[$idx] = $cell;
delete $nums->{$cell};
return 1
}
sub check_center_lines {
## validate the two orthogonals that pass through the center
my ($sol) = @_;
for ([3,4,5], [1,4,7]) {
return undef if $sol->[$_->[0]] + $sol->[$_->[1]]
+ $sol->[$_->[2]] != $target;
}
return 1;
}
sub print_square {
my $sq = shift;
say "$sq->@[0..2]";
say "$sq->@[3..5]";
say "$sq->@[6..8]";
say '';
}The analysis and method derived from it here are fairly well specific to the 3×3 square defined in the challenge, and do not immediately scale to, say, a 4×4. In that configuration, and larger versions, things obviously get much more complicated. In the end, though, cells will be defined by the simultaneous solutions to their dependent equations, giving the center and corners more weight, so to speak, in the same manner outlined above. Perhaps starting with a kernel quad and progressing to the corners would likewise prove a good strategy. It does seem as good a place as any to start.
Programming Excursions in Perl and Raku 