写点什么

编程谜题:提升你解决问题的训练场

  • 2021 年 12 月 06 日
  • 本文字数:13132 字

    阅读完需:约 43 分钟

摘要:有趣的编程谜题可以练习你解决问题的能力,快来挑战吧~~


本文分享自华为云社区《代码的出现:用 Python 解决你的难题》,作者: Yuchuan 。


代码谜题的出现旨在让任何对解决问题感兴趣的人都能上手。您不需要具有深厚的计算机科学背景即可参与。相反,代码的来临是学习新技能和测试 Python 新功能的绝佳场所。

编程中的困惑?


处理谜题似乎是在浪费您可用的编程时间。毕竟,您似乎并没有真正生产出任何有用的东西,也没有推进您当前的项目。


然而,花一些时间练习编程谜题有几个好处:

  • 与您的常规工作任务相比,编程难题通常更明确且包含更多内容。它们让您有机会针对比您在日常工作中通常需要处理的问题更简单的问题练习逻辑思维

  • 你经常可以用几个类似的谜题来挑战自己。这使您可以建立程序记忆,就像肌肉记忆一样,并获得构建某些类型代码的经验。

  • 拼图的设计通常着眼于解决方案。它们使您可以了解和应用经过试验和测试的算法,这些算法是任何程序员工具箱的重要组成部分。

  • 对于一些谜题解决方案,如果算法效率低下,即使是最强大的超级计算机也可能太慢。您可以分析您的解决方案的性能并获得经验,以帮助您了解什么时候简单的方法足够快,什么时候需要更优化的程序。

  • 大多数编程语言都非常适合解决编程难题。这为您提供了一个很好的机会,可以针对不同的任务比较不同的编程语言。拼图也是了解新编程语言或尝试您最喜欢的语言的一些最新功能的好方法。


最重要的是,用编程难​​题挑战自己通常非常有趣!当你把所有的东西加起来时,为谜题留出一些时间是非常有益的。

探索在线解决编程难题的选项


幸运的是,您可以在许多网站上找到编程难题并尝试解决它们。这些网站存在的问题类型、您提交解决方案的方式以及网站可以提供的反馈和社区类型通常存在差异。因此,您应该花一些时间环顾四周,找到对您最有吸引力的那些。


在本教程中,您将了解代码的来临,包括您可以在那里找到什么样的谜题以及您可以使用哪些工具和技巧来解决它们。但是,您也可以在其他地方开始解决编程难题:

  • Exercism 有许多不同编程语言的学习路径。每个学习轨道都提供有关不同编程概念、编码挑战和指导者的小型教程,为您提供有关解决方案的反馈。

  • 欧拉计划已经存在很长时间了。该网站提供数百个谜题,通常以数学问题的形式表述。您可以使用任何编程语言解决问题,一旦您解决了难题,您就可以访问社区线程,在那里您可以与其他人讨论您的解决方案。

  • Code Wars 提供了大量的编码挑战,他们称之为 katas。您可以使用许多不同的编程语言通过内置编辑器和自动化测试解决难题。之后,您可以将您的解决方案与其他人的解决方案进行比较,并在论坛中讨论策略。

  • 如果您正在寻找工作,HackerRank 具有强大的功能。他们提供许多不同技能的认证,包括解决问题和 Python 编程,以及一个工作板,可让您在工作申请中展示自己的解谜技能。


还有许多其他网站可供您练习解谜技巧。在本教程的其余部分,您将重点关注 Advent of Code 必须提供的内容。

为 Code 的出现做准备:25 个圣诞节的新鲜谜题


现在是代码出现的时候了!它由 Eric Wastl 于 2015 年创立。从那时起,每年 12 月都会发布包含 25 个新编程谜题的新出现日历。这些年来,拼图变得越来越流行。自 2020 年以来,已有超过 170,000 人至少解决了其中一个难题。


注意:传统上,降临节日历是用于在等待圣诞节期间计算降临节天数的日历。多年来,降临节日历变得更加商业化并且失去了一些与基督教的联系。


大多数降临节日历从 12 月 1 日开始,到 12 月 24 日(平安夜)或 12 月 25 日(圣诞节)结束。如今,各种降临节日历应有尽有,包括乐高日历、茶日历和化妆品日历。


在传统的降临节日历中,您每天打开一扇门以显示里面的内容。Advent of Code 模仿了这一点,让您从 12 月 1 日到 12 月 25 日每天打开一个谜题。对于您解决的每个难题,您都将获得金星,您可以保留这些星星。


