マップ内のステップをトレースする方法、Advent of Code ay 6

Advent of Code チャレンジの話に戻りますが、予期せぬ問題が発生したため、時間内にチャレンジを完了することができず、現在約 5 ～ 6 日遅れています。しかし、私は今年もパズルを完成させる決意をしています。今日は、6 番目のパズルについて説明しましょう。

Copilot が生成した、テーマにある程度適合する画像

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,
        )

ダンダー/マジック メソッド __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 は、入力内のさまざまなシンボルの意味をカプセル化する標準の列挙型です。スペース、ガード、オブストラクションの意味は一目瞭然です。ボードはマップを表現したものです。私の最初のアプローチには、よりオブジェクト指向の設計が含まれていましたが、最終的には、各クラスが簡単に検査できる状態を維持するこの実装を選択しました。

入力を解析することから始めましょう:

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 秒から単一コアでのわずか数秒へのランタイムの改善を考慮すると、最適化には非常に満足していますが、さらなる改善の可能性があることはわかっています (理想的には 1 秒未満の実行を目指します)。

仕事の採点を試みた前回の試みは、報酬なしで追加の課題/テストのリクエストを拒否したため、うまく終わりませんでした (はい、それでも #OpenToWork を送信してください!)。来年は状況が大幅に改善されることを願っています。また来週も書きます。

以上がマップ内のステップをトレースする方法、Advent of Code ay 6の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。