Solving Perl Weekly Challenge 088 -- Array of Prodict vs Spiral Matrix.
作者：gugod 發佈於： ，更新於： #rakuThis article is the explalation of my solutions to the tasks from Perl Weekly Challenge 088. Somehow putting their names together reminds me of those titles of Harry Potter books.
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].
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
It appears to me that M[i] can be defined as ∏(N) / N[i], with ∏(N) being the product of all elements in N. Let's compute ∏(N) first ;
my $p = [*] @N;... and transform @N based on that value.
my @M = @N.map(-> $n { $p / $n });This solution, however, does not correctly handle the case when N[i] is 0. It throws an exception as long as there are any elements in N being 0.
It is not difficult to bypass that case though, pretty much the same as ignoring all zeros. But first of all, let's compute $q, the product of all non-zero numbers:
my $q = [*] @N.grep(-> $n { $n != 0 });As it is stated in the task that M[i] is the product of all numbers in N except for N[i], there are 3 possible cases:
- N contains no zeros
- N contains exactly 1 zero
- N contains 2 or more zeros.
When in case 1, $p is the same as $p and the old solution works.
When in case 2, M[i] is $q, while all other elements in M are zero.
When in case 3, all elements in M are zero.
Now that our problem is properly analysed, here is our solution:
sub array-of-product (@N) {
my $zeros = @N.grep(-> $n { $n == 0 }).elems;
my $q = [*] @N.grep(-> $n { $n != 0 });
my $fun;
if $zeros == 0 {
$fun = -> $n { $q / $n };
} elsif $zeros == 1 {
$fun = -> $n { $n == 0 ?? $q !! 0 };
} else {
$fun = -> $n { 0 };
}
return @N.map($fun);
}Base on each of those 3 cases, we have a $fun function which then becomes the parameter to @N.map to transform array @N one by one.
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 ]
Imagine there's a cursor walking from top-left corner (0,0), toward the direction of rightward, downward, leftward, upward, and only taking right turn when hitting the boundary. After turning right, the boundray at the back should be move "inward". The walk ends when there are nowhere to go.
Let's start by defining some constants and variables:
my $width := @M[0].elems;
my $height := @M.elems;
my @directions := [
[ 1, 0], # →
[ 0, 1], # ↓
[-1, 0], # ←
[ 0,-1], # ↑
];
my @cursor = [0,0];
my $curdir = 0;
my @boundary = [
-1, # ↑
$width, # →
$height, # ↓
-1, # ←
];
With those, we could define subroutine turn for making rightward turns and adjusting boundaries. We could also define the subroutine next-step for computing the next position if we move forward one step. For making it simple to define turn, the meanings in terms of direction of each corresponding elements in @boundray and @directions are different.
sub turn ($curdir is rw, @boundary) of Nil { # ⤵
@boundary[$curdir] += ($curdir == 0|3) ?? 1 !! -1;
$curdir = ($curdir + 1) % 4;
return;
}
sub next-step (@cursor) {
return @cursor >>+<< @directions[$curdir];
}The symbol of >>+<< is a hyper operator and looks fancy, while what it really does is to generate a list of sums of correspoing elemens frome two lists. (a[0] + b[0], a[1] + b[1], a[2] + b[2], ...)
We also need a subroutine to tell if we are hitting boundary:
sub inside-boundary(@cursor, @boundary) of Bool {
return ((@boundary[3] < @cursor[0] < @boundary[1])
and (@boundary[0] < @cursor[1] < @boundary[2]));
}The decision of making turn easier to write seems to make these array indices looks odd. Perhaps this could be rewritten with HashMap and string keys of left/right/top/bottom, for the sake of readability...
Anyhow, with thoes basic building block, let's combine:
sub spiral-matrix (@M) {
# Things don't change
my $width := @M[0].elems;
my $height := @M.elems;
my @directions := [
[ 1, 0], # →
[ 0, 1], # ↓
[-1, 0], # ←
[ 0,-1], # ↑
];
# Things change.
my @cursor = [0,0];
my $curdir = 0;
# The order of boundary is arranged in thee way to make it easier to implement turn().
my @boundary = [
-1, # ↑
$width, # →
$height, # ↓
-1, # ←
];
my sub turn ($curdir is rw, @boundary) of Nil { # ⤵
@boundary[$curdir] += ($curdir == 0|3) ?? 1 !! -1;
$curdir = ($curdir + 1) % 4;
return;
}
my sub next-step (@cursor, $curdir) {
@cursor >>+<< @directions[$curdir];
}
my sub inside-boundary(@cursor, @boundary) of Bool {
return ((@boundary[3] < @cursor[0] < @boundary[1])
and (@boundary[0] < @cursor[1] < @boundary[2]));
}
return gather {
while inside-boundary(@cursor, @boundary) {
take @M[@cursor[1]][@cursor[0]];
my @next = next-step(@cursor, $curdir);
unless inside-boundary(@next, @boundary) {
turn($curdir, @boundary);
@next = next-step(@cursor, $curdir);
}
@cursor = @next;
}
};
}For this round, those subroutines are declared with my and all put inside the body of subroutine spiral-matrix. This constraints their scope. The last core part of the solution can be described as: if taking next step in the current direction would hit the boundary,, let's take right turn first before actually stepping forward. If we still hit boundray, everything is over.