深さ優先探索の丘を登る、Advent of Code 10 日目

今日のチャレンジは、6 日目と似た 2D グリッドである 10 日目のパズルに取り組みますが、複数のパスの探索が必要です。 このパズルは、深さ優先検索 (DFS) の能力をエレガントに示しています。

AI が生成したパズルのイラスト

マップは辞書として表現されます。キーは (x, y) 座標で、値は高さを示す 1 桁の整数 (0 ～ 9) で、9 がピークを表します。 解析関数は次のデータ構造を効率的に処理します:

def parse(input: str) -> dict[tuple[int, int], int | None]:
    return {
        (x, y): int(item) if item.isdigit() else None
        for y, row in enumerate(input.strip().splitlines())
        for x, item in enumerate(row)
    }

トレイルは登山口 (高さ 0) から頂上 (高さ 9) まで上昇し、1 歩ごとに正確に 1 ずつ高さが増加します。 next_step 関数は、有効な次のステップを識別します:

TRAIL_MAX = 9

def next_step(
    topo_map: dict[tuple[int, int], int | None], x: int, y: int
) -> tuple[tuple[int, int], ...]:
    assert topo_map[(x, y)] != TRAIL_MAX

    return tuple(
        incoming
        for incoming in (
            (x + 1, y),
            (x, y + 1),
            (x - 1, y),
            (x, y - 1),
        )
        if (
            isinstance(topo_map.get(incoming), int)
            and isinstance(topo_map.get((x, y)), int)
            and (topo_map[incoming] - topo_map[(x, y)] == 1)
        )
    )

Trailhead (高さ 0) は、find_trailheads:

を使用して配置されます。

TRAILHEAD = 0

def find_trailheads(
    topo_map: dict[tuple[int, int], int | None],
) -> tuple[tuple[int, int], ...]:
    return tuple(key for key, value in topo_map.items() if value == TRAILHEAD)

ソリューションの中核は、深さ優先検索を実装する climb 関数です。 Wikipedia の DFS の定義に従って、後戻りする前に各ブランチを完全に調査します。

深さ優先検索の視覚的表現

マップポイントは私たちの「ノード」であり、一度に 1 つの高さレベルを登ります。 climb 関数は DFS プロセスを管理します:

def climb(
    topo_map: dict[tuple[int, int], int | None], trailheads: tuple[tuple[int, int], ...]
) -> dict[
    tuple[tuple[int, int], tuple[int, int]], tuple[tuple[tuple[int, int], ...], ...]
]:
    candidates: list[tuple[tuple[int, int], ...]] = [(head,) for head in trailheads]

    result = {}

    while candidates:
        current = candidates.pop()
        while True:
            if topo_map[current[-1]] == TRAIL_MAX:
                result[(current[0], current[-1])] = result.get(
                    (current[0], current[-1]), ()
                ) + (current,)
                break

            elif steps := next_step(topo_map, *current[-1]):
                incoming, *rest = steps

                candidates.extend([current + (step,) for step in rest])

                current = current + (incoming,)
            else:
                break

    return result

else 句の break は行き止まりを処理し、無限ループを防ぎます。 この関数は、各登山口から山頂までのすべてのパスを返します。

パート 1 では、固有のピーク目的地をカウントします:

def part1(input: str) -> int:
    topo_map = parse(input)

    return len(climb(topo_map, find_trailheads(topo_map)))

パート 2 では、すべての一意のパスをカウントします:

def part2(input: str) -> int:
    topo_map = parse(input)

    return sum(
        len(routes) for routes in climb(topo_map, find_trailheads(topo_map)).values()
    )

代替アプローチ (例: トレイルヘッド検出を解析に統合する) は存在しますが、このソリューションのパフォーマンスは許容範囲内です。 最近の就職活動の挫折は私の気持ちを弱めませんでした。私はまだ希望を持っています。 中上級の Python 開発者をお探しの場合は、お問い合わせください。 来週まで！

以上が深さ優先探索の丘を登る、Advent of Code 10 日目の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。