在本节中,您将更加熟悉 Advent of Code 并瞥见您的第一个谜题。稍后,您将了解如何解决这些难题的详细信息,并练习自己解决一些难题。

代码谜题的出现


Advent of Code 是一个在线 Advent 日历,从 12 月 1 日到 12 月 25 日,每天都会发布一个新的谜题。每个谜题都在美国东部时间午夜可用。Advent of Code 谜题有几个典型特征:

  • 每个谜题由两部分组成,但在您完成第一部分之前不会显示第二部分。

  • 每完成一个部分,您将获得一颗金星 (⭐)。这意味着如果您在一年内解决所有难题,您每天可以获得两颗星和五十颗星。

  • 每个人的谜题都是一样的,但您需要根据从 Advent of Code 网站获得的个性化输入来解决它。这意味着您对一个谜题的答案将与其他人的不同,即使您使用相同的代码来计算它。


您可以参加全球竞赛,成为第一个解决每个难题的人。然而,这里通常挤满了高技能、有竞争力的程序员。如果您将 Code of Code 用作自己的练习,或者如果您向您的朋友和同事发起小型友好竞赛,它可能会更有趣。


要了解代码出现难题的工作原理,请考虑 2020 年的第一天难题:

在你离开之前,会计精灵只需要你修正你的开支报告(你的拼图输入);显然,有些事情并没有完全加起来。

具体来说,他们需要您找到总和为的两个条目,2020 然后将这两个数字相乘。

每年,都会有一个非常愚蠢的背景故事将谜题联系在一起。2020 年的故事描述了您尝试离开去度过一个当之无愧的假期,因为您已经连续几年拯救了圣诞节。这个故事通常对谜题没有影响,但跟随它仍然很有趣。

在故事的情节元素之间,你会发现谜题本身。在此示例中,您要在拼图输入中查找总和为 2,020 的两个条目。在描述问题的解释之后,您通常会找到一个示例,显示您需要执行的计算:


例如,假设您的费用报告包含以下内容:

17219793662996751456
复制代码


在这份名单中,这两个条目总和 2020 是 1721 和 299。将它们相乘产生 1721 * 299 = 514579,所以正确答案是 514579


该示例向您展示了此特定数字列表的答案。如果您要开始解决这个难题,现在您将开始考虑如何在任何有效数字列表中找到这两个条目。但是,在深入研究这个难题之前,您将探索如何使用 Advent of Code 站点。

如何参与代码的出现


您已经看到了代码出现难题的示例。接下来,您将了解如何提交答案。您永远不会提交任何代码来解决难题。您只需提交答案,通常是数字或文本字符串。


通常,您将按照一系列步骤来解决网站上的难题:

  1. 登录 Advent of Code 网站。您可以使用来自其他服务(如 GitHub、Google、Twitter 或 Reddit)的凭据来执行此操作。

  2. 阅读拼图文字并特别注意给定的例子。您应该确保您了解示例数据的解决方案。

  3. 下载拼图的个性化输入。您将需要此输入才能找到问题的唯一答案。

  4. 编写您的解决方案。这是有趣的部分,您将在本教程的其余部分获得大量练习。

  5. 在拼图页面上输入您对拼图的答案。如果您的答案是正确的,那么您将获得一颗金星,并打开谜题的第二部分。

  6. 对拼图的第二部分重复步骤 2 到 4。第二部分与第一部分类似,但它通常会增加一些需要您调整代码的扭曲。

  7. 在拼图页面上输入您的第二个答案,以获得第二颗星并完成拼图。


请记住,您不提交任何代码——只提交您的谜题答案。这意味着可以用任何编程语言解决代码难题的出现。许多人使用 Advent of Code 来练习和学习一种新的编程语言。Advent of Code 的创建者 Eric Wastl 在 2019 年发表了一次演讲,他谈到了参与人员的不同背景和动机等。


注意:有一个 Advent of Code 的排行榜。一般来说,你应该忽略这个排行榜!它仅显示在拼图打开后谁提交了前 100 个解决方案。要想跻身排行榜,您需要大量的准备、奉献精神和竞争性编程的经验。


相反,您应该查看私人排行榜。这些在您登录后可用,它们让您有机会邀请您的朋友和同事加入更轻松的社区。您可以选择基于要么得分您的私人排行榜的困惑基础上得到解决或者干脆数量困惑的人已经解决了的。


