CY's Take on PWC#088
If you want to challenge yourself on programming, especially on Perl and/or Raku, go to https://perlweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email).
This blogpost is not in shortage of unanswered questions...
Task 1 Array of Product
sub myproduct {
my @arr = @_;
my @ans;
my $pre_prod = 1; # short for "previous product"
push @arr, 1;
for my $i (0..$#arr-1) {
my $entry = $pre_prod;
$entry *= $arr[$_] for ($i+1..$#arr);
$pre_prod *= $arr[$i];
push @ans, $entry;
}
return \@ans;
}
my @arr = @_;
my @ans;
my $pre_prod = 1; # short for "previous product"
push @arr, 1;
for my $i (0..$#arr-1) {
my $entry = $pre_prod;
$entry *= $arr[$_] for ($i+1..$#arr);
$pre_prod *= $arr[$i];
push @ans, $entry;
}
return \@ans;
}
The above, I designed, is a prototype for multiplication (and division, if possible) when it is expensive to do mulitplication,
such as matrices. Since I don't know much about
those algorithmic knowledge, just leave the codes here for personal future digestion.
---
What I have submitted is an one-liner:
perl -e '
for $j (0..scalar @ARGV-1) {$a = 1; eval {$a *= $ARGV[$_] if $_ != $j} for (0..scalar @ARGV-1); print "$a "; }' 5 2 1 3 4
I get another item for "investigation" here. Why doesn't the following line work?
perl -e '
for $j (0..scalar @ARGV-1) {$a = 1; eval {$a *= $ARGV[$i] if $i != $j} for $i (0..scalar @ARGV-1); print "$a "; }' 5 2 1 3 4
Code inserted:
Output:
Task 2 Spiral Matrix
the Testing
This is time for Test::Deep and Test::More again:
cmp_deeply(
flat([[ 1, 2, 3],
[ 4, 5, 6,],
[ 7, 8, 9, ]]),
[ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]
, "Example 1");
cmp_deeply(
flat([[ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ],
[ 13, 14, 15, 16 ]]),
[ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
, "Example 2");
cmp_deeply(
flat([[ 1, 2, 3],
[ 4, 5, 6,]]),
[ 1, 2, 3, 6, 5, 4 ]
, "small test case");
cmp_deeply(
flat([
[ 2, 3, 5, 7],
[11,13,17,19],
[23,29,31,37],
[41,43,47,53],
[59,61,67,71]])
, [2, 3, 5, 7, 19, 37, 53, 71, 67, 61, 59,
41, 23, 11, 13, 17, 31, 47, 43, 29]
, "prime numbers 5 x 4");
$ perl ch-2.pl 1..4 ok 1 - Example 1 ok 2 - Example 2 ok 3 - small test case ok 4 - prime numbers 5 x 4Or customize a test:
$ perl ch-2.pl 3 5 A B C D E F G H I J K L M N [A, B, C, D, E] [F, G, H, I, J] [K, L, M, N, O] A, B, C, D, E, J, O, N, M, L, K, F, G, H, I
the codes
Honestly I did not plan much on the task. (I) I created a "helper matrix" (@helper_mat)
to record which terms on the original matrix is traversed: traversed,
1; not yet traversed, 0. (II) I went through the outermost terms -- the
four sides -- of the matrix by counting off one by one. (III) I made use
of a boolean variable $success_click to tackle the change of direction.
sub flat {
my @ans;
my @mat = @{$_[0]};
my $M = scalar @mat;
my $N = scalar @{$mat[0]};
# (I) initialize of the helper matrix
my @helper_mat;
push @helper_mat, [("0") x $N] for (0..$M-1);
my @row_dir = ( 0, +1, 0, -1 );
my @col_dir = ( +1, 0, -1, 0 );
my ($r, $c) = ( 0 , 0 );
push @ans, ${$mat[$r]}[$c];
${$helper_mat[$r]}[$c] = 1;
# end (I)
# (II): preparation of clockwise traverse of the outermost part of the matrix
my @numbering = (
[1..$N-1],
[$N..$N+$M-2],
[$N+$M-1..$N+$M+$N-3],
[$N+$M+$N-2..($M-1)*2+($N-1)*2-1]
);
(II): traverse the outermost matrix terms
for my $q (0..3) {
for (@{$numbering[$q]}) {
$r += $row_dir[$q];
$c += $col_dir[$q];
push @ans, ${$mat[$r]}[$c];
${$helper_mat[$r]}[$c] = 1;
}
}
# end (II)
my $time_now = 3;
my $success_click = undef; #(III)
my $count = ($M-1)*2+($N-1)*2;
while ($count < $M*$N) {
if ($success_click) {
$r += $row_dir[$time_now];
$c += $col_dir[$time_now];
if (${$helper_mat[$r]}[$c] == 0) {
push @ans, ${$mat[$r]}[$c];
${$helper_mat[$r]}[$c] = 1;
$success_click = 1;
$count++;
} else
{
$success_click = undef; #(III)
$r -= $row_dir[$time_now];
$c -= $col_dir[$time_now];
}
} else
{
$time_now = ($time_now+1) % 4;
$success_click = 1; #(III)
}
}
return \@ans;
}
my @ans;
my @mat = @{$_[0]};
my $M = scalar @mat;
my $N = scalar @{$mat[0]};
# (I) initialize of the helper matrix
my @helper_mat;
push @helper_mat, [("0") x $N] for (0..$M-1);
my @row_dir = ( 0, +1, 0, -1 );
my @col_dir = ( +1, 0, -1, 0 );
my ($r, $c) = ( 0 , 0 );
push @ans, ${$mat[$r]}[$c];
${$helper_mat[$r]}[$c] = 1;
# end (I)
# (II): preparation of clockwise traverse of the outermost part of the matrix
my @numbering = (
[1..$N-1],
[$N..$N+$M-2],
[$N+$M-1..$N+$M+$N-3],
[$N+$M+$N-2..($M-1)*2+($N-1)*2-1]
);
(II): traverse the outermost matrix terms
for my $q (0..3) {
for (@{$numbering[$q]}) {
$r += $row_dir[$q];
$c += $col_dir[$q];
push @ans, ${$mat[$r]}[$c];
${$helper_mat[$r]}[$c] = 1;
}
}
# end (II)
my $time_now = 3;
my $success_click = undef; #(III)
my $count = ($M-1)*2+($N-1)*2;
while ($count < $M*$N) {
if ($success_click) {
$r += $row_dir[$time_now];
$c += $col_dir[$time_now];
if (${$helper_mat[$r]}[$c] == 0) {
push @ans, ${$mat[$r]}[$c];
${$helper_mat[$r]}[$c] = 1;
$success_click = 1;
$count++;
} else
{
$success_click = undef; #(III)
$r -= $row_dir[$time_now];
$c -= $col_dir[$time_now];
}
} else
{
$time_now = ($time_now+1) % 4;
$success_click = 1; #(III)
}
}
return \@ans;
}
Extras
Here I am going to describe two extra functionalities I added:
(A) I find that addition or modification of a few lines can create anticlockwise traverse:
@row_dir = map {$_ = -$_} (reverse @row_dir);
@col_dir = map {$_ = -$_} (reverse @col_dir);
@numbering = (
[1..$M-1],
[$M..$N+$M-2],
[$N+$M-1..$N+$M+$M-3],
[$N+$M+$M-2..($M-1)*2+($N-1)*2-1]
);
@col_dir = map {$_ = -$_} (reverse @col_dir);
@numbering = (
[1..$M-1],
[$M..$N+$M-2],
[$N+$M-1..$N+$M+$M-3],
[$N+$M+$M-2..($M-1)*2+($N-1)*2-1]
);
(B) An inverse subroutine &matrixize for the original task: given parameters m, n, put a list of m x n integers as a m x n spiral matrix.
Code inserted:
my @test = matrixize([1..60], 6, 10);
print_matrix([@test]);
print "test end\n";
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [28, 29, 30, 31, 32, 33, 34, 35, 36, 11] [27, 48, 49, 50, 51, 52, 53, 54, 37, 12] [26, 47, 60, 59, 58, 57, 56, 55, 38, 13] [25, 46, 45, 44, 43, 42, 41, 40, 39, 14] [24, 23, 22, 21, 20, 19, 18, 17, 16, 15] test end
The codes for this subroutine (&matrixize) largely reuse that in &flat.
Dissatifaction
- As said, can one make a more maintainable and concise version of &matrixize and &flat? (A bit more thought: the current &matrixize has only clockwise version.)
- I could set every initial term as 0, 'z', '.' or undef, etc. , hence skipped @helper_mat with little amount of typing. Is there a case which a @helper_mat is really need?
- $success changes once or none for each occupant of the matrix (a note for more preciseness: except those of the "perimeter" of the matrix). Are there any cases which a $success is need to change twice? (Or change with respect to a task with more subtlies?)
For the latter two questions, I am thinking whether irregular 2D boards can make full use of @helper_mat and $success. But not every irregular 2D polyomino can have a spiral path traversing each grid...
...
...
...
Do tell or correct me, if you have oppositions, want to discuss or give me advice!
Stay alert and healthy! □
Irregular boards: sample input 1: ######### # * * x # # * * * # # * * * # # * * x # ######### sample output 1: ######### # 0 1 x # # 9 2 3 # # 8 5 4 # # 7 6 x # ######### sample input 2: ######### # * * x # # * * * # # * * * # # x * * # ######### sample output 2: ######### # 0 1 x # # 9 2 3 # # 8 7 4 # # x 6 5 # ######### sample input 3: ######### # * * * # # * * * # # x * * # # x * * # ######### sample output 3: ######### # 0 1 2 # # 9 8 3 # # x 7 4 # # x 6 5 # #########
This blog is inactive and replaced by https://e7-87-83.github.io/coding/blog.html ; but I post highly Perl-related posts here.
Why do this?
Why not just call the variable
$previous_product? Sure, it's a little longer, but it's not that bad, and you'd actually make the code shorter overall because you could get rid of that comment!Toby, thank you for the attention to the details and advice.