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

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

對於那些沒有聽說過「Advent of Code」的人來說，這是由 Eric Wastl 主辦的年度活動。每年，它都會講述一個以節(jié)日為背景的故事，今年的故事是關(guān)於尋找首席歷史學(xué)家，他可能是每次大型聖誕雪橇發(fā)射中的重要人物。該挑戰(zhàn)將於每年12月1日持續(xù)至25日。每天，劇情都會進展，並且包含一個程式設(shè)計謎題（並且?guī)в休斎耄?

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

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

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

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()), ((), ())
    )

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

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

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

然後另一個函數(shù)發(fā)送所有頁面組合（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)
    )

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

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

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

引用自 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

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

接下來是排序演算法：

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

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

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()), ((), ())
    )

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

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

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

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

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

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)
    )

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

演算法的工作原理如下：

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

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

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

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 接收的是排序列表。本質(zhì)上， if 就好像我正在以函數(shù)形式的構(gòu)建塊以稍微不同的組合來組裝答案。

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

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

以上是如何為 Code 4 的出現(xiàn)編寫排序演算法的詳細內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！