如何為 Code 4 的出現編寫排序演算法

在上一篇文章中，我簡單提到我將參加今年的「程式碼降臨」活動。巧合的是，在其中一個謎題中，特別是在第 5 天發布的謎題中，涉及修復清單中頁面的順序。這是在我發布關於實現排序演算法的文章後不久，所以我認為我應該寫一下它。

描繪某種排序演算法的可愛圖像

對於那些沒有聽說過「Advent of Code」的人來說，這是由 Eric Wastl 主辦的年度活動。每年，它都會講述一個以節日為背景的故事，今年的故事是關於尋找首席歷史學家，他可能是每次大型聖誕雪橇發射中的重要人物。該挑戰將於每年12月1日持續至25日。每天，劇情都會進展，並且包含一個程式設計謎題（並且帶有輸入）。

在故事敘述中，謎題通常被明確定義，並包含測試案例。每個謎題都分為兩個部分，第二部分只有在提交第一個答案後才會出現。

參與者可以用任何語言實現任何演算法，甚至完全跳過編程，只要派生的答案匹配即可。今年我嘗試用 Python 寫解決方案，9 天后，我覺得我在整個過程中學到了很多。

第五天，故事要求幫忙印製安全手冊。輸入包含頁面規則和精靈嘗試列印的頁面清單。

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

讓我們先從解析輸入開始：

def parse(
    input: str,
) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
    def inner(
        current, incoming
    ) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
        rules, pages = current

        if "|" in incoming:
            return rules + (
                tuple(int(item) for item in incoming.strip().split("|")),
            ), pages

        else:
            return rules, pages + (
                tuple(int(item) for item in incoming.strip().split(",")),
            )

    return reduce(
        inner, filter(lambda line: line.strip(), input.strip().splitlines()), ((), ())
    )

該函數接收名為input 的字串形式的輸入，使用.splitlines() 將其分成幾行，然後發送到內部函數以產生兩個元組，一個用於頁面規則，另一個用於頁面序列。程式碼透過分隔符號 | 區分兩種類型的定義。表示頁面規則， , 表示頁面。

在拼圖的第一部分，故事要求檢查頁面是否按順序排列。讓我們從實作一個完成這項工作的函數開始：

def check_pair(rules: tuple[tuple[int, int], ...], alpha: int, beta: int) -> bool:
    return (beta, alpha) not in rules

然後另一個函數發送所有頁面組合（combinations((1,2,3), 2) 回傳 1,2, 1,3 和 2,3）：

from itertools import combinations

def check_pages(rules: tuple[tuple[int, int], ...], pages: tuple[int, ...]) -> bool:
    return all(
        check_pair(rules, alpha, beta)
        for alpha, beta in combinations(pages, 2)
    )

我將這兩個函數分成單獨的函數的主要原因是我想讓每個部分盡可能小。根據我的經驗，保持事物足夠小不僅可以使其可測試，而且通常還有助於調試最終輸入（通常很大）。

很多時候，第 2 部分會讓人感到驚訝，並且經常會發現它要求對第 1 部分的代碼設計進行修訂。這可能是您已實現的內容的一個小變化，或者需要不同的功能不同目標的調用順序等。我確實保持在工作中編寫短函數的習慣（作為註釋的替代）。

像這樣的小函數只有名字好才有效，所以你需要注意命名。這需要練習，但是一旦你熟練了，這種方法就可以使程式碼變得非常自我記錄。較大規模的函數讀起來就像一個故事，讀者可以根據需要選擇深入了解哪些函數以了解更多細節。

引用自 Martin Fowler 撰寫的題為 Function Length 的文章

回到謎題。

最後，謎題要求計算所有頁面排序正確的情況下中間頁碼的總和。

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

非常簡單，如果你已經完成了所有正確的事情，那麼它只是一個列表理解（因為 Python 開發人員更喜歡這個而不是映射/過濾器）。

接下來是排序演算法：

繼續第 1 部分，第二部分想要中間頁的總和，但適用於頁面排序不正確的情況。該指令還要求在檢索中間頁碼之前修復順序。

雖然我的同行在沒有成熟的排序演算法的情況下設法解決了這個問題，但我決定按照前面描述的難題（在解釋頁規則的部分中）的確切方式來完成它。我已經完成了比較部分（check_pair），現在我需要一個可以移動元素的函數。

def parse(
    input: str,
) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
    def inner(
        current, incoming
    ) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
        rules, pages = current

        if "|" in incoming:
            return rules + (
                tuple(int(item) for item in incoming.strip().split("|")),
            ), pages

        else:
            return rules, pages + (
                tuple(int(item) for item in incoming.strip().split(",")),
            )

    return reduce(
        inner, filter(lambda line: line.strip(), input.strip().splitlines()), ((), ())
    )

假設我有 1,2,3,4,5，該函數將傳入的數字移到目前數字的前面。假設current = 2，傳入= 4，那麼我將得到1,4,2,3,5作為回報（假設我們是按照遞增的數值排列）。

我向朋友解釋演算法的失敗嘗試

下一步是將我手寫草稿中顯示的演算法轉換為實際程式碼。

def check_pair(rules: tuple[tuple[int, int], ...], alpha: int, beta: int) -> bool:
    return (beta, alpha) not in rules

是的，不幸的是它是遞歸的。我應該發布第一個版本，這可能更容易閱讀：

from itertools import combinations

def check_pages(rules: tuple[tuple[int, int], ...], pages: tuple[int, ...]) -> bool:
    return all(
        check_pair(rules, alpha, beta)
        for alpha, beta in combinations(pages, 2)
    )

兩者本質相同，只是最終的功能版本略有最佳化。參考草稿截圖，我有兩個指針，黃色底線在代碼中名為指針，傳入藍色下劃線。

演算法的工作原理如下：

1. 首先將指標設定為第一個元素。
2. 最初傳入的總是它旁邊的元素。
3. 傳入的指標會一次遍歷一個元素，如果違反規則，會將值移至目前元素之前。
4. 一旦發生這種情況，傳入指標將重置，並移回目前的下一個。
5. 目前指標沒有改變位置，但它現在指向上一個步驟中插入的新元素。

如果傳入指標設法逐步遍歷列表的其餘部分而沒有引入任何更改，則我們將當前指標前進（並且傳入指標重新初始化到它旁邊的位置），並再次重複該過程。

演算法完成最後 2 個元素的比較後，該過程結束，然後返回排序後的頁面作為結果。然後，我們可以繼續組裝第 2 部分中的所有內容：

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

兩個部分的程式碼相似。它只是對第 1 部分進行了輕微修改，只是過濾器子句中的一些變化，並且 get_middle 接收的是排序列表。本質上， if 就好像我正在以函數形式的構建塊以稍微不同的組合來組裝答案。

雖然這仍然不是一個有效的演算法，因為時間複雜度接近 O(n^2)。根據windsurf中的cascade AI-companion，演算法在某些方面類似於插入排序（是的，這就是AI工具有用的時候，為演算法提供解釋）。

今天就這樣，我很高興演算法運作良好，儘管我的生活目前一團糟（由於資金問題剛從一個專案中退出）。希望隨著時間的推移事情會變得更好，下週我會再寫。

以上是如何為 Code 4 的出現編寫排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！