您还可以将您在私人排行榜中的名字链接到您的 GitHub 帐户,这样您就可以与朋友分享您的解决方案。登录后,您可以通过单击 Advent of Code 站点菜单中的设置来进行设置。


Advent of Code 完全免费使用,但您仍然可以通过几种不同的方式支持该项目:

  • 您可以在您的社交媒体上分享有关 Advent of Code 的信息以宣传。

  • 您可以通过参与 r/adventofcode subreddit 或其他论坛来帮助他人

  • 您可以邀请您的朋友参加 Advent of Code,在私人排行榜上分享您的结果。

  • 您可以向 Advent of Code 捐款。如果您这样做了,那么您将在网站上的姓名旁边看到一个 AoC++徽章。


在接下来的部分中,您将看到有关如何准备使用 Python 解决代码出现问题的一些建议。还有一个很棒的列表,您可以查看与 Advent of Code 相关的许多不同资源的链接,包括许多其他人的解决方案。

用 Python 解决代码的出现


Code of Code 已成为全球许多编码人员的年度亮点。2020 年,超过 170,000 人提交了他们的解决方案。自 2015 年 Advent of Code 启动以来,已有超过 380,000 名程序员参与其中。他们中的许多人使用 Python 来解决难题。


那么,现在轮到你了!前往 Advent of Code 网站,查看最新的谜题。然后,返回本教程获取一些提示并帮助开始使用 Python 解决代码出现难题。

拼图的剖析


在本节中,您将探索代码出现难题的典型剖析。此外,您将了解一些可用于与之交互的工具。


每个 Advent of Code 谜题都分为两部分。当您开始处理拼图时,您只会看到第一部分。一旦您提交了第一部分的正确答案,第二部分就会解锁。这通常是您在第一部分解决的问题的转折点。有时,您会发现有必要从第一部分重构您的解决方案,而有时您可以根据您已经完成的工作快速解决第二部分。


两个部分始终使用相同的拼图输入。您可以从当天的拼图页面下载拼图输入。您会在拼图说明后找到一个链接。


注意:如前所述,您的拼图输入是个性化的。这意味着如果您与其他人讨论解决方案,他们的最终答案可能与您的不同。


提交拼图解决方案所需执行的所有操作(实际解决拼图除外)都可以在 Advent of Code 网站上完成。您应该使用它来提交您的第一个解决方案,以便您熟悉流程。


稍后,您可以使用多种工具来组织 Advent of Code 设置并提高工作效率。例如,您可以使用该 advent-of-code-data 包下载数据。这是一个可以使用 pip 安装的 Python 包:

$ python -m pip install advent-of-code-data
复制代码


您可以使用 advent-of-code-data 其 aocd 工具在命令行上下载特定的拼图输入集。另一个有趣的可能性是在您的 Python 代码中自动下载和缓存您的个性化拼图输入:

>>>>>> from aocd.models import Puzzle>>> puzzle = Puzzle(year=2020, day=1)
>>> # Personal input data. Your data will be different.>>> puzzle.input_data[:20]'1753\n1858\n1860\n1978\n'
复制代码


您需要在环境变量或文件中设置会话 ID,然后才能使用 advent-of-code-data. 您将在文档中找到对此的解释。如果您感兴趣,还可以使用 advent-of-code-data 或 aocd 提交您的解决方案并查看您之前的答案。


作为拼图文本的一部分,您还会发现一个或多个示例,这些示例通常是根据比您的个性化输入数据更小的数据来计算的。在开始编码之前,您应该仔细阅读这些示例,并确保您了解要求您执行的操作。


您可以使用这些示例为您的代码设置测试。一种方法是在示例数据上手动运行您的解决方案并确认您得到了预期的答案。或者,您可以使用类似工具 pytest 来自动化该过程。


注意: 测试驱动开发 (TDD)是一个在实现代码之前编写测试的过程。由于 Advent of Code 为您提供了对小示例的预期答案,因此它为您提供了自己尝试测试驱动开发的绝佳机会。


稍后当您尝试自己解决一些难题时,您将了解有关 TDD 的更多信息。


您只需使用简单的 Python 和标准库即可解决所有 Advent of Code 难题。但是,有一些软件包可以帮助您整理解决方案:

  • advent-of-code-data 可以下载您的输入数据并提交您的解决方案。

  • pytest 可以自动检查示例数据上的解决方案。

  • parse 可以用比正则表达式更简单的语法来解析字符串。

  • numpy 可以有效地计算数字数组。

  • colorama 可以在终端中为您的解决方案设置动画。


