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

作者:
發佈於: ,更新於:
#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] 以外所有數字的乘積。那,可以拆分成為三種狀況:

  1. N 裡面沒有 0
  2. N 裡面只有一個 0,其所在位置為 i
  3. 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,      # ←
];

然後先定義兩個函式: turnnext-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 這個函式裡面。這麼做可以將其語意範圍縮小。 最後核心部份的主要驟就是:如果下一步會撞牆,就先右轉。然後向前走一步。如果還是撞牆,一切都結束了(?)