如何为 Code 4 的出现编写排序算法

百变鹏仔 5天前 #Python

文章标签何为

在上一篇文章中，我简单提到我将参加今年的“代码降临”活动。巧合的是，在其中一个谜题中，特别是在第 5 天发布的谜题中，涉及修复列表中页面的顺序。这是在我发布关于实现排序算法的文章后不久，所以我认为我应该写一下它。

描绘某种排序算法的可爱图像

对于那些没有听说过“advent of code”的人来说，这是由 eric wastl 主办的年度活动。每年，它都会讲述一个以节日为背景的故事，今年的故事是关于寻找首席历史学家，他可能是每次大型圣诞雪橇发射中的重要人物。该挑战将于每年12月1日持续至25日。每天，剧情都会进展，并且包含一个编程谜题（并且带有输入）。

在故事叙述中，谜题通常被明确定义，并包含测试用例。每个谜题都分为两部分，第二部分只有在提交第一个答案后才会出现。

参与者可以用任何语言实现任何算法，甚至完全跳过编程，只要派生的答案匹配即可。今年我尝试用 python 编写解决方案，9 天后，我觉得我在整个过程中学到了很多东西。

第五天，故事要求帮忙印刷安全手册。输入包含页面规则和精灵尝试打印的页面列表。

47|5397|1397|6197|4775|2961|1375|5329|1397|2953|2961|5397|5361|2947|1375|4797|7547|6175|6147|2975|1353|1375,47,61,53,2997,61,53,29,1375,29,1375,97,47,61,5361,13,2997,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 combinationsdef 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 的文章

回到谜题。

最后，谜题要求计算所有页面排序正确的情况下中间页码的总和。

def get_middle(pages: tuple[int, ...]) -> int:    return pages[len(pages) // 2]def part1(input: str) -> int:    rules, pages_list = parse(input)    return sum(        get_middle(pages)        for pages in pages_list        if check_pages(rules, pages)    )

非常简单，如果你已经完成了所有正确的事情，那么它只是一个列表理解（因为 python 开发人员更喜欢这个而不是映射/过滤器）。

接下来是排序算法：

继续第 1 部分，第二部分想要中间页的总和，但适用于页面排序不正确的情况。该指令还要求在检索中间页码之前修复顺序。

虽然我的同行在没有成熟的排序算法的情况下设法解决了这个问题，但我决定按照前面描述的难题（在解释页面规则的部分中）的确切方式来完成它。我已经完成了比较部分（check_pair），现在我需要一个可以移动元素的函数。

def move(items: tuple[int, ...], current: int, incoming: int) -> tuple[int, ...]:    assert incoming > current    return (        *items[:current],        items[incoming],        *tuple(            item            for idx, item in enumerate(items)            if (idx >= current) and not (idx == incoming)        ),    )

假设我有 1,2,3,4,5，该函数将传入的数字移动到当前数字的前面。假设current = 2，传入= 4，那么我将得到1,4,2,3,5作为回报（假设我们是按照递增的数值排列）。

我向朋友解释算法的失败尝试

下一步是将我手写草稿中显示的算法转化为实际代码。

def sort_pages(    rules: tuple[tuple[int, int], ...],    pages: tuple[int, ...],    pointer: int = 0,    subpointer: int = 0,) -> tuple[int, ...]:    return (        sort_pages(            rules,            *next(                (                    (move(pages, pointer, incoming), pointer, pointer + 2)                    for incoming in range(subpointer, len(pages))                    if check_pair(rules, pages[pointer], pages[incoming]) is false                ),                (pages, pointer + 1, pointer + 2),            ),        )        if pointer < (len(pages) - 1)        else pages    )

是的，不幸的是它是递归的。我应该发布第一个版本，这可能更容易阅读：

def sort_pages(    rules: tuple[tuple[int, int], ...], pages: tuple[int, ...]) -> tuple[int, ...]:    result, pointer = pages, 0    while true:        if pointer == (len(pages) - 1):            break        changed = false        for incoming in range(pointer + 1, len(pages)):            if check_pair(rules, result[pointer], result[incoming]) is false:                result = move(result, pointer, incoming)                changed = true                break        pointer = 0 if changed else pointer + 1    return result

两者本质相同，只是最终的功能版本略有优化。参考草稿截图，我有两个指针，黄色下划线在代码中名为指针，传入蓝色下划线。

算法的工作原理如下：

首先将指针设置为第一个元素。
最初传入的总是它旁边的元素。
传入的指针将一次遍历一个元素，如果违反规则，会将值移至当前元素之前。
一旦发生这种情况，传入指针将重置，并移回当前的下一个。
当前指针没有改变位置，但它现在指向上一步中插入的新元素。

如果传入指针设法逐步遍历列表的其余部分而没有引入任何更改，则我们将当前指针前进（并且传入指针重新初始化到它旁边的位置），并再次重复该过程。

算法完成对最后 2 个元素的比较后，该过程结束，然后返回排序后的页面作为结果。然后，我们可以继续组装第 2 部分中的所有内容：

def part2(input: str) -> int:    rules, pages_list = parse(input)    return sum(        get_middle(sort_pages(rules, pages))        for pages in pages_list        if check_pages(rules, pages) is False    )

两个部分的代码相似。它只是对第 1 部分进行了轻微修改，只是过滤器子句中的一些变化，并且 get_middle 接收的是排序列表。本质上， if 就好像我正在以函数形式的构建块以稍微不同的组合来组装答案。

虽然这仍然不是一个有效的算法，因为时间复杂度接近 o(n^2)。根据windsurf中的cascade ai-companion，该算法在某些方面类似于插入排序（是的，这就是ai工具有用的时候，为算法提供解释）。

今天就这样，我很高兴算法运行良好，尽管我的生活目前一团糟（由于资金问题刚刚从一个项目中退出）。希望随着时间的推移事情会变得更好，下周我会再写。

文章推荐

如何为 Code 4 的出现编写排序算法

学习起来哪个更容易，SQL还是Python？

Python - 使用切片获取最后K个列表项的总和

Python程序计算标准差

使用内置函数的Python程序来反转数组的元素

Python程序检测链表中的循环