代码日到来键盘难题

第 21 天：键盘难题

GitHub 存储库 - 解决方案

今天的挑战很难，我花了两天时间才解决，也完全理解了逻辑。今年我发现，我很难理解这些说明的意图。

我希望您像我一样从这个挑战和解决方案中学到了一些东西。我发现每年参加“Advent of Code”，我都会学到很多东西，这就是为什么我喜欢尝试不同的语言或推动自己走出舒适区。我认为 Advent of Code 更多的是一个学习/发展的机会，开发者应该分享他们的知识和想法，而不是仅仅将其视为一场竞赛。

今天再次尝试 Python，我对这个解决方案很满意。我今天学到的东西是；在类声明上使用 @dataclass(frozen=True) 注释的不可变类。

我创建了 Location 类作为辅助类来导航和更新坐标（有点像我之前在某些 C# 解决方案中使用 Point 类所做的那样。

作为具有 C# / .Net 强类型背景的人，我尝试在代码中添加类型，以帮助我可视化在这个复杂问题中我正在处理的内容。我在编写 TypeScript 时也习惯这样做，所以几乎是第二天性。

今天的问题

**第一部分**介绍了导航和控制多个机器人以将指令传递给下一个机器人以在数字键盘上输入代码的问题。

第二部分通过一系列机器人和方向键盘增加复杂性来解决这个问题，展示了多级依赖关系的指数性质。

演练

由于我们已经知道方向和键盘的布局，我们可以构建所有位置映射和他们可以移动的方向的字典。

缓存（cache 和 move_cache）

缓存：存储之前计算的最短序列，以避免冗余计算，提高性能。

moves_cache：存储键盘上任意两个按钮之间的所有有效移动序列，预先计算以便快速查找。

最短长度计算（shortest_length）

递归计算输入给定代码的最短按键顺序。

通过迭代级别 (cur_深度) 直至极限 (深度_限制) 来处理键盘的多级链接。

*在位置之间移动 (moves_ Between_positions)
*

计算键盘上两个按钮之间的所有有效运动序列，确保机器人不会通过指向无效位置（间隙）来恐慌。

缓存初始化（create_cache_moves）

预先计算数字键盘和方向键盘上所有按钮对的有效移动序列，从而节省运行时计算。

求解函数，然后循环输入，通过将序列长度乘以代码的数字部分来计算其复杂性，然后根据谜题的要求简单地总结所有代码的复杂性。

排列

排列有什么作用？

Python 中的排列函数（来自 itertools 模块）生成项目集合的所有可能的有序排列。

例如：

from itertools import permutations

items = ['a', 'b', 'c']
list(permutations(items))

这将产生：

[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

每个排列都是一个唯一的序列，包含原始集合中的所有项目，但顺序不同。

为什么使用排列而不是组合？

排列：

生成项目集合的所有可能的有序排列。
项目的顺序很重要。

然而，
组合：

生成项目集合的所有可能的无序选择。

项目的顺序并不重要。

为什么顺序在这种情况下很重要？

键盘导航：每次移动后，机器人在键盘上的位置都会发生变化，因此执行移动的顺序会直接影响结果。

有效移动检查： 该功能检查导航过程中中间位置的有效性。更改移动顺序可能会导致无效路径。

组合何时有用？

在移动顺序无关紧要的情况下或者您选择移动或按钮的子集而不关心其顺序的情况下，组合可能很有用。

当前使用排列是必要的，因为移动顺序对于键盘导航很重要。用组合替换它会破坏程序的逻辑。如果任务需要找到所有独特的动作或按键组（无论顺序如何），那么组合会更合适。

这个难题中最困难的部分是想出一种漂亮而干净的方法来跟踪机器人指令的深度（初始）级别——花了我一些时间，以便我可以全神贯注于它。

以上是代码日到来键盘难题的详细内容。更多信息请关注PHP中文网其他相关文章！