Wherein we learn to look at some things by the holes they leave behind and others by the long tendrils they leave in their wake
THE WEEKLY CHALLENGE – PERL & RAKU #88
Chapter One
The Product of the Absence
TASK #1
Array of Product
Submitted by: Mohammad S Anwar
You are given an array of positive integers @N.
Write a script to return an array @M where $M[i] is the product of all elements of @N except the index $N[i].
Example 1:
Input:
@N = (5, 2, 1, 4, 3)
Output:
@M = (24, 60, 120, 30, 40)
$M[0] = 2 x 1 x 4 x 3 = 24
$M[1] = 5 x 1 x 4 x 3 = 60
$M[2] = 5 x 2 x 4 x 3 = 120
$M[3] = 5 x 2 x 1 x 3 = 30
$M[4] = 5 x 2 x 1 x 4 = 40
Example 2:
Input:
@N = (2, 1, 4, 3)
Output:
@M = (12, 24, 6, 8)
$M[0] = 1 x 4 x 3 = 12
$M[1] = 2 x 4 x 3 = 24
$M[2] = 2 x 1 x 3 = 6
$M[3] = 2 x 1 x 4 = 8Method
Selectively taking the product from various combinations of array elements sounds like a complex job, but a little analysis belies that first impression. Instead of working forwards, isolating out only those values we wish to multiply, alternately we can invert the process: first we multiply everything together, then, as we iterate across the individual elements we can remove that multiplier by dividing it out. The remaining product will be that of all the elements except the selected, as requested.
Perl Solution
In Perl, the action can be delivered in two steps. First we establish an accumulator, $product, and loop through the array values, progressively multiplying the total. Then a function can be applied using map across the input array, dividing out each element in turn and producing the output array.
Easy-peasy. Sometimes it’s better to look where you want to end up with and plot the way backwards, rather than the other way around.1
1 As a side note, this is all well and good in the reversible closed world of math, but outside, in Real Life™ , starting from a decided conclusion and then looking for evidence to support that position is what we call ‘motivated reasoning‘ and I have to step in and decry against it. There’s far, far too much of it in the world. Learn to see it and suddenly it’s everywhere you look. So really, take the time and learn to recognize it and please, please don’t do that.
my @input = @ARGV;
@ARGV == 0 and @input = (5, 2, 1, 4, 3);
my $product = 1;
$product *= $_ for @input;
my @output = map { $product / $_ } @input;
say "@input";
say "@output";
Raku Solution
In Raku, things are even more concise. We can use a multiplicative reduction metaoperator to quickly get our total product, and again a simple mapping generates the output array values. I think the functional metaoperators in Raku really transcend the Perl motto “making easy things easy and hard things possible” and take things to the next level, making hard things easy. I just love applying functions over data structures, treating the data as a whole rather than a composite of parts. It’s so… clean.
unit sub MAIN (*@input) ;
@input.elems == 0 and @input = 5, 2, 1, 4, 3;
my $product = [*] @input;
my @output = @input.map: {$product/$_};
say @input;
say @output;
Chapter Two
“Spiralize the Pain Away”
TASK #2
Spiral Matrix
Submitted by: Mohammad S Anwar
You are given m x n matrix of positive integers.
Write a script to print spiral matrix as list.
Example 1:
Input:
[ 1, 2, 3 ]
[ 4, 5, 6 ]
[ 7, 8, 9 ]
Ouput:
[ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]
Example 2:
Input:
[ 1, 2, 3, 4 ]
[ 5, 6, 7, 8 ]
[ 9, 10, 11, 12 ]
[ 13, 14, 15, 16 ]
Output:
[ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]Method
Again, on first look I considered the idea of abstracting a literal spiral to be a daunting task. After all, a literal spiral is a contiguous line changing its radius in polar space and a multidimensional array, composed of rows and columns, has none of that. Well, not easily at least. I do wonder whether the PDL can handle this request, but have to say that’s a little outside my wheelhouse. I’ll inquire and if I have something to add I’ll get back to you.
In any case, the first thing to do is put the name ‘spiral’ out of the picture and just look and identify what is actually happening, so we can then reproduce the effect desired, whatever we choose to call it. When daunted by words, let’s use different words and see what remains.
Our action here is to move left to right across the top of the matrix, then top to bottom down the right side. Continuing, we proceed right to left across the bottom row, then bottom to top up the left side. After this circumscribing we end up where we started, or really right next to where we started because we don’t wish to repeat ourselves. What we’ve really done is drawn a circle, leaving inside an untouched matrix one smaller in each dimension. To extend the process, we just need to complete the same motion, starting from the position adjacent to our endpoint, on this inner matrix, continuing until there are no more unwalked cells ahead of us.
So a complex process is reduced to an act of encircling, repeated, constraining the perimeter by one cell in each direction on every pass. It stands to reason abstracting this motion, and attaching a counter to produce an offset, should produce the result we were looking for.
With no need for polar coordinates or continuous equations either. Discrete math is back on the menu. Cool.
Perl Solution
The challenge here can be summarized into three parts:
- abstracting the circular motion, then
- reducing that motion stepwise, and
- recognizing when we need to stop.
To accomplish this we write a routine that will walk around the circumference in a clockwise fashion. Clockwise, otherwise known as ‘deasil’, describes that apparent direction of the Sun across the sky in the northern hemisphere. Which in turn is why clocks move in that particular choice of angular direction, if you’re the sort to ever wonder about such things. Which, obviously, I am.2
Anyways, back to the task at hand, there are four actions described to perform the circumscription. Let’s try one: moving across the top. That’s easy, it’s the row itself. If we’re planning ahead to include an offset it’s just an array slice of the row. That’s it; once grabbed it goes straight to the output array. Hmmm. This might be easier than we thought.
On the subject of that offset, let’s think that part through before we get too far along. Rather than a spiral, this action of circling is better conceived as a set of Dantesque concentric rings. Assuming we can construct a suitable progression along the four sides, we need to loop through these four steps, shortening the span of elements registered on every pass. We’ll institute a counter and build our offset off of that, starting from 0 (no offset) and incrementing every time we complete a loop. We will use this counter to count the circles as we descend and adjust our start and end points accordingly, moving towards the center of each span as we move towards the center of the matrix.
Traversing down the right side, what we’ll do is span the inside of the column between the top and bottom rows, so we need to move our start and end points an additional increment towards the center. The reasoning here will become clear in a moment. If there’s nothing left to snatch so be it — if the width is greater than the height this will happen. As we’re grabbing the last (offset) element from successive rows, we need to construct a proper loop for this action, but it’s not complex or anything. We just grab a fixed, calculated index over a span of rows.
Next the bottom. For this we reverse the same slice that we made along the top, now along the lowermost offset row. This is why we chose to pick the whole row to start, as this selection of indices is symmetrical when reversed, which is also be true of the two inset sides. As expected the return up the left hand side is done with a reversed list of indices for the rows.
Astute observers will have noticed I made no mention of escaping this Comedic descent. In fact, as space is finite there will always come a time when there are no more untrodden souls cells to gather. What we will do is loop infinitely until this time, inexorably, comes.
At first it wasn’t super obvious to me how a given looping would cease. As we remove an element from each end of a given span on each iteration, it seemed clear that determining whether there were any cells left to traverse in a given step would have something to do with the size of some matrix dimension over 2. In fact, after mucking about I realized it was pretty straightforward: generalized, it was the array dimension, sometimes rows, sometimes columns, divided by two with one of the pair of ceiling and floor functions applied to the result. This would alternately produce an integer index to one side of the midpoint or the other. With the use of the POSIX ceil and floor functions, and the numbers $rows and $cols (being what you’d expect), the four variations to the expression
return $out if $rank > ceil( $rows / 2 - 1);prove to be exactly what we’re looking for. The rank is the current circle, and the expression in its various incarnations ratchets the result accordingly, returning the output array reference when the matrix is consumed.
There are basically four cases for an input matrix, which determine the last leg of the encircling to be evaluated. Either the width will exceed the height, or vice versa (or they are equal and it just works out). In any case one dimension will run out before the other, and if that dimension is odd-sized the first evaluated span will be the last, and if even-sized it will be the second. Confused? Don’t be. Imagine a three high matrix with a large width. We travel once across the top, down and once across the bottom, up and then one last time across the top, ending the spiral. See? If the dimension was four instead of three there would be an additional span across the bottom before finishing. It’s ultimately quite simple and of course works the same for the sides. For completeness’ sake the asymmetry we introduced where the top and bottom cap the sides, extending the whole width with the sides inset, is what resolves the case where the matrix is square; it this case the last leg will either be a top or bottom, so we still only have four variations. These correspond directly to the four exit cases from the loop.
One last thing, is I feel I need to explain the curious bareword construction
while (-spiraling) {
...
}This is me being clever and is another way of writing while (1) { ... } that gives an opportunity to add commentary about what’s actually being done. It works by virtue that the unitary negation operator looks at whatever follows it as a number and immediately acts on it, whether it actually is a number or not; this very strong bonding slips in and quietly numifies the string before the complier can choke on it. Once it becomes a number it’s no longer a bareword to the interpreter. As whatever number we’ve created will not be 0, the expression is logically true and the loop continues. It’s a neat little trick and provides an opportunity to label your loop for free, so to speak. Is it canon? Um, no. Is it safe? Yes. Ok, pretty sure. Constructing negative numbers is a very basic operation to parsing and needs to be buried primordially deep to do its magic. I don’t see that changing. I’ll be sure to update should I find out otherwise.
2 In fact I believe the original question was: “What is the opposite direction of widdershins?” Widdershins, of course, being an extremely colorful word meaning counter- or anti-clockwise. It seemed “widdershins” had no connection to clocks, and there being two available angular movements, left-hand or right-hand leading, it stood to reason there should be a similar complement from whatever construction that word was based on. I mean, “widdershins” is just an objectively interesting word, and this question demanded an answer. It turns out it comes to English from Scotland, in turn from the middle German “against the way” combined with the dual meaning that in Scots Gaelic “sin” means “sun”. That’s a singularly nice poetic resonance for you. No wonder it stuck. “Deasil” is Gaelic as well, it coming from the Latin root of “dexter”, meaning right-handed, or skillful, as in “dexterous”. And yes, these days those terms are most commonly associated with witchcraft. So there’s that. One thing about witches: they’ve got character in spades.
use warnings;
use strict;
use feature ":5.26";
use POSIX qw( ceil floor );
## ## ## ## ## MAIN:
my $mat;
$mat = [ [1,2,3,4], [5,6,7,8], [9,10,11,12] ];
## we need to check some alternate and degenerate cases
## to make sure they work.
## spoiler: they do
# $mat = [ [1,2,3], [4,5,6], [7,8,9], [10,11,12], [13,14,15] ];
# $mat = [ [1], [2], [3], [4] ];
# $mat = [ [1,2,3,4] ];
# $mat = [
# [ 1, 2, 3, 4, 5, 6],
# [ 7, 8, 9,10,11,12],
# [13,14,15,16,17,18],
# [19,20,21,22,23,24],
# [25,26,27,28,29,30]
# ];
my @out = spiralize($mat)->@*;
say "@out";
## ## ## ## ## SUBS:
sub spiralize {
my ($mat) = @_;
my $cols = $mat->[0]->@*;
my $rows = $mat->@*;
my $rank = 0; ## loop count of spiral, 0-based
my $out = [];
while (-spiraling) {
## upper - left to right
return $out if $rank > ceil( $rows / 2 - 1);
push $out->@*, $mat->[$rank]->@[$rank..$cols-$rank-1];
## right - top to bottom
return $out if $rank > ceil( $cols / 2 - 1);
for my $row ( $rank+1..$rows-$rank-2 ) {
push $out->@*, $mat->[$row][$cols-$rank-1];
}
## lower - right to left
return $out if $rank > floor( $rows / 2 - 1);
push $out->@*, reverse
$mat->[$rows-$rank-1]->@[$rank..$cols-$rank-1] ;
## left - bottom to top
return $out if $rank > floor( $cols / 2 - 1);
for my $row ( reverse $rank+1..$rows-$rank-2 ) {
push $out->@*, $mat->[$row][$rank];
}
$rank++
}
}
Programming Excursions in Perl and Raku 