解 Perl Weekly Challenge 083:以 Raku 與 Python。

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

Perl Weekly Challenge 083 這周也是兩個題目。這次試著用 Raku 與 Python 來解看看。

TASK #1 › Words Length

這題沒講說 "word" 的定義是甚麼,故且就用「一連串非空白字符」這個簡單的定義好了。定義想清楚後演算法就出來了:先將輸入 $s 去掉前後空白,再取得第一個空白到最後一個空白中間的距離。將此數字減去剩餘空白總數,就是答案。

# Raku
sub words-length (Str $s) {
    my @w = $s.trim.indices(' ');
    return @w.elems == 0 ?? 0 !! @w.tail - @w.head - @w.elems + 1;
}

# Python
def wordsLength(s):
    s = s.strip(' ')
    p = s.find(' ')
    return 0 if p == -1 else (s.rfind(' ') - p - s.count(' ') + 1);

可以看到 Raku 與 Python 兩語言提供的函式庫似乎很類似。Python 有 str.indexstr.rindex,能找出指定目標物出現在字串中最左邊與最右邊的位置,但若目標物並不存在於字串中時,那兩個函式式會丟出例外。以本題為目的的話,str.findstr.rfind 用起來比較容易,這兩函式與 Raku 中的 indexrindex 行為正好完全一樣。

而 Python 中的 str.count 函式能計數某目標在字串中的出現次數。在 Raku 中並沒有與 Python str.count 行為一樣的函式,倒是有個能一次找出所有目標物位置的 indices 函式。以 @w = $s.indices(' ') 如此呼叫函式會使其傳回一個整數陣列 @w,其元素數 @w.elems 就是空白字符在 $s 中的出現次數。且第一個元素 @w.head 正好就是 $s.index(' '),而最後一個元素 @w.tail 正好就是 $s.rindex(' ')。雖然 @w 中間的項目全部都沒有用到,但這樣寫起來頂簡潔的。

另外就是 Python 中的 s.strip() 的行為與 Raku 中 $s.trim 相同。都是把字串 s 中兩端的空白字符去除掉。不過 Raku trim 函式並不接受參數。

TASK #2 › Flip Array

這一題比較有意思。輸入是一個正整數陣列 @A,目的是要找出其中一個最小的子集合,在將子集合中所有數字翻為負號後,使總和為最小且不為負。

稍微換句話說,就是找到一個 @A 之子集合 @B,使 sum(@A) - 2 * sum(@B) 不為負數且為最小,並且 @B 的長度亦為最小。這裡的算式是在 @A 內容全為正整數之下才與原題意相同。

題目只要求要取得 @B 的長度,而沒要求 @B 的內容。這一點有點令人在意。

一個直觀的暴力解法就是去列舉出所有長度的 @B,逐一計算總和並追蹤最小之總和與其對應的 @B

@A 衍生出長度為 $k 的子集合 @B,這是取組合,@A 的長度若是 n,就是會有 C(n, k) 種取法。

這種要取出所有特定長度組合的事情,在 python 中就是 itertools.combinations 這個函數能解決。竟然也有一題 Leetcode 就是要做一個 combination iterator。真是個高人氣題目。

在 Raku 也已經內建有由 List 生出 k 個元素組合的函數:combinations。由其 signature 看來,傳回值為 Seq 型別。正好就是個 combination iterator。

由於搜尋標的條件有兩條:① 總和要最小,且 ② @B 的元素數亦要最少。就算在列舉 @B 時由短至長,在搜得第一組答案時,未必就能滿足條件①,並不能因此立刻停止。唯總和為零時,由於不可能更小,所以可以立刻停止。

以暴力法所寫得的完整答案如下:

# Raku
sub flip-elems (@n) {
    my $sum = [+] @n;
    my @min_combination = @n;
    my $min_sum = Inf;
    K: for 1..@n.elems - 1 -> $k {
        for @n.combinations($k) -> @c {
            my $s = $sum - 2 * ([+] @c);
            if 0 <= $s < $min_sum {
                @min_combination = @c;
                $min_sum = $s;
                if $s == 0 {
                    last K;
                }
            }
        }
    }
    say ">> $min_sum = ([+] {@n}) - 2 * ([+] {@min_combination})";
    return @min_combination.elems;
}

# Python
import itertools

def flipCombination(A):
    minSum = nSum = sum(A)
    minCombination = ()
    for k in range(1, len(A)):
        for c in itertools.combinations(A, k):
            s = nSum - 2 * sum(c)
            if 0 <= s < minSum:
                minCombination = c
                minSum = s
                yield minSum, minCombination

def flipElems(A):
    minSum = 0
    minCombination = ()
    for minSum, minCombination in flipCombination(A):
        if minSum == 0:
            break
    print(f'>> {minSum} = sum({A}) - 2 * sum({minCombination})')
    return len(minCombination)

在 Python 這裡似乎沒有能從多層迴圈深處瞬間移動出來的手段,所以就拆成兩個函式。其一 flipCombination 是個 iterator,在上層 flipElems 被使用。上層如果看到 s == 0,表示可以提早下班(?)休息(break),只要把 iterator 放置不管就好了。

在 Raku 這邊為了方便起見,就直接用 last K 這種與 goto 無限接近的寫法了。但要像做 Van Eck 數列產生器 那般另外做個 iterator 把雙層迴圈藏到別的函式去,想來亦不困難。

在 Python 與 Raku 兩解之中,都使用到了 0 <= s < minSum 這種連環比較運算式語法。可見這語法確實有其便利性。

由於一時想不到這題問是否有比暴力解更佳的解法,就暫時沒再想下去了。如果先將 @A 排序過,或可利用數字大小關係去排除一部份的搜尋範圍。但似乎沒有合適的貪婪演算法或是動態規劃演算法。