Perl Weekly Challenge 88: Array of Products and Spiral Matrices
These are some answers to the Week 88 of the Perl Weekly Challenge organized by Mohammad S. Anwar.
Spoiler Alert: This weekly challenge deadline is due in a couple of days (November 29, 2020). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.
Task 1: Array of Products
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 = 8
Array of Products in Raku
I immediately thought about two methods to solve this problem. Although I thought the second method was probably better, let me show first the first one.
The first way to do it is to traverse the input array and, for each item, multiply all items before with all items after and store the product in the equivalent position of the result array. Here we use the reduction metaoperator with multiplication, [*], to compute the chained multiplication. And we use array slices to pick the relevant items to be multiplied. For some reason, array slice did not work properly for the first element of the array, so I computed it separately before entering the for loop.
use v6;
my @tests = [5, 2, 1, 4, 3], [2, 1, 4, 3];
for @tests -> @array {
my @result;
@result[0] = [*] @array[1..@array.end];
for 1..@array.end -> $i {
@result[$i] = ([*] @array[0..$i-1]) * [*] (@array[$i+1..@array.end]);
}
say "Input array: ", @array;
say "Result: ", @result;
}
This script produces the following output:
$ raku array-of_products.raku
Input array: [5 2 1 4 3]
Result: [24 60 120 30 40]
Input array: [2 1 4 3]
Result: [12 24 6 8]
There may be a better way to handle the special case of the first item of the list, but, rather than trying to improve it, I preferred to implement the second method. Here, the idea is to compute only once the product of all elements of the input array. Then, for each position in the array, we divide the overall product by the item in the current position. The code becomes slightly simpler, and the performance is also likely to be better, since we’re performing much less arithmetical operations overall (especially if the input array is somewhat large).
my @tests = [5, 2, 1, 4, 3], [2, 1, 4, 3];
for @tests -> @array {
my $product = [*] @array;
my @result = map { $product / $_ }, @array;
say "Input array: ", @array;
say "Result: ", @result;
}
This script produces the same result as before:
Input array: [5 2 1 4 3]
Result: [24 60 120 30 40]
Input array: [2 1 4 3]
Result: [12 24 6 8]
Array of Products in Perl
This is a port to Perl of the method used in the second Rakudo script above: we compute the product of all elements of the input array. Then, for each position in the array, we divide the overall product by the item in the current position.
use strict;
use warnings;
use feature "say";
my @tests = ([5, 2, 1, 4, 3], [2, 1, 4, 3]);
for my $array_ref (@tests) {
my $product = 1;
$product *= $_ for @$array_ref;
my @result = map $product / $_, @$array_ref;
say "Input: @$array_ref";
say "Result: @result";
}
This displays the following output:
$ perl array-of-products.pl
Input: 5 2 1 4 3
Result: 24 60 120 30 40
Input: 2 1 4 3
Result: 12 24 6 8
Task 2: Spiral Matrix
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 ]
Spiral Matrix in Raku
For this task, we’ll use a @tests array of five rectangular matrices. The print-matrix subroutine is a helper function to pretty print the input matrix. Note that, when applied to a list, the fmt method applies the formatting string to each element of the list (contrary to sprintf), so that there is no need to add a map to process each item of a matrix line. For example:
say <1 2 3 4>.fmt("%04i");
will print:
0001 0002 0003 0004
The main loop reads the values of the matrix (in accordance to the rules explained just after) and stores them into the @result array. It processes first the first matrix line (left to right); it then processes the last column, i.e. the last item of each line, from top to bottom, and deletes it at the same time; it then processes (right to left) the last line of the matrix and also deletes this line; and it processes the first column (bottom to top) of the matrix. It then assign to @matrix a version of the original matrix with all values on the four edges removed. And the loop is restarted with the new smaller matrix if it is not empty.
Note that the :delete adverb removes entirely the last item of an array, but it leaves a “hole” when applied to any other element of the array.
use v6;
my @tests =
[ [ |(0..3) ], [ |(4..7) ], [ |(8..11) ], [ |(12..15) ] ],
[ [ |(0..4) ], [ |(5..9) ], [ |(10..14) ], [ |(15..19) ] ],
[ [ |(0..5) ], [ |(6..11) ], [ |(12..17) ], [ |(18..23) ] ],
[ [ |(0..5) ], [ |(6..11) ], [ |(12..17) ] ],
[ [ |(0..2) ], [ |(4..6) ], [ |(8..10) ], [ |(12..14) ] ];
sub print-matrix (@matrix) {
say "[ {$_.fmt("% 3i")} ]" for @matrix;
say "";
}
for @tests -> @matrix {
my @result;
print-matrix @matrix;
loop {
push @result, |@matrix[0];
push @result, @matrix[$_][*-1]:delete for 1..@matrix.end;
push @result, |(reverse @matrix[@matrix.end]:delete);
last if @matrix.elems == 1;
push @result, @matrix[$_][0]:delete for reverse 1..@matrix.end;
@matrix = map { [$_[|(1..$_.end)]] }, @matrix[|(1..@matrix.end)];
# print-matrix @matrix;
last unless @matrix;
}
say @result, "\n";
}
This program displays the following output:
[ 0 1 2 3 ]
[ 4 5 6 7 ]
[ 8 9 10 11 ]
[ 12 13 14 15 ]
[0 1 2 3 7 11 15 14 13 12 8 4 5 6 10 9]
[ 0 1 2 3 4 ]
[ 5 6 7 8 9 ]
[ 10 11 12 13 14 ]
[ 15 16 17 18 19 ]
[0 1 2 3 4 9 14 19 18 17 16 15 10 5 6 7 8 13 12 11]
[ 0 1 2 3 4 5 ]
[ 6 7 8 9 10 11 ]
[ 12 13 14 15 16 17 ]
[ 18 19 20 21 22 23 ]
[0 1 2 3 4 5 11 17 23 22 21 20 19 18 12 6 7 8 9 10 16 15 14 13]
[ 0 1 2 3 4 5 ]
[ 6 7 8 9 10 11 ]
[ 12 13 14 15 16 17 ]
[0 1 2 3 4 5 11 17 16 15 14 13 12 6 7 8 9 10]
[ 0 1 2 ]
[ 4 5 6 ]
[ 8 9 10 ]
[ 12 13 14 ]
[0 1 2 6 10 14 13 12 8 4 5 9]
We can make it slightly simpler by stripping out the used matrix edges as we go, using the pop and shift methods each time we use some values, so that we don’t have to reassign the @matrix at each iteration. This also simplifies the handling of array subscripts. In the code below, the only changes are in the loop block:
use v6;
my @tests =
[ [ |(0..3) ], [ |(4..7) ], [ |(8..11) ], [ |(12..15) ] ],
[ [ |(0..4) ], [ |(5..9) ], [ |(10..14) ], [ |(15..19) ] ],
[ [ |(0..5) ], [ |(6..11) ], [ |(12..17) ], [ |(18..23) ] ],
[ [ |(0..5) ], [ |(6..11) ], [ |(12..17) ] ],
[ [ |(0..2) ], [ |(4..6) ], [ |(8..10) ], [ |(12..14) ] ];
sub print-matrix (@matrix) {
say "[ {$_.fmt("% 3i")} ]" for @matrix;
say "";
}
for @tests -> @matrix {
my @result;
print-matrix @matrix;
loop {
push @result, |@matrix.shift;
push @result, @matrix[$_].pop for 0..@matrix.end;
last unless @matrix.elems;
push @result, |(reverse @matrix.pop);
push @result, @matrix[$_].shift for reverse 0..@matrix.end;
last unless @matrix;
}
say @result, "\n";
}
This produces the same output as before:
[ 0 1 2 3 ]
[ 4 5 6 7 ]
[ 8 9 10 11 ]
[ 12 13 14 15 ]
[0 1 2 3 7 11 15 14 13 12 8 4 5 6 10 9]
[ 0 1 2 3 4 ]
[ 5 6 7 8 9 ]
[ 10 11 12 13 14 ]
[ 15 16 17 18 19 ]
[0 1 2 3 4 9 14 19 18 17 16 15 10 5 6 7 8 13 12 11]
[ 0 1 2 3 4 5 ]
[ 6 7 8 9 10 11 ]
[ 12 13 14 15 16 17 ]
[ 18 19 20 21 22 23 ]
[0 1 2 3 4 5 11 17 23 22 21 20 19 18 12 6 7 8 9 10 16 15 14 13]
[ 0 1 2 3 4 5 ]
[ 6 7 8 9 10 11 ]
[ 12 13 14 15 16 17 ]
[0 1 2 3 4 5 11 17 16 15 14 13 12 6 7 8 9 10]
[ 0 1 2 ]
[ 4 5 6 ]
[ 8 9 10 ]
[ 12 13 14 ]
[0 1 2 6 10 14 13 12 8 4 5 9]
Spiral Matrix in Perl
For this task, we’ll use a @tests array of five rectangular matrices. The print_matrix subroutine is a helper function to pretty print the input matrix.
The main while loop reads the values of the matrix (in accordance to the rules explained just after) and stores them into the @result array. It processes first the first matrix line (left to right) and removes it from the matrix; it then processes the last column, i.e. the last item of each line, from top to bottom, and deletes it at the same time; it then processes (right to left) the last line of the matrix and also deletes this line; and finally it processes the first column (bottom to top) of the matrix and removes it.
After one iteration, the original matrix is stripped of all its edge items. And the loop is restarted with the new smaller matrix if it is not empty.
use strict;
use warnings;
use feature "say";
use Data::Dumper;
my @tests = ( [ [ 0..3 ], [ (4..7) ], [ (8..11) ], [ (12..15) ] ],
[ [ 0..4 ], [ (5..9) ], [ (10..14) ], [ (15..19) ] ],
[ [ 0..5 ], [ (6..11) ], [ (12..17) ], [ (18..23) ] ],
[ [ 0..5 ], [ (6..11) ], [ (12..17) ] ],
[ [ 0..2 ], [ (4..6) ], [ (8..10) ], [ (12..14) ] ]
);
# @tests = ( [ [ 0..3 ], [ (4..7) ], [ (8..11) ], [ (12..15) ] ] );
sub print_matrix {
my @matrix = @{$_[0]};
say "";
say "[ ", (map { sprintf "% 3i", $_ } @$_), " ]" for @matrix;
say "";
}
for my $m_ref (@tests) {
print_matrix($m_ref);
my @result;
my @matrix = @$m_ref;
while (1) {
push @result, @{shift @matrix};
last if scalar @matrix == 0;
push @result, pop @{$matrix[$_]} for 0..$#matrix;
push @result, reverse @{pop @matrix};
push @result, shift @{$matrix[$_]} for reverse 0..$#matrix;
last if @matrix == 0;
}
say join " ", @result;
}
This displays the following output:
[ 0 1 2 3 ]
[ 4 5 6 7 ]
[ 8 9 10 11 ]
[ 12 13 14 15 ]
0 1 2 3 7 11 15 14 13 12 8 4 5 6 10 9
[ 0 1 2 3 4 ]
[ 5 6 7 8 9 ]
[ 10 11 12 13 14 ]
[ 15 16 17 18 19 ]
0 1 2 3 4 9 14 19 18 17 16 15 10 5 6 7 8 13 12 11
[ 0 1 2 3 4 5 ]
[ 6 7 8 9 10 11 ]
[ 12 13 14 15 16 17 ]
[ 18 19 20 21 22 23 ]
0 1 2 3 4 5 11 17 23 22 21 20 19 18 12 6 7 8 9 10 16 15 14 13
[ 0 1 2 3 4 5 ]
[ 6 7 8 9 10 11 ]
[ 12 13 14 15 16 17 ]
0 1 2 3 4 5 11 17 16 15 14 13 12 6 7 8 9 10
[ 0 1 2 ]
[ 4 5 6 ]
[ 8 9 10 ]
[ 12 13 14 ]
0 1 2 6 10 14 13 12 8 4 5 9
Perl Weekly Challenge in Scala
As I mentioned elsewhere, what I like in Scala is the ability to combine the object-oriented and functional programming paradigms, like Raku and to a lesser degree Perl. Please note that I am a beginner in Scala, don’t look here for idiomatic Scala or for good practices.
Array of Products in Perl
Just like our second solution in Raku and our Perl solution, the idea is to compute only once the product of all elements of the input array. Then, for each position in the array, we divide the overall product by the item in the current position.
object ArrayOfProduct extends App {
val in = Array(5, 2, 1, 4, 3)
var product = 1;
for (item <- in) {
product *= item;
}
val result = in.map(product / _)
println(result.mkString(" "));
}
Output:
24 60 120 30 40
Spiral Matrix in Scala
Here, I’m essentially porting my Perl solution to Scala. It would probably be better (well, at least, more in the spirit of Scala) to go toward a more functional programming solution, but, for the time being, I have enough trouble fighting with the language syntax, I don’t want to add other difficulies. But I promise that I’ll soon try to make Scala programs which are more in the spirit of the language. I need to complete my reading of a couple of Scala books before I can really do that.
import Array._
import scala.language.postfixOps
object spiralMatrix extends App {
val mat = ofDim[Int](4, 6)
var k = 1
// Populate the input matrix
for (i <- 0 to mat.length - 1) {
for (j <- 0 to mat(0).length - 1) {
mat(i)(j) = k;
k += 1
}
}
println()
printMatrix(mat)
println(unrollMatrix(mat).mkString(" "))
def printMatrix(mat: Array[Array[Int]]): Unit = {
for (i <- 0 to mat.length - 1) {
for (j <- 0 to mat(0).length - 1) {
print(f"${mat(i)(j)}%3d");
}
println()
}
println(" ")
}
def unrollMatrix(matrix: Array[Array[Int]]): Array[Int] = {
var mat = matrix
var result = Array.empty[Int]
var continue = true
while (continue) {
result = result ++ mat(0)
mat = mat.drop(1)
if (mat.isEmpty) {
return result
}
for (i <- 0 to mat.length - 1) {
result = result :+ mat(i).last
mat(i) = mat(i).dropRight(1)
}
var i = mat.length - 1
result = result ++ mat(mat.length - 1).reverse
mat = mat.dropRight(1)
i = mat.length - 1
for (j <- (0 to i).reverse) {
result = result :+ mat(j)(0)
mat(j) = mat(j).drop(1)
}
if (mat.isEmpty) {
return result
}
}
return result
}
}
This program displays the following output:
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
1 2 3 4 5 6 12 18 24 23 22 21 20 19 13 7 8 9 10 11 17 16 15 14
Wrapping up
The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, December 6, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.
I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.
Update: added Scala solutions on Dec. 20, 2020.)