解 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.index 與 str.rindex，能找出指定目標物出現在字串中最左邊與最右邊的位置，但若目標物並不存在於字串中時，那兩個函式式會丟出例外。以本題為目的的話，str.find 與 str.rfind 用起來比較容易，這兩函式與 Raku 中的 index 與 rindex 行為正好完全一樣。

而 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 排序過，或可利用數字大小關係去排除一部份的搜尋範圍。但似乎沒有合適的貪婪演算法或是動態規劃演算法。