I’ve been doing the Perl Weekly
Challenges. The
latest
involved multiplications and spirals. (Note that this is open until 29
November 2020.)
TASK #1 › Array of Product
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]
.
In other words, given [a,b,c]
, return [b*c,a*c,a*b]
.
There are two obvious ways to do it. The naïve approach would be to
build each subset of the list, then take the product: so for each of
the n
list members do n-2
multiplications, a total of n²-2n
. The
other would be to multiply everything together (n-1
multiplications), and then divide the product by each element in turn
(n
divisions). Divisions are more computationally expensive than
multiplications, of course, and the product will be slightly larger,
but it's still O(n) rather than O(n²).
Anyway, the naïve approach (using the product
function from
List::Util
):
sub aop {
my $ns=shift;
my @o;
foreach my $i (0..$#{$ns}) {
push @o,product(map {$ns->[$_]} grep {$_ != $i} (0..$#{$ns}));
}
return \@o;
}
and the better one that I ended up using:
sub aop {
my $ns=shift;
my $p=product(@{$ns});
return [map {$p/$_} @{$ns}];
}
Profiling showed that on a 20-element list the naïve approach took
about ten times as long. One restriction is that the product has to
fit in a standard integer (I didn't bother with BigInt
or
equivalents).
The other languages I'm using have reduce
-type functions, a compact
way of combining list members with a specific function. The syntax
varies a bit from one language to another. Raku:
sub aop(@ns) {
my $p=@ns.reduce: &infix:<*>;
return (map {$p div $_}, @ns);
}
Python:
def aop(ns):
p=reduce(operator.mul,ns)
return [p // i for i in ns]
Ruby:
def aop(*ns)
p=ns.reduce(:*)
return ns.map {|x| p.div(x)}
end
Rust:
fn aop(ns: Vec<i32>) -> Vec<i32> {
let p=ns.iter().fold(1,|sum, item| sum * item);
return ns.iter().map(|i| p/i).collect()
}
TASK #2 › Spiral Matrix
You are given m × n
matrix of positive integers.
Write a script to print spiral matrix as list.
The approach I took on this was a path traversal. Start off by going
along one edge, logging each cell value; whenever there's no cell
ahead (i.e. an edge), or the cell ahead has already been visited, turn
right.
I'll use the Raku version to demonstrate; they all look roughly the same.
sub sm(@m) {
Establish x/y sizes
my $mx=@m.elems;
my $my=@m[0].elems;
Push the first entry into the output list.
my @o=(@m[0][0]);
Construct the "visited" matrix, initially 0
throughout.
my @v;
for 1..$mx {
push @v,[(0) xx $my];
}
Establish the direction array and initialise x, y and direction.
my @dir=(
[0,1],
[1,0],
[0,-1],
[-1,0],
);
my ($x,$y,$d)=(0,0,0);
We don't need an "exit if no un-visited adjacent cells" test, because
we know how many cells are to be visited.
for 2..$mx*$my {
Mark the current cell as visited
@v[$x][$y]=1;
Generate the neighbouring cell coordinates. If they're out of bounds,
or they've been visited, turn right and try again.
my ($nx,$ny);
while (1) {
($nx,$ny)=($x+@dir[$d][0],$y+@dir[$d][1]);
if ($nx < 0 || $nx >= $mx || $ny < 0 || $ny >= $my || @v[$nx][$ny]==1) {
$d++;
$d%=4;
} else {
last;
}
}
We have valid coordinates, so stick the new cell's value on the output.
($x,$y)=($nx,$ny);
push @o,@m[$x][$y];
}
return @o.List;
}
The other languages worked pretty much the same way. Something went a
bit strange with Rust, and I had to sprinkle types and type
conversions all over everything; I suspect this is because of the the
possibility that a value I'll want to use for a subscript will at some
point be negative (even if I explicitly test for that first).
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.