解 Perl Weekly Challenge 087

作者：gugod 發佈於：2020/11/20 #raku

TASK #1 › Longest Consecutive Sequence

You are given an unsorted array of integers @N.

Write a script to find the longest consecutive sequence. Print 0 if none sequence
found.

Example 1:

Input: @N = (100, 4, 50, 3, 2)
Output: (2, 3, 4)

Example 2:

Input: @N = (20, 30, 10, 40, 50)
Output: 0

Example 3:

Input: @N = (20, 19, 9, 11, 10)
Output: (9, 10, 11)

看來這輸入 @N 是一些沒有排序過的整數，而輸出則是一段連續整數數列，且每個元素都要在 @N 裡面。如果有很多段的話，還要挑出最長的。

如果 @N 是以升冪次序排好了的話，那就只要逐一檢查目前的數字是否與前一數字差一，並依此條件判斷目前的數列，再順便更新一下目前已知最長數列，似乎就行了。

Raku 版寫來如下。時間複雜度為 O(n log(n))，空間為 O(1)：

sub longest-consecutive-sequence(@N) {
    my @m = @N.sort({ $^a <=> $^b });

    my $seq_from = @m[0];
    my $seq_until = @m[0];
    my $longest_seq_from = @m[0];
    my $longest_seq_until = @m[0];
    my $longest_seq_length = 0;

    for 1..@m.end -> $i {
        my $n = @m[$i];
        if $n - @m[$i-1] == 0|1 {
            $seq_until = $n;
            my $len = $seq_until - $seq_from;
            if $longest_seq_length < $len {
                $longest_seq_from   = $seq_from;
                $longest_seq_until  = $seq_until;
                $longest_seq_length = $len;
            }
        } else {
            $seq_from  = $n;
            $seq_until = $n;
        }
    }

    return $longest_seq_length == 0 ?? Nil !! [$longest_seq_from...$longest_seq_until];
}

TASK #2 › Largest Rectangle

You are given matrix m x n with 0 and 1.

Write a script to find the largest rectangle containing only 1. Print 0 if none found.

Example 1:

Input:
[ 0 0 0 1 0 0 ]
[ 1 1 1 0 0 0 ]
[ 0 0 1 0 0 1 ]
[ 1 1 1 1 1 0 ]
[ 1 1 1 1 1 0 ]

Output:
[ 1 1 1 1 1 ]
[ 1 1 1 1 1 ]

Example 2:

Input:
[ 1 0 1 0 1 0 ]
[ 0 1 0 1 0 1 ]
[ 1 0 1 0 1 0 ]
[ 0 1 0 1 0 1 ]

Output: 0

Example 3:

Input:
[ 0 0 0 1 1 1 ]
[ 1 1 1 1 1 1 ]
[ 0 0 1 0 0 1 ]
[ 0 0 1 1 1 1 ]
[ 0 0 1 1 1 1 ]

Output:
[ 1 1 1 1 ]
[ 1 1 1 1 ]

看來就是在零壹矩陣中找出全為壹之子矩陣中之最大者。最直觀的解法，就是窮舉出所有子矩陣、去掉不全為壹者、再紀錄最大者。至於何為最「大」？問題中沒明說，姑且就用寬高相乘。

一個子矩陣可用左上與右下兩點之座標來清楚地定義出來。從題意猜來，大小為一之子矩陣似乎不算，也就是左上角與右下角的座標不能相同。所以，要窮舉出所有子矩陣，就等於是先找出所有座標之集合，再取此集合之兩兩組合、最後將不符合左上右下關係者去掉。

慣例上來說，如果用二維陣列 @matrix 來裝一個矩陣的話，第一維為橫、第二維為豎。也就是說高度 $h 為第一維之元素數量，寬度 $w 為第二維之元素數量：

$h = @matrix.elems;
$w = @matrix[0].elems;

而一個寬為 $w 高為 $h 的矩陣之所有座標點，就是 [0 .. ^$h] 與 [0 .. ^$w] 兩整數集合之外積：

([^$h] X [^$w])

再取兩兩組合、並去掉不不符合左上、右下相對關係者：

.combinations(2)
.grep(-> ($p, $q) { $p[0] <= $q[0] and $p[1] <= $q[1] })

這樣是得到一組組 (左上、右下) 的座標組合。再接著轉回實際的子矩陣：

.map(
    -> ($p, $q) {
        ($p[0] .. $q[0]).map(
            -> $y {
                @matrix[$y][ $p[1] .. $q[1] ]
            })
    })

…去掉不全為一者…

.grep(
    -> @m {
        ([^@m] X [^@m[0]]).map(-> ($y,$x) { @m[$y][$x] == 1 }).all
    }
)

…取寬高相乗最大者…

.max(-> @m { @m.elems * @m[0].elems });

就解完了。

上述片段全部合體後得函式如下：

sub largest-rectangle(@matrix) {

    ([^@matrix] X [^@matrix[0]])
    .combinations(2)
    .grep(
        -> ($p, $q) {
            $p[0] <= $q[0] and $p[1] <= $q[1]
        })

    .map(
        -> ($p, $q) {
            ($p[0] .. $q[0]).map(
                -> $y {
                    @matrix[$y][ $p[1] .. $q[1] ]
                })
        })

    .grep(
        -> @m {
            ([^@m] X [^@m[0]]).map(-> ($y,$x) { @m[$y][$x] == 1 }).all
        })

    .max(
        -> @m {
            @m * @m[0]
        })
}

中間那建出子矩陣的部份，一開始我試著用陣列切片的語法這麼寫：

    @matrix[ $p[0] .. $q[0] ][ $p[1] .. $q[1] ]

但這招行不通，於執行時出現一堆錯誤。不曉得 Raku 中有沒有能一步切出一個二維陣列切片這種這麼炫炮的語法。