Arrayed Spiral with Raku and Perl
[104] Published 25. November 2020.This is my response to the Perl Weekly Challenge #088.
Challenge #088.1: Array of Product
@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
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 = 8
We are required to mulitply a lot of values together, but the numbers vary for each position
in @M. We can work around this by multipling all the numbers together initially,
and then divide that number by the current value of $N[i] to get $M[i].
#! /usr/bin/env raku
subset PositiveInt of Int where * > 0; # [1a]
unit sub MAIN (*@N where @N.elems && all(@N) ~~ PositiveInt); # [1]
my $product = [*] @N; # [2]
my @M = @N.map( { $product / $_ }); # [3]
say '(', @M.join(', '), ')'; # [4]
[1] All the parameters must be positive integers ([1a]), and there must be at least one of them.
[2] Multiply all the integers together.
[3] For each value in the input array, divide the value fom [2] with the current value, to get what we are looking for
[4] Print the values.
Running it on the examples:
$ ./array-of-product 5 2 1 4 3
(24, 60, 120, 30, 40)
$ ./array-of-product 2 1 4 3
(12, 24, 6, 8)
Looking good.
A Perl Version
This is straight forward translation of the Raku version. File: array-of-product-perl
#! /usr/bin/env perl
use strict;
use feature 'say';
use List::Util qw/reduce all/;
my @N = @ARGV;
die '@N must contain positive integers only'
unless all { $_ =~ qr/^[1-9]\d*$/ } @N; # [1]
my $product = reduce { $a * $b } @N;
my @M = map { $product / $_ } @N;
say '(', join(', ', @M), ')';
[1] The first digit in a Positive Integer cannot be zero. The rest, if any, can.
Running it gives the same result as the Raku version:
$ ./array-of-product-perl 5 2 1 4 3
(24, 60, 120, 30, 40)
$ ./array-of-product-perl 2 1 4 3
(12, 24, 6, 8)
Challenge #088.2: Spiral Matrix
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 ]
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 ]
Note the commas between the values this time (as opposed to what we have seen and done the previous weeks). This makes it somewhat harder to read (and parse) the input.
We start at the upper left corner, heading east (right). Then we go straight ahead (gobbling up values, and removing the cells from the matrix) until we reach the end of the matrix. Then we take a right hand turn, and continue straight ahead. We do this until we run out of cells.
Treating the matrix as a map, with compass directions N (North), E (East), S (South) and W (West), is inspired by the Wall Follower Algorithm presented in my Amazingly Raku - Part 3: The Wall article.
File: spiral-matrix
#! /usr/bin/env raku
# subset PositiveInt of Int where * > 0; # [1]
unit sub MAIN ($matrix where $matrix.IO.f && $matrix.IO.r); # [2]
my @matrix = $matrix.IO.lines # [3]
>>.words # [3a]
>>.map( * ~~ (/<[1..9]>\d*/) ) # [3b]
>>.grep( *.defined ) # [3c]
>>.Array; # [3d]
my $rows = @matrix.elems; # [4]
my $cols = @matrix[0].elems; # [5]
die "All rows must have the same length" unless [==] @(@matrix)>>.elems; # [6]
my $row = 0; # [6]
my $col = 0; # [6]
my $direction = "E"; # [7]
my @spiral; # [8]
say ": { @matrix[$row][$col] } Direction: $direction" if $verbose;
loop # [9]
{
@spiral.push: @matrix[$row][$col]; # [10]
@matrix[$row][$col] = Any; # [10a]
if $direction eq "E" && @matrix[$row][$col+1] { $col++; $direction = "E"; }
elsif $direction eq "E" && @matrix[$row+1][$col] { $row++; $direction = "S"; }
elsif $direction eq "S" && @matrix[$row+1][$col] { $row++; $direction = "S"; }
elsif $direction eq "S" && @matrix[$row][$col-1] { $col--; $direction = "W"; }
elsif $direction eq "W" && @matrix[$row][$col-1] { $col--; $direction = "W"; }
elsif $direction eq "W" && @matrix[$row-1][$col] { $row--; $direction = "N"; }
elsif $direction eq "N" && @matrix[$row-1][$col] { $row--; $direction = "N"; }
elsif $direction eq "N" && @matrix[$row][$col+1] { $col++; $direction = "E"; }
else # [11]
{
last; # [12]
}
say ": { @matrix[$row][$col] } Direction: $direction" if $verbose;
}
say "[ { @spiral.join(', ') } ]"; # [13]
[1] Not actually used, as a regex was easier (in [3b]).
[2] The matrix must be specified as a file.
[3] Read the matrix, row by row. Then split each row into words [3a]. Note that
words split by spaces, so that the brackets are still there - and the
commas are attached to the integer values. Then we use map to convert
each cell value to a positive integer with a regex match [3b]. This removes the
commas, and the brackets are left as undefined values. Then we remove the undefined
values with grep [3c]. And finally we coerce the rows to Arrays [3d],
as the default Sequence is read only (and we want to change the values later on).
[4] Get the number of rows,
[5] and columns. (Or rather, the number of columns in the first row.)
[6] Ensure that all the rows have the same number of columns, thus complementing [5].
[7] We start off heading East («E»).
[8] We are collecting the values here, as we go along.
[9] Off we go. Note the exit strategy in [12].
[10] Get the current cell value, and remove the cell from the matrix [10a].
[11] These 8 lines takes care of the logic. We go on in the current direction (N, E, S or W) as long as there are cells there. Then we take a right hand turn and continue in that direction.
[12] When we have run out of cells, we are done.
[13] Print the values.
Note that a cell
value of 0 would cause havoc in the if-block, as we test
the value and not for definedness. That does not matter here,
as 0 does not occur in the matrix, but we could have fixed it by
adding a trailing .defined on the condition. (E.g.
@matrix[$row][$col+1].defined.)
See
docs.raku.org/routine/defined
for more information about defined.
Running it:
$ ./spiral-matrix example1.txt
[ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]
$ ./spiral-matrix example2.txt
[ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
With verbose mode:
$ ./spiral-matrix -v example1.txt
: 1 Direction: E
: 2 Direction: E
: 3 Direction: E
: 6 Direction: S
: 9 Direction: S
: 8 Direction: W
: 7 Direction: W
: 4 Direction: N
: 5 Direction: E
[ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]
$ ./spiral-matrix -v example2.txt
: 1 Direction: E
: 2 Direction: E
: 3 Direction: E
: 4 Direction: E
: 8 Direction: S
: 12 Direction: S
: 16 Direction: S
: 15 Direction: W
: 14 Direction: W
: 13 Direction: W
: 9 Direction: N
: 5 Direction: N
: 6 Direction: E
: 7 Direction: E
: 11 Direction: S
: 10 Direction: W
[ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
Perl
I decided to do it slightly differently this time, using a real matrix and matrix operations with the Math::Matrix module.
I start by removing the top row of the matrix. Then I rotate the matrix 90 degrees counter-clockwise, and remove the top row. And so on until the matrix is empty.
The first square (A) is the initial matrix, with the spiralling pattern from the Raku solution. The next square (B) shows the result of removing the top row (marked with blue), giving the first 4 values. The next square (C) has the ramaining matrix rotated 90 degrees counter-clockwise, and with the top row removed (again marked with blue). And so on, until there is nothing left to rotate.
File: spiral-matrix-perl
#! /usr/bin/env perl
use strict;
use feature 'say';
use Math::Matrix;
use File::Slurp;
die "Specify a matrix file" unless $ARGV[0];
my @rows;
for my $line (read_file($ARGV[0], chomp => 1)) # [1]
{
$line =~ /\[ +(.*) \]/; # [1a]
my @values = split(",? +", $1); # [1b]
push(@rows, \@values); # [1c]
}
my $m = Math::Matrix->new(@rows);
my @spiral;
while ($m->nrow()) # [2]
{
my $row = $m->getrow(0); # [3]
push(@spiral, @{@{$row}[0]}); # [4]
$m = $m->delrow(0);
$m = $m->rot90(); # [5]
} # [6]
say '[ ', join(', ', @spiral), ' ]'; # [7]
[1] Read one line at a time, with File::Slurp::read-file, remove
the brackets, split the remainder of the line on spaces (possibly prefixed
with a comma), and add the list to the array.
[2] As long as there are something (i.e. at least one row) in the matrix,
[3] • Get the top row,
[4] • and add it (the values) to the result.
[5] • Remove the top row.
[6] • Rotate the matrix.
[7] Print the result.
Running it:
$ ./spiral-matrix-perl example1.txt
[ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]
$ ./spiral-matrix-perl example2.txt
[ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
And that's it.