解 Perl Weekly Challenge 088 -- 陣列乘積與矩陣之螺旋

作者：gugod 發佈於：2020/11/24 ，更新於：2020/11/29 #raku

本文說明 Perl Weekly Challenge 088 兩題目的解。這兩題目名稱組合起來之後怎麼有種哈利波特書名感？

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

看來 M[i] 可以簡單地定義為 ∏(N) / N[i] -- 其中 ∏(N) 為陣列 N 所有內容之乘積（∏ 為希臘字母 π 的大寫）。也就是說，只要先算出 ∏(N):

my $p = [*] @N;

再以 map 將 @N 逐一轉換就可以求出 @M

my @M = @N.map(-> $n { $p / $n });

不過，這個解法無法處理 N[i] 為 0 的狀況。只要 N 中某一個元素為 0，在計算 M 的過程中，就會出錯。

但是要繞過這個狀況也不困難。只要忽略所有的 0 就可以了。首先，先計算出所有非零數字的乘積 $q

my $q = [*] @N.grep(-> $n { $n != 0 });

依題目原意，M[i] 為 N[i] 以外所有數字的乘積。那，可以拆分成為三種狀況：

N 裡面沒有 0
N 裡面只有一個 0，其所在位置為 i
N 裡面有兩個以上的 0

如果是狀況 1，那 $q 與 $p 會相等，舊解法管用。

如果是狀況 2，那 M[i] 為 $q，而 M 中其他元素全為 0。

如果是狀況 3，那 M 中所有元素皆為 0。

題目分析完畢之後，完整解也就隨之出現了：

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);
}

這裡的作法是依照三種情況，定義出不同的 $fun 函式，而此 $fun 函式則是作為 @N.map 的參數，將 @N 之中的元素一一轉換。

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 ]

這有點像是有個游標在二維空間中自左上角 (0,0) 依右、下、左、上這固定次序進行直線移動。在碰到邊界時變換方向(右轉)，並在右轉之後將剛剛走完的那一側之邊界向內縮。如果一步都不能走了，就結束。

首先定一些會用到的常數與變數：


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,      # ←
];

然後先定義兩個函式： turn 與 next-step 。一是為了進行右轉，另一是計算下一步的位置。每右轉一次後，正後方那個方向的邊界就可以內縮。為此，@boundary 內容對應到的方向與 @direction 略有不同。

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];
}

>>+<< 這個超算符符號看來很炫炮，但其實就只是把左右兩串東西一對一地相加起來，再傳回一串新的東西。(a[0] + b[0], a[1] + b[1], a[2] + b[2], ...)

也要有個函式能判斷某座標有無出界：

sub inside-boundary(@cursor, @boundary) of Bool {
    return ((@boundary[3] < @cursor[0] < @boundary[1])
            and (@boundary[0] < @cursor[1] < @boundary[2]));
}

為了讓 turn 寫起來方便，結果讓這些算式中的數字看起來有點怪怪的。或許改用 HashMap 與配合 left/right/top/bottom 等字串來表記方向會讓程式好讀一點……

總之有了這些基本元素之後，就可以來組合一下：

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;
        }
    };
}

這次把前面幾個函式前方加上 my 字，全放進 spiral-matrix 這個函式裡面。這麼做可以將其語意範圍縮小。最後核心部份的主要驟就是：如果下一步會撞牆，就先右轉。然後向前走一步。如果還是撞牆，一切都結束了(?)