如何在地圖中追蹤步驟，代碼降臨 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中文網其他相關文章！