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 @arr1;
    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 = 1eval {$a *= $ARGV[$_if $_ != $jfor (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 = 1eval {$a *= $ARGV[$iif $i != $jfor $i (0..scalar @ARGV-1); print "$a "; }' 5 2 1 3 4


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 4
Or 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 $Nfor (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]
    );



(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], 610);
print_matrix([@test]);
print "test end\n";
Output:
[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
  1. 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.)
  2. 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?
  3. $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! □

link for codes: ch-1.pl , ch-2.pl

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 # 
#########

2 Comments

Why do this?

my $pre_prod = 1;   # short for "previous product"

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!

Leave a comment

About C.-Y. Fung

user-pic a beginner in programming; passionate in mathematics, distance running and gender issues; from Hong Kong. https://twitter.com/e7_87