如果您创建了一个虚拟环境并安装了这些包,那么您将拥有一个非常可靠的工具箱,用于您的 Advent of Code 冒险。后来,你会看到你如何使用的例子 parse,numpy 和 colorama 解决难题。

解决方案的结构


在上一节中,您熟悉了如何阅读和理解 Advent of Code 谜题。在本节中,您将了解如何解决这些问题。在解决“代码出现”难题之前,您无需进行大量设置。


你有没有想过如何解决你之前看到的难题?回想一下,您正在查找列表中总和为 2,020 的两个数字的乘积。在继续之前,请考虑——也许可以编写代码——如何找到以下列表中哪两个条目的总和为 2,020:

numbers = [1721, 979, 366, 299, 675, 1456]
复制代码


以下脚本显示了解决 2020 年第 1 天难题的第一部分的一种方法:

 1for num1 in numbers: 2    for num2 in numbers: 3        if num1 < num2 and num1 + num2 == 2020: 4            print(num1 * num2)
复制代码


嵌套 for 循环从列表中查找两个数字的所有组合。第 3 行的测试实际上比实际需要的稍微复杂一些:您只需要测试数字总和是否为 2,020。但是,通过添加 num1 应该小于的条件,num2 可以避免两次找到解。


在这个例子中,一个解决方案的模样 num1 = 1721 和 num2 = 299,但因为你可以以任何顺序添加数字,这意味着还 num1 = 299 和 num2 = 1721 形成的解决方案。通过额外检查,仅报告后一种组合。


一旦你有了这个解决方案,你就可以将你的个性化输入数据复制到 numbers 列表中并计算你的谜题答案。


注意:有比尝试所有可能性更有效的方法来计算这个答案。但是,从基本方法开始通常是个好主意。引用乔·阿姆斯特朗的话说:

让它工作,然后让它漂亮,然后如果你真的,真的必须,让它快。90% 的情况下,如果你让它漂亮,它已经很快了。所以真的,只是让它漂亮!—乔·阿姆斯特朗

既然你已经看到了这个谜题的有效解决方案,你能把它做得漂亮吗?


当您解决更多难题时,您可能会开始觉得将数据复制到代码中并将其重写为有效的 Python 变得很烦人。类似地,向代码中添加一些函数可为您提供更大的灵活性。例如,您可以使用它们向代码中添加测试。


Python 有许多强大的字符串解析功能。从长远来看,最好在下载时保留输入数据,让 Python 将它们解析为可用的数据结构。事实上,将代码分成两个函数通常是有益的。一个函数将解析字符串输入,另一个函数将解决这个难题。基于这些原则,你可以重写你的代码:

 1# aoc202001.py 2 3import pathlib 4import sys 5 6def parse(puzzle_input): 7    """Parse input""" 8    return [int(line) for line in puzzle_input.split()] 910def part1(numbers):11    """Solve part 1"""12    for num1 in numbers:13        for num2 in numbers:14            if num1 < num2 and num1 + num2 == 2020:15                return num1 * num21617if __name__ == "__main__":18    for path in sys.argv[1:]:19        print(f"\n{path}:")20        puzzle_input = pathlib.Path(path).read_text().strip()2122        numbers = parse(puzzle_input)23        print(part1(numbers))
复制代码


在第 12 到 15 行,您将识别出您之前的解决方案。首先,您已将其包装在一个函数中。这使得以后更容易向代码中添加自动测试。您还添加了一个 parse()函数,可以将字符串行转换为数字列表。


在第 20 行,您用于 pathlib 将文件内容作为文本读取并去除末尾的所有空白行。循环 sys.argv 为您提供在命令行中输入的所有文件名。


在您处理解决方案时,这些更改为您提供了更大的灵活性。假设您已将示例数据存储在名为 的文件中,example.txt 并将您的个性化输入数据存储在名为 input.txt. 然后,您可以通过在命令行上提供它们的名称,在其中任何一个或什至两者上运行您的解决方案:

$ python aoc202001.py example.txt input.txtexample.txt:514579
input.txt:744475
复制代码


514579 确实是使用示例输入数据时问题的答案。请记住,您的个性化输入数据的解决方案将与上面显示的解决方案不同。


现在是时候让 Advent of Code 网站一展身手了!转到 2020 Advent of Code 日历并找到第 1 天的谜题。如果您还没有,请下载输入数据并计算谜题的解决方案。然后,在网站上输入您的解决方案并点击提交。

起始模板


