如何在地图中追踪步骤，代码降临 ay 6

回到我的 Advent of Code 挑战，由于一些不可预见的问题，我无法及时完成挑战，目前大约落后了 5-6 天。不过，我仍然决心今年一定要完成拼图。今天我们来讨论第六个谜题。

副驾驶生成的图像有点适合主题

在 2D 平面中寻找事物似乎是今年反复出现的主题。今天，我们正在追踪一名具有清晰、明确的运动逻辑的警卫的脚步。守卫直线移动，遇到阻碍时右转。

假设我们将守卫所采取的每一步表示为 2D 平面中的一个点，那么我们可以将不同方向上的每一步表示为向量：

LEFT = (1, 0)
RIGHT = (-1, 0)
UP = (0, -1)
DOWN = (0, 1)

通过执行如下所示的一些计算，我们得到一个代表右旋转的矩阵

推导旋转矩阵

最初，它被表示为字典，因为我们将严重依赖它来进行大量计算。但是，我想确保正确的类型注释，因此现在采用此实现。

class Rotation:
    c0r0: int
    c1r0: int
    c0r1: int
    c1r1: int

@dataclass(frozen=True)
class RotateRight(Rotation):
    c0r0: int = 0
    c1r0: int = 1
    c0r1: int = -1
    c1r1: int = 0

我们还需要一种表示位置和运动的方法，以及操纵位置和执行旋转的方法：

from __future__ import annotations

@dataclass(frozen=True)
class Point:
    x: int
    y: int

    def __add__ (self, direction: Direction) -> Point:
        return Point(self.x + direction.x, self.y + direction.y)

@dataclass
class Direction:
    x: int
    y: int

    def __mul__ (self, rotation: Rotation) -> Direction:
        return Direction(
            self.x * rotation.c0r0 + self.y * rotation.c0r1,
            self.x * rotation.c1r0 + self.y * rotation.c1r1,
        )

定义 dunder/magic 方法 __add__ 和 __mul__ 使 Point 和 Direction 对象都可以像代码中的标准算术运算一样进行操作。该代码片段还演示了如何有效地对 Rotation 类进行类型注释。

最后，我们定义输入的模型：

class Symbol(Enum):
    Guard = "^"
    Obstruction = "#"

@dataclass
class Space:
    pass

@dataclass
class Guard:
    pass

@dataclass
class Obstruction:
    pass

@dataclass
class Board:
    tiles: dict[Point, Space | Guard | Obstruction]
    width: int
    height: int

Symbol 是一个标准枚举，它封装了输入中各种符号的含义。空间、守卫和障碍具有不言自明的含义。 Board 是地图的表示。我最初的方法涉及更面向对象的设计，但我最终选择了这种实现，其中每个类只维护一个可以轻松检查的状态。

让我们从解析输入开始：

def finder(board: tuple[str, ...], symbol: Symbol) -> Generator[Point, None, None]:
    return (
        Point(x, y)
        for y, row in enumerate(board)
        for x, item in enumerate(tuple(row))
        if item == symbol.value
    )

def parse(input: str) -> tuple[Board, Point]:
    board = tuple(input.strip().splitlines())

    return (
        Board(
            {point: Obstruction() for point in finder(board, Symbol.Obstruction)},
            len(board[0]),
            len(board),
        ),
        next(finder(board, Symbol.Guard)),
    )

守卫由 Point 对象表示。查找功能负责扫描输入并识别所需符号的位置。类似的 2D 地图解析解决方案将在后续帖子中继续探索。

我的第 1 部分的解决方案相对简单。计算守卫的下一步：

1. 根据当前方向向量确定守卫正前方所需的目的地。
2. 检查想要的目的地是否有障碍。
3. 如果想要的目的地被遮挡：我们返回想要的目的地，以及当前的方向向量。
4. 如果所需的目的地没有被阻挡：我们返回当前位置和旋转的方向向量。

LEFT = (1, 0)
RIGHT = (-1, 0)
UP = (0, -1)
DOWN = (0, 1)

最后，我们解决挑战的第 1 部分，这需要确定警卫访问过的唯一图块的数量。

class Rotation:
    c0r0: int
    c1r0: int
    c0r1: int
    c1r1: int

@dataclass(frozen=True)
class RotateRight(Rotation):
    c0r0: int = 0
    c1r0: int = 1
    c0r1: int = -1
    c1r1: int = 0

第 2 部分向我们抛出了一个曲线球！我们的任务是找到在地图上放置新物体的完美位置，以使我们的机器人永远循环巡逻。

好消息是，找到合适的地点并不是什么难事。我们从第 1 部分中知道机器人的初始路径，因此我们只需将物体放置在该路线沿线的某个位置即可。

现在，棘手的部分：我们如何知道我们是否已成功创建循环？

这是我的方法：

1. 跟踪机器人的动作：我没有跟踪它的确切位置，而是专注于记录它所采取的每一个“步骤”。每一步基本上都是从一个图块移动到下一个图块。
2. 寻找重复模式：如果机器人开始重复相同的步骤序列，我们就有了一个循环！
3. 确保它留在地图上：至关重要的是，我们需要确保机器人不会偏离地图。

from __future__ import annotations

@dataclass(frozen=True)
class Point:
    x: int
    y: int

    def __add__ (self, direction: Direction) -> Point:
        return Point(self.x + direction.x, self.y + direction.y)

@dataclass
class Direction:
    x: int
    y: int

    def __mul__ (self, rotation: Rotation) -> Direction:
        return Direction(
            self.x * rotation.c0r0 + self.y * rotation.c0r1,
            self.x * rotation.c1r0 + self.y * rotation.c1r1,
        )

我选择将步骤存储在字典中的原因是步骤的顺序对于问题的这一部分并不重要（这暗示了后面的谜题中的类似概念）。

由于我需要经常检查特定步骤是否已经发生，因此将步骤存储在字典中可以显着提高性能。 Python 中的字典的查找速度非常快，与使用列表或元组相比，这些检查速度要快得多。

我最初的尝试使用了不同的数据结构，在我机器的所有 8 个核心上运行大约需要 70 秒。通过切换到字典，我能够将运行时间显着缩短到几秒钟。这证明了为手头的任务选择正确的数据结构的力量！

今天就这样。考虑到运行时间从所有核心上的 70 秒缩短到单个核心上的几秒，我对优化感到非常满意，尽管我知道进一步的改进是可能的（理想的目标是亚秒级执行）。

我之前找工作的尝试并没有得到很好的结果（是的，仍然是#OpenToWork，请联系我！），因为我拒绝了额外作业/测试的请求，且没有任何补偿。希望明年情况会显着改善，下周我会再写。

以上是如何在地图中追踪步骤，代码降临 ay 6的详细内容。更多信息请关注PHP中文网其他相关文章！