解 Perl Weekly Challenge 091 -- 數數字與跳格子

TASK #1 › Count Number

Submitted by: Mohammad S Anwar

You are given a positive number $N.

Write a script to count number and display as you read it.

Example 1:

Input: $N = 1122234
Output: 21321314

as we read "two 1 three 2 one 3 one 4"

Example 2:

Input: $N = 2333445
Output: 12332415

as we read "one 2 three 3 two 4 one 5"

Example 3:

Input: $N = 12345
Output: 1112131415

as we read "one 1 one 2 one 3 one 4 one 5"

解 #1 › Count Number

依照這題題意所的的直觀方法就是，取得數字 $N 的每個位數後，逐一迭代，算得此位數字接下來重複出現次數，並將重複次數轉換為輸出的一部分。假設輸入數字為 XXYZZZ ，輸出則應為 2X1Y3Z。這其實就是坊間常見(?)的 RLE 編碼法 (Run-length encoding)。

依此解法寫得的 Raku 語程式如下：

sub MAIN (Int $N) {

    # [1]
    my @chars = $N.comb;

    my Str $out;
    my $i = 0;
    my $j = 0;

    # [2] invariant: @chars[$i..$j] eq (@chars[$i] x ($j - $i))
    while $j < @chars.elems {
        $j++ while $j < @chars.elems && @chars[$i] eq @chars[$j];

        $out ~= ($j - $i) ~ @chars[$i];

        $i = $j;
    }

    say $out;
}

在 [1] 處，使用了 .comb 函式一步直接把整數 $N 轉成字串後，取得字串列表，存在左方陣列 @chars 中。

在 [2] 的迴圈處，則是調整 $j 的值，使其盡量大，但同時不能違反 @chars[$i] eq @chars[$j] 這個條件。也就是說，在外層 while 迴圈內， $i..$j 這個數字範圍所對應到的字串都是相同的。因此 $j - $i 就是字符 @chars[$i] 重複出現之次數。

其他部分就是逐漸把輸出 $out 建構出來而已。

TASK #2 › Jump Game

Submitted by: Mohammad S Anwar

You are given an array of positive numbers @N, where value at each index determines how far you are allowed to jump further.

Write a script to decide if you can jump to the last index. Print 1 if you are able to reach the last index otherwise 0.

Example 1:

Input: @N = (1, 2, 1, 2)
Output: 1

as we jump one place from index 0 and then twoe places from index 1 to reach the last index.

Example 2:

Input: @N = (2,1,1,0,2)
Output: 0

it is impossible to reach the last index. as we jump two places from index 0 to reach index 2, followed by one place jump from index 2 to reach the index 3. once you reached the index 3, you can't go any further because you can only jump 0 position further.

解 #2 › Jump Game

這題題目描述了某個版本的跳格子遊戲。整數陣列 @N 的內容表示遊戲規則，每一「格」中的數字，表示可以向前跳的最大格數。若有 @N = (2, 3, 0, 1)，當「站」在第 0 格時，格中數目為 @N[0] == 2，表示可以跳到第 1 格 (@N[1]) 或第 2 格 (@N[2])。

此題的直觀解是直接跳跳看。做個 BFS 或 DFS，把所有可能性都查過一遍。

另有個不直觀解是使用 Dynamic programming，先把 @N 尾端幾格解了，再利用剛剛取得的部分解答往前逐漸取得整體解答。實作此演算法的 Raku 語程式如下。

sub play-jump-game (@N) {

    # [1]: $reachable[$i] = solution of the sub-problem: $i .. @N.end
    my Bool @reachable = @N.map({ False });
    @reachable[ @reachable.end ] = True;

    # [2]: Solve the lightly bigger sub-problem each time
    for @N.end-1 ... 0 -> $i {
        my $maxjump = @N[$i];

        # [3]: Take 1 jump, see if I land on a pad that's known to reachable to the end
        @reachable[$i] = any( @reachable[$i+1 .. min($i+$maxjump, @reachable.end)]).Bool;
    }

    say '@N = ' ~ @N.raku;
    say @reachable[0] ?? 1 !! 0;
}

在 [1] 處，首先定義一個容器 @reachable 來裝解答。@reachable[$i] 若為 True，表示可以從第 $i 格跳到終點，否則表示跳不到。依次定義，最後一格必定為 True。

在 [2] 處的迴圈，則是從倒數第2格開始往前處理。如果跳得到的目標中有任何一格是已知可接到終點的，那麼本格必定也可接到終點。這一行的實作在 [3] 處，也就是檢查 @reachable 某一小段範圍的內容是否有任一一個為 True。

前述迴圈結束後 @reachable[0] 中裝的就是整體解答了。