正如您在上面看到的,代码谜题的出现遵循一套结构。因此,为自己创建一个模板是有意义的,您可以在开始编写解决方案时将其用作起点。您在这样的模板中到底想要多少结构是个人品味的问题。首先,您将探索一个基于您在上一节中看到的原则的模板示例:

 1# aoc_template.py 2 3import pathlib 4import sys 5 6def parse(puzzle_input): 7    """Parse input""" 8 9def part1(data):10    """Solve part 1"""1112def part2(data):13    """Solve part 2"""1415def solve(puzzle_input):16    """Solve the puzzle for the given input"""17    data = parse(puzzle_input)18    solution1 = part1(data)19    solution2 = part2(data)2021    return solution1, solution22223if __name__ == "__main__":24    for path in sys.argv[1:]:25        print(f"{path}:")26        puzzle_input = pathlib.Path(path).read_text().strip()27        solutions = solve(puzzle_input)28        print("\n".join(str(solution) for solution in solutions))
复制代码


该模板具有用于解析输入以及解决谜题的两个部分的单独函数。您根本不需要触及第 15 到 27 行。他们照顾的阅读文本从输入文件,要求 parse(),part1()和 part2(),然后再报告解决方案控制台。


您可以创建一个类似的模板来测试您的解决方案。


注意:如前所述,示例数据对于创建测试很有用,因为它们代表具有相应解决方案的已知数据。

以下模板 pytest 用作测试运行程序。它的三个不同的测试,每一个功能的准备 parse(),part1()以及 part2():

 1# test_aoc_template.py 2 3import pathlib 4import pytest 5import aoc_template as aoc 6 7PUZZLE_DIR = pathlib.Path(__file__).parent 8 9@pytest.fixture10def example1():11    puzzle_input = (PUZZLE_DIR / "example1.txt").read_text().strip()12    return aoc.parse(puzzle_input)1314@pytest.fixture15def example2():16    puzzle_input = (PUZZLE_DIR / "example2.txt").read_text().strip()17    return aoc.parse(puzzle_input)1819@pytest.mark.skip(reason="Not implemented")20def test_parse_example1(example1):21    """Test that input is parsed properly"""22    assert example1 == ...2324@pytest.mark.skip(reason="Not implemented")25def test_part1_example1(example1):26    """Test part 1 on example input"""27    assert aoc.part1(example1) == ...2829@pytest.mark.skip(reason="Not implemented")30def test_part2_example2(example2):31    """Test part 2 on example input"""32    assert aoc.part2(example2) == ...
复制代码


你会看到,你如何使用这个模板的例子以后。在此之前,您应该注意以下几点:

  • 如第 1 行所示,您应该 pytest 使用 test_前缀命名您的文件。

  • 类似地,每个测试都在一个以 test_前缀命名的函数中实现。您可以在第 20、25 和 30 行看到这些示例。

  • 您应该更改第 5 行的导入以导入您的解决方案代码。

  • 该模板假定示例数据存储在名为 example1.txt 和 的文件中 example2.txt。

  • 当您准备好开始测试时,您应该删除第 19、24 和 29 行的跳过标记。

  • 您需要...根据示例数据和相应的解决方案填写第 22、27 和 32 行的省略号 ( )。


例如,如果您要将此模板改编为上一节中 2020 年第 1 天谜题第一部分的重写解决方案,则您需要创建一个 example1.txt 包含以下内容的文件:

17219793662996751456
复制代码


接下来,您将删除前两个测试的跳过标记并按如下方式实现它们:

def test_parse_example1(example1):    """Test that input is parsed properly"""    assert example1 == [1721, 979, 366, 299, 675, 1456]
def test_part1_example1(example1): """Test part 1 on example input""" assert aoc.part1(example1) == 514579
复制代码


最后,您需要确保您正在导入您的解决方案。如果您使用了 filename aoc202001.py,那么您应该将第 5 行更改为 import aoc202001:

 5import aoc202001 as aoc
复制代码


然后,您将运行 pytest 以检查您的解决方案。如果您正确地实施了您的解决方案,那么您会看到如下内容:

$ pytest====================== test session starts =====================collected 3 items
test_aoc202001.py ..s [100%]================= 2 passed, 1 skipped in 0.02s =================
复制代码


注意... 前面的两个点 ( ) s。它们代表两个通过的测试。如果测试失败,您会看到 F 而不是每个点,以及出现问题的详细说明。


Cookiecutter 和 Copier 等工具可以更轻松地处理此类模板。如果您安装了 Copier,那么您可以通过运行以下命令来使用类似于您在此处看到的模板:

