Raku: 解 Perl Weekly Challenge 082

作者:   發佈於: ,更新於:

本周的 Perl Weekly Challenge 082 的題目不錯,兩題都很適合拿來當做討論演算法的題目。

TASK #1 › Common Factors

這題的題目描述為:

You are given 2 positive numbers $M and $N. Write a script to list all common factors of the given numbers.

直觀地來解,就是分別找出兩數的所有因數,再取交集:

sub common-factors (Int $M, Int $N) {
    factors($N) ∩ factors($M)
}

其中 符號為交集運算子。而 factors 函式定義為:

sub factors (Int $n) {
    (1..$n).grep(-> $it { $n %% $it });
}

%% 是「整除於運算子」。$a %% $b$a % $b == 0 兩者同義。

基本上這樣就以暴力法打完收工了。不過這演算法的時間複雜度是至少是 𝑂(MN)-- 無論 M 與 N 之間關係為何,都必需要走 MN 次餘數除法才能找出所有因數。取兩集合交集的時間複雜度另計。

立刻想到一些可以修改的地方。

如果 M 很小,而 N 很大。在取 N 之因數時,取到任何比 M 大者,都不會在結果中出現。因此這部份的計算是白花時間。

前述 factors 函式中,$n/2 .. $n 這段範圍裡,只有 $n 一個數字必為 $n 的因數,其他的數字必定不是 $n 的因數。因此這函式有 50% 的計算量是在浪費時間。

稍微修改之後,再版如下:

sub common-factors (Int $a, Int $b) {
    my $x = min($a, $b);
    my @x = (1, 2..$x/2, $x).flat;
    return @x.grep(-> $it { $a %% $it && $b %% $it });
}

基本上的想法是框出一個較小的搜尋範圍 @x,且要保證所有的共同因數都會落在這範圍中。

感覺起來還有能改進的可能,但好像會進入特化的領域。像是先檢查兩數有沒有哪個是質數,有的話 2..$x/2 這個範圍全部都不必檢查之類的。

(10/14 更新) 經過推友 zard1989 提示,先確認了「兩數之公因數全部都是最大公因數之因數」這件事。於是再改版如下:

sub common-factors (Int $a, Int $b) {
    my $x = $a gcd $b;
    return (1..$x).grep(-> $n { $x %% $n });
}

嗯,求最大公因數這個計算,在 Raku 中是個內建的運算符:infix gcd

如此一來,搜尋範圍的上限就不可能再下降了。似乎也可以不必特別處理有質數的狀態。應該算是個很不錯的解了。

TASK #2 › Interleave String

這題題目為:

You are given 3 strings; $A, $B and $C. Write a script to check if $C is created by interleave $A and $B. Print 1 if check is success otherwise 0.

也就是要去檢查 $C 是否能由 $A$B 交織而成。何謂「交織」?配合幾個範例後才看懂了。

簡單地說,如果 $C 可以由 $A$B 的片斷(子字串)輪流交替相連而成,那就說是 $C$A$B 交織品。

也就是說,要檢驗這點,可以逐一看過 $C 裡的字符,判斷那是從 $A 來的或是從 $B 來的。但亦會出現兩邊都有可能的狀況,會需要個搜尋過程。

最後寫得一個不需回溯、時間 O(n) 空間 O(n) 出來的解法如下,其中 n 為字串 $C 的字符數。這段程式碼還頂長的:

sub interleaves (Str $A, Str $B, Str $C) {
    my @stash;
    @stash.push([-1, -1]);

    my $i = 0;
    while $i < $C.chars && @stash.elems > 0 {
        my $c = $C.substr($i++, 1);
        my @stash2 = gather {
            while @stash.elems > 0 {
                my $it = @stash.pop();
                my $a = $A.substr($it[0]+1, 1);
                my $b = $B.substr($it[1]+1, 1);
                if $c eq $a {
                    take [$it[0]+1, $it[1]];
                }
                if $c eq $b {
                    take [$it[0], $it[1]+1];
                }
            }
        };

        @stash = @stash2.unique(:with(&[eqv]));
    }

    return $i == $C.chars && @stash.elems > 0 && @stash[0][0].succ == $A.chars && @stash[0][1].succ == $B.chars;
}

寫這段時發現 Raku 中,要取字串特定位置之字符出來,似乎得用 substr,並沒有類似 charAt 這類名字的函式。