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 這類名字的函式。