$ copier gh:gahjelle/template-aoc-python advent_of_code
复制代码


这将为 advent_of_code 您计算机上目录的子目录中的一个特定拼图设置模板。

解决策略


代码谜题的出现非常多样化。随着日历的推进,您将解决许多不同的问题,并发现许多解决这些问题的不同策略。


其中一些策略非常通用,可以应用于任何谜题。如果您发现自己被一个谜题卡住了,您可以尝试解决以下问题:

  • 重新阅读说明。代码谜题的出现通常非常明确,但其中一些可能包含大量信息。确保您没有遗漏拼图的重要部分。

  • 积极使用示例数据。确保您了解这些结果是如何实现的,并检查您的代码是否能够重现这些示例。

  • 一些谜题可能会涉及一些。将问题分解为更小的步骤,并单独实施和测试每个步骤。

  • 如果您的代码适用于示例数据但不适用于您的个性化输入数据,那么您可以根据您能够手动计算的数字构建其他测试用例,以查看您的代码是否涵盖所有极端情况。

  • 如果您仍然被卡住,那么在一些致力于代码出现的论坛上与您的朋友和其他解谜者联系,并询问他们如何解决谜题的提示。


随着您做越来越多的谜题,您将开始认识到一些反复出现的一般谜题。


一些谜题涉及文本和密码。Python 有几个强大的工具来处理文本字符串,包括许多字符串方法。要读取和解析字符串,了解正则表达式的基础知识会很有帮助。但是,您通常也可以使用第三方 parse 库。


例如,假设您有字符串"shiny gold bags contain 2 dark red bags."并希望从中解析相关信息。您可以使用 parse 及其模式语法:

>>>>>> import parse>>> string = "shiny gold bags contain 2 dark red bags.">>> pattern = "{outer_color} bags contain {num:d} {inner_color} bags.">>> match = parse.search(pattern, string)>>> match.named{'outer_color': 'shiny gold', 'num': 2, 'inner_color': 'dark red'}
复制代码


在后台,parse 构建一个正则表达式,但您使用类似于 f-strings 使用的语法的更简单的语法。


在其中一些文本问题中,明确要求您使用代码和解析器,通常构建小型自定义汇编语言。解析完代码后,通常需要运行给定的程序。实际上,这意味着您构建了一个小型状态机,可以跟踪其当前状态,包括其内存的内容。


您可以使用类将状态与行为保持在一起。在 Python 中,数据类非常适合快速设置状态机。以下示例显示了一个可以处理两种不同指令的小型状态机的实现:

 1from dataclasses import dataclass 2 3@dataclass 4class StateMachine: 5    memory: dict[str, int] 6    program: list[str] 7 8    def run(self): 9        """Run the program"""10        current_line = 011        while current_line < len(self.program):12            instruction = self.program[current_line]1314            # Set a register to a value15            if instruction.startswith("set "):16                register, value = instruction[4], int(instruction[6:])17                self.memory[register] = value1819            # Increase the value in a register by 120            elif instruction.startswith("inc "):21                register = instruction[4]22                self.memory[register] += 12324            # Move the line pointer25            current_line += 1
复制代码


这两个指令 set 并 inc 进行分析和内处理.run()。请注意,第 5 行和第 6 行的类型提示使用更新的语法,该语法仅适用于 Python 3.9 及更高版本。如果您使用的是旧版本的 Python,那么您可以使用 importDict 和 Listfromtyping 代替。


要运行您的状态机,您首先使用初始内存对其进行初始化并将程序加载到机器中。接下来,您调用.run(). 程序完成后,您可以检查.memory 以查看机器的新状态:

>>>>>> state_machine = StateMachine(...     memory={"g": 0}, program=["set g 44", "inc g"]... )>>> state_machine.run()>>> state_machine.memory{'g': 45}
复制代码


该程序首先设置 g 为 的值 44,然后增加它,使其最终值为 45。


一些有趣的谜题涉及网格和迷宫。如果您的网格具有固定大小,那么您可以使用 NumPy 来获得它的有效表示。迷宫通常有助于可视化。您可以使用 Colorama 直接在您的终端中绘制:

import numpy as npfrom colorama import Cursor
grid = np.array( [ [1, 1, 1, 1, 1], [1, 0, 0, 0, 1], [1, 1, 1, 0, 1], [1, 0, 0, 2, 1], [1, 1, 1, 1, 1], ])
num_rows, num_cols = grid.shapefor row in range(num_rows): for col in range(num_cols): symbol = " #o"[grid[row, col]] print(f"{Cursor.POS(col + 1, row + 2)}{symbol}")
复制代码


