深さ優先探索の丘を登る、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 サイトの他の関連記事を参照してください。

ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

SublimeText3 中国語版
中国語版、とても使いやすい

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SublimeText3 Mac版
神レベルのコード編集ソフト(SublimeText3)

ホットトピック











fiddlereveryversings for the-middleの測定値を使用するときに検出されないようにする方法

10時間以内にコンピューター初心者プログラミングの基本を教える方法は?コンピューター初心者にプログラミングの知識を教えるのに10時間しかない場合、何を教えることを選びますか...

Pythonasyncioについて...

Investing.comの反クラウリング戦略を理解する多くの人々は、Investing.com(https://cn.investing.com/news/latest-news)からのニュースデータをクロールしようとします。

Python 3.6のピクルスファイルの読み込みエラー:modulenotfounderror:nomodulenamed ...

SCAPYクローラーを使用するときにパイプラインファイルを作成できない理由についての議論は、SCAPYクローラーを学習して永続的なデータストレージに使用するときに、パイプラインファイルに遭遇する可能性があります...
