火柴棍壓縮

每週挑戰 296

穆罕默德·S·安瓦爾 (Mohammad S. Anwar) 每週都會發出“每週挑戰”，讓我們所有人都有機會為每週兩次的任務提出解決方案。我的解決方案先用Python編寫，然後轉換為Perl。這對我們所有人來說都是練習編碼的好方法。

挑戰，我的解決方案

任務 1：字串壓縮

任務

您將獲得一串字母字符，$chars。

編寫一個腳本，使用遊程編碼來壓縮字串，如範例所示。

壓縮單元可以是單一字符，也可以是計數後面跟著一個字符。

獎勵：寫一個解壓縮函數。

我的解決方案

由於正規表示式的強大功能，這是一項非常簡單的任務。 Python 和 Perl 都允許替換值是一個函數。因此，我有一個名為 sc 的函數，它將多個字母轉換為數字和字母。例如如果輸入是aaa，它將回傳3a。

def sc(match):
    m = match.group(0)
    return str(len(m)) + m[0]

然後就是根據需要呼叫這個函數了。

def string_compress(s: str) -> str:
    return re.sub(r'(([a-z])+)', sc, s)

解壓縮函數（僅限Python）以類似的方式運作。它採用數字後面跟著字母的模式，並將其更改為重複指定次數的字母。

def usc(match):
    m = match.group(0)
    return m[-1] * int (m[:-1])

def string_decompress(s: str) -> str:
    return re.sub(r'(\d+[a-z])', usc, s)

為了從命令列執行，我使用 argparse 模組來查看是否指定了 --decompress 選項。

def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("--decompress", help="decompress the input", action='store_true')
    parser.add_argument("str", help="the string to compress/decompress")
    args = parser.parse_args()

    if args.decompress:
        result = string_decompress(args.str)
    else:
        result = string_compress(args.str)
    print(result)

範例

$ ./ch-1.py abbc
a2bc

$ ./ch-1.py aaabccc
3ab3c

$ ./ch-1.py abcc
ab2c

$ ./ch-1.py --decompress a2bc
abbc

$ ./ch-1.py --decompress 3ab3c
aaabccc

$ ./ch-1.py --decompress ab2c
abcc

任務2：火柴方

任務

給你一個整數數組，@ints。

編寫一個腳本來查找是否可以使用給定數組 @ints 中的棍子製作一個正方形，其中 $ints[ì] 是第 i 根棍子的長度。

我的解決方案

這會有點長，所以請繫好安全帶。我檢查的第一件事是木棍的總和是否能被四整除。如果不是，沒有可能的解決方案，我可以回傳 false

我還可以檢查沒有一根棍子比一邊長。如果發生這種情況，我也會回傳 false。

透過這兩項檢查，所有範例都會給出正確的結果。然而，它會錯誤地報告 4 3 3 3 3 為真，但實際上並非如此。

嘗試二

查看範例和我自己的想法，我認為解決方案是匹配一對值來匹配每一側。因此，對於例 3 4 1 4 3 1，我們有兩對 3 和 1 棍子，組成四根棍子。這將解決 4 3 3 3 3 問題，因為 3 沒有匹配的。

但是如果棍子是 4 4 3 1 2 1 1，這將不起作用，因為一側使用三根棍子（一根 2 和兩根 1）

試三

所以我的下一次嘗試有點複雜，我認為這是一個很好的解決方案......直到它不是。對於這次嘗試，我從最長的棍子開始。如果不是邊的長度，我就拿完成邊所需的下一根最長的棍子，然後重複，直到沒有可能的解決方案。使用此方法，以下解決方案是正確的。

• 4 4 3 1 2 1 1
• 9 5 4 3 3 3 3 3 3
• 9 6 3 5 4 3 3 3
• 9 6 3 5 4 3 3 2 1

我以為這就是解決方案，直到我意識到 9 5 3 1 5 2 2 3 3 3 不起作用。第一條邊是 9，下一條邊是 5 3 1，第三邊會失敗，只有 5 3 而沒有 1。

嘗試四

此時，我開始懷疑是否有可能想出一個不涉及暴力的解決方案。所以我睡在上面，在平板電腦上寫下了很多東西（我正在度假，所以我不能使用我的白板），然後又睡在上面。我的結論是使用遞歸函數是唯一的解決方案。

也許我只是想太多了，或者也許有一個我剛剛想到的真正簡單的解決方案（就像上週的情況）。

最終程式碼

還在讀書嗎？幹得好:)

對於這個任務，我有一個名為 make_side 的遞歸函數。它需要一個剩餘棍棒的清單（Perl 中的 arrayref）以及所需的長度。然後它會遍歷剩餘的棍子（首先是最高的）。然後發生以下三件事之一：

• 如果棍子比要求的長度長，我會跳過它。
• 如果是需要的長度，我就回。
• 如果它很短，我會使用它並再次調用該函數以使用另一根棍子。此呼叫會刪除已使用的棍子，並根據已使用的棍子的長度減少所需的長度。

該函數將傳回所使用的棍子列表，如果未找到有效的棍子組合，則傳回 None（Perl 中的 undef）。

def sc(match):
    m = match.group(0)
    return str(len(m)) + m[0]

拼圖的最後一塊，我執行第一部分中提到的檢查（總和可以被四整除，長度不能超過邊長），然後呼叫上面的函數。如果返回 None，我返回 false。如果所有的棍子都被使用，我返回true。

def string_compress(s: str) -> str:
    return re.sub(r'(([a-z])+)', sc, s)

範例

def usc(match):
    m = match.group(0)
    return m[-1] * int (m[:-1])

def string_decompress(s: str) -> str:
    return re.sub(r'(\d+[a-z])', usc, s)

以上是火柴棍壓縮的詳細內容。更多資訊請關注PHP中文網其他相關文章！