此脚本显示了使用 NumPy 数组存储网格,然后使用 Cursor.POSfrom Colorama 在终端中定位光标以打印出网格的示例。运行此脚本时,您将看到如下输出:

######   #### ##  o######
复制代码


在运行时可视化您的代码可能很有趣,并且还可以为您提供一些很好的见解。当您在调试并且不太了解正在发生的事情时,它也可以是非常宝贵的帮助。


到目前为止,在本教程中,您已经获得了一些关于如何使用 Advent of Code 谜题的一般提示。在接下来的部分中,您将获得更明确的信息并解决早年的两个难题。

代码实践:2019 年第 1 天


您将尝试自己解决的第一个难题是 2019 年第 1 天,称为火箭方程式的暴政。这是一个典型的第 1 天难题,因为该解决方案并不是很复杂。这是一个很好的练习,可以习惯 Advent of Code 的工作方式并检查您的环境是否已正确设置。

第 1 部分:拼图说明


在 2019 年的故事情节中,你将拯救被困在太阳系边缘的圣诞老人。在第一个谜题中,您正在准备发射火箭:

精灵们迅速将您装入宇宙飞船并准备发射。

在第一次 Go / No Go 民意调查中,每个 Elf 都是 Go,直到 Fuel Counter-Upper。他们还没有确定所需的燃料量。

发射给定模块所需的燃料基于其质量。具体来说,要找到模块所需的燃料,取其质量,除以 3,向下取整,然后减去 2。


示例数据如下所示:

  • 对于质量 12,除以 3 并向下取整得到 4,然后减去 2 得到 2。

  • 对于质量 14,除以 3 并四舍五入仍然产生 4,因此所需的燃料也是 2。

  • 对于质量为 1969,所需的燃料为 654。

  • 对于质量为 100756,所需的燃料为 33583。


您需要计算航天器的总燃料需求:

Fuel Counter-Upper 需要知道总燃料需求。要找到它,请单独计算每个模块(您的拼图输入)的质量所需的燃料,然后将所有燃料值加在一起。

您的航天器上所有模块的燃料需求总和是多少?

现在是时候尝试自己解决难题了!下载您的个性化输入数据并在 Advent of Code 上检查您的解决方案可能是最有趣的,这样您就可以获得星星。但是,如果您还没有准备好登录 Advent of Code,请根据上面提供的示例数据随意解决难题。

第 1 部分:解决方案


完成拼图并获得星星后,您可以展开折叠块以查看拼图解决方案的讨论:

2019 年第 1 天的解决方案,第 1 部分显示隐藏

您现在已经解决了谜题的第一部分。但是,在进入谜题的第二部分之前,下一部分将展示如何使用之前在解决此问题时看到的模板。

第 1 部分:使用模板的解决方案


展开下面的折叠块,查看 2019 年第 1 天代码出现难题第一部分的另一个解决方案——这次使用您之前看到的模板来组织代码并简化测试:

2019 年第 1 天第 1 部分的模板化解决方案显示隐藏

您现在可以继续进行拼图的第二部分。你准备好扭转了吗?

第 2 部分:拼图说明


每个 Advent of Code 谜题都由两部分组成,只有在您解决第一部分后才会显示第二部分。第二部分始终与第一部分相关,并将使用相同的输入数据。但是,您可能经常需要重新考虑解决谜题前半部分的方法,以便考虑后半部分。


展开下面折叠的块以查看 2019 年第 1 天代码出现难题的第二部分:

2019 年第 1 天,第 2 部分显示隐藏

您将在下一部分看到第二部分的可能解决方案。但是,请先尝试自己解决难题。如果您需要开始的提示,请展开下面的框:

2019 年第 1 天的提示,第 2 部分显示隐藏

你怎么做的?你的火箭准备好发射了吗?

第 2 部分:解决方案


本节展示了如何解决第二部分,继续使用上面看到的模板:

2019 年第 1 天的解决方案,第 2 部分显示隐藏

恭喜!您现在已经解决了整个 Advent of Code 难题。您准备好迎接更具挑战性的挑战了吗?

代码实践:2020 年第 5 天


您将尝试解决的第二个难题是 2020 年第 5 天的难题,称为 Binary Boarding。这个谜题比前一个更具挑战性,但最终的解决方案不需要很多代码。首先查看第一部分的拼图说明。

第 1 部分:拼图说明


