在上一篇文章中，我簡(jiǎn)單提到我將參加今年的“代碼降臨”活動(dòng)。巧合的是，在其中一個(gè)謎題中，特別是在第 5 天發(fā)布的謎題中，涉及修復(fù)列表中頁(yè)面的順序。這是在我發(fā)布關(guān)于實(shí)現(xiàn)排序算法的文章后不久，所以我認(rèn)為我應(yīng)該寫(xiě)一下它。

描繪某種排序算法的可愛(ài)圖像

對(duì)于那些沒(méi)有聽(tīng)說(shuō)過(guò)“Advent of Code”的人來(lái)說(shuō)，這是由 Eric Wastl 主辦的年度活動(dòng)。每年，它都會(huì)講述一個(gè)以節(jié)日為背景的故事，今年的故事是關(guān)于尋找首席歷史學(xué)家，他可能是每次大型圣誕雪橇發(fā)射中的重要人物。該挑戰(zhàn)將于每年12月1日持續(xù)至25日。每天，劇情都會(huì)進(jìn)展，并且包含一個(gè)編程謎題（并且?guī)в休斎耄?/p>

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

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

第五天，故事要求幫忙印刷安全手冊(cè)。輸入包含頁(yè)面規(guī)則和精靈嘗試打印的頁(yè)面列表。

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

讓我們從解析輸入開(kāi)始：

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ù)以生成兩個(gè)元組，一個(gè)用于頁(yè)面規(guī)則，另一個(gè)用于頁(yè)面序列。該代碼通過(guò)分隔符 | 區(qū)分兩種類型的定義。表示頁(yè)面規(guī)則， , 表示頁(yè)面。

在拼圖的第一部分，故事要求檢查頁(yè)面是否按順序排列。讓我們從實(shí)現(xiàn)一個(gè)完成這項(xiàng)工作的函數(shù)開(kāi)始：

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

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

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

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

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

引用自 Martin Fowler 撰寫(xiě)的題為 Function Length 的文章

回到謎題。

最后，謎題要求計(jì)算所有頁(yè)面排序正確的情況下中間頁(yè)碼的總和。

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

非常簡(jiǎn)單，如果你已經(jīng)完成了所有正確的事情，那么它只是一個(gè)列表理解（因?yàn)?Python 開(kāi)發(fā)人員更喜歡這個(gè)而不是映射/過(guò)濾器）。

接下來(lái)是排序算法：

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

雖然我的同行在沒(méi)有成熟的排序算法的情況下設(shè)法解決了這個(gè)問(wèn)題，但我決定按照前面描述的難題（在解釋頁(yè)面規(guī)則的部分中）的確切方式來(lái)完成它。我已經(jīng)完成了比較部分（check_pair），現(xiàn)在我需要一個(gè)可以移動(dòng)元素的函數(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ù)字移動(dòng)到當(dāng)前數(shù)字的前面。假設(shè)current = 2，傳入= 4，那么我將得到1,4,2,3,5作為回報(bào)（假設(shè)我們是按照遞增的數(shù)值排列）。

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

下一步是將我手寫(xiě)草稿中顯示的算法轉(zhuǎn)化為實(shí)際代碼。

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

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

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ì)相同，只是最終的功能版本略有優(yōu)化。參考草稿截圖，我有兩個(gè)指針，黃色下劃線在代碼中名為指針，傳入藍(lán)色下劃線。

算法的工作原理如下：

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

如果傳入指針設(shè)法逐步遍歷列表的其余部分而沒(méi)有引入任何更改，則我們將當(dāng)前指針前進(jìn)（并且傳入指針重新初始化到它旁邊的位置），并再次重復(fù)該過(guò)程。

算法完成對(duì)最后 2 個(gè)元素的比較后，該過(guò)程結(jié)束，然后返回排序后的頁(yè)面作為結(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

兩個(gè)部分的代碼相似。它只是對(duì)第 1 部分進(jìn)行了輕微修改，只是過(guò)濾器子句中的一些變化，并且 get_middle 接收的是排序列表。本質(zhì)上， if 就好像我正在以函數(shù)形式的構(gòu)建塊以稍微不同的組合來(lái)組裝答案。

雖然這仍然不是一個(gè)有效的算法，因?yàn)闀r(shí)間復(fù)雜度接近 O(n^2)。根據(jù)windsurf中的cascade AI-companion，該算法在某些方面類似于插入排序（是的，這就是AI工具有用的時(shí)候，為算法提供解釋）。

今天就這樣，我很高興算法運(yùn)行良好，盡管我的生活目前一團(tuán)糟（由于資金問(wèn)題剛剛從一個(gè)項(xiàng)目中退出）。希望隨著時(shí)間的推移事情會(huì)變得更好，下周我會(huì)再寫(xiě)。

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