2020 年,您正在努力前往您当之无愧的度假胜地。在第 5 天,当麻烦接踵而至时,您将要登机:

你登上飞机却发现一个新问题:你丢了登机牌!你不确定哪个座位是你的,所有的空乘人员都忙着处理突然通过护照检查的人潮。


您编写了一个快速程序,使用手机的摄像头扫描附近的所有登机牌(您的拼图输入);也许你可以通过淘汰的过程找到你的座位。


这家航空公司使用二元空间分区来安排座位,而不是区域或组。一个座位可能被指定为 FBFBBFFRLR,其中的 F 意思是“前”,B 意思是“后”,L 意思是“左”,R 意思是“右”。


前 7 个字符将是 F 或 B; 这些精确指定的一个 128 行上的平面(编号 0 通过 127)。每个字母都会告诉您给定的座位位于区域的哪一半。


从整个行列表开始;第一个字母表示座位是在前面(0 通过 63)还是在后面(64 通过 127)。下一个字母表示座位位于该区域的哪一半,依此类推,直到您只剩下一排。


例如,仅考虑 的前七个字符 FBFBBFFRLR:

  • 首先考虑整个范围,行 0 到 127.

  • F 意味着采取下半部分,保持行 0 通过 63。

  • B 意味着采取上半部分,保持行 32 通过 63。

  • F 意味着采取下半部分,保持行 32 通过 47。

  • B 意味着采取上半部分,保持行 40 通过 47。

  • B 保持行 44 通过 47。

  • F 保持行 44 通过 45。

  • finalF 保留两者中较低的,row44


最后三个字符将是 L 或 R; 这些精确指定的一个 8 列的在飞机上的座位(编号 0 通过 7)。再次进行与上述相同的过程,这次只需要三个步骤。L 表示保留下半部分,同时 R 表示保留上半部分


例如,仅考虑 的最后 3 个字符 FBFBBFFRLR:

  • 首先考虑整个范围,列 0 到 7.

  • R 意味着采取上半部分,保持列 4 通过 7。

  • L 意味着采取下半部分,保持列 4 通过 5。

  • finalR 保留两者中的较高者,column5


因此,解码 FBFBBFFRLR 显示它是 row 44, column5 的座位。

每个座位也有一个唯一的座位 ID:将行乘以 8,然后添加列。在此示例中,座位具有 ID 44 * 8 + 5 = 357


以下是其他一些登机牌:

  • BFFFBBFRRR:行 70,列 7,座位 ID 567。

  • FFFBBBFRRR:行 14,列 7,座位 ID 119。

  • BBFFBBFRLL:行 102,列 4,座位 ID 820。


作为健全性检查,请查看您的登机牌清单。登机牌上的最高座位 ID 是多少?

这个谜题说明中有很多信息!但是,大部分内容都涉及二进制空间分区如何为该特定航空公司工作。

现在,尝试自己解决难题!请记住,如果您从正确的角度考虑,从登机牌规范到座位 ID 的转换并不像最初看起来那么复杂。如果您发现自己在该部分遇到困难,请展开下面的框以查看有关如何开始的提示。

2020 年第 5 天的提示,第 1 部分显示隐藏

完成解决方案后,请查看下一部分以了解有关该难题的讨论。

第 1 部分:解决方案


既然您已经自己试过了,您可以继续展开以下块以查看解决难题的一种方法:

2020 年第 5 天的解决方案,第 1 部分显示隐藏

是时候进入拼图的第二部分了。你能登机吗?

第 2 部分:拼图说明


准备好拼图的第二部分后,展开以下部分:

2020 年第 5 天,第 2 部分显示隐藏

花点时间研究第二部分的解决方案。

第 2 部分:解决方案


当您准备好将您的解决方案与另一个解决方案进行比较时,请打开下面的框:

2020 年第 5 天的解决方案,第 2 部分显示隐藏

恭喜!到目前为止,您已经解决了至少两个 Advent of Code 难题。幸运的是,还有数百个等着你!


点击关注,第一时间了解华为云新鲜技术~

发布于: 2 小时前阅读数: 7
用户头像

提供全面深入的云计算技术干货 2020.07.14 加入

华为云开发者社区,提供全面深入的云计算前景分析、丰富的技术干货、程序样例,分享华为云前沿资讯动态,方便开发者快速成长与发展,欢迎提问、互动,多方位了解云计算! 传送门:https://bbs.huaweicloud.com/

评论

发布
暂无评论
编程谜题:提升你解决问题的训练场