ホームページ バックエンド開発 Python チュートリアル 深さ優先探索の丘を登る、Advent of Code 10 日目

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

Jan 13, 2025 pm 02:09 PM

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

Climbing a depth-first search hill, Advent of Code day 10
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 の定義に従って、後戻りする前に各ブランチを完全に調査します。

Climbing a depth-first search hill, Advent of Code day 10
深さ優先検索の視覚的表現

マップポイントは私たちの「ノード」であり、一度に 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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

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

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

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

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

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

Python vs. C:曲線と使いやすさの学習 Python vs. C:曲線と使いやすさの学習 Apr 19, 2025 am 12:20 AM

Pythonは学習と使用が簡単ですが、Cはより強力ですが複雑です。 1。Python構文は簡潔で初心者に適しています。動的なタイピングと自動メモリ管理により、使いやすくなりますが、ランタイムエラーを引き起こす可能性があります。 2.Cは、高性能アプリケーションに適した低レベルの制御と高度な機能を提供しますが、学習しきい値が高く、手動メモリとタイプの安全管理が必要です。

Pythonの学習:2時間の毎日の研究で十分ですか? Pythonの学習:2時間の毎日の研究で十分ですか? Apr 18, 2025 am 12:22 AM

Pythonを1日2時間学ぶだけで十分ですか?それはあなたの目標と学習方法に依存します。 1)明確な学習計画を策定し、2)適切な学習リソースと方法を選択します。3)実践的な実践とレビューとレビューと統合を練習および統合し、統合すると、この期間中にPythonの基本的な知識と高度な機能を徐々に習得できます。

Python vs. C:パフォーマンスと効率の探索 Python vs. C:パフォーマンスと効率の探索 Apr 18, 2025 am 12:20 AM

Pythonは開発効率でCよりも優れていますが、Cは実行パフォーマンスが高くなっています。 1。Pythonの簡潔な構文とリッチライブラリは、開発効率を向上させます。 2.Cのコンピレーションタイプの特性とハードウェア制御により、実行パフォーマンスが向上します。選択を行うときは、プロジェクトのニーズに基づいて開発速度と実行効率を比較検討する必要があります。

Python vs. C:重要な違​​いを理解します Python vs. C:重要な違​​いを理解します Apr 21, 2025 am 12:18 AM

PythonとCにはそれぞれ独自の利点があり、選択はプロジェクトの要件に基づいている必要があります。 1)Pythonは、簡潔な構文と動的タイピングのため、迅速な開発とデータ処理に適しています。 2)Cは、静的なタイピングと手動メモリ管理により、高性能およびシステムプログラミングに適しています。

Python Standard Libraryの一部はどれですか:リストまたは配列はどれですか? Python Standard Libraryの一部はどれですか:リストまたは配列はどれですか? Apr 27, 2025 am 12:03 AM

PythonListSarePartOfThestAndardarenot.liestareBuilting-in、versatile、forStoringCollectionsのpythonlistarepart。

Python:自動化、スクリプト、およびタスク管理 Python:自動化、スクリプト、およびタスク管理 Apr 16, 2025 am 12:14 AM

Pythonは、自動化、スクリプト、およびタスク管理に優れています。 1)自動化:OSやShutilなどの標準ライブラリを介してファイルバックアップが実現されます。 2)スクリプトの書き込み:Psutilライブラリを使用してシステムリソースを監視します。 3)タスク管理:スケジュールライブラリを使用してタスクをスケジュールします。 Pythonの使いやすさと豊富なライブラリサポートにより、これらの分野で優先ツールになります。

科学コンピューティングのためのPython:詳細な外観 科学コンピューティングのためのPython:詳細な外観 Apr 19, 2025 am 12:15 AM

科学コンピューティングにおけるPythonのアプリケーションには、データ分析、機械学習、数値シミュレーション、視覚化が含まれます。 1.numpyは、効率的な多次元配列と数学的関数を提供します。 2。ScipyはNumpy機能を拡張し、最適化と線形代数ツールを提供します。 3. Pandasは、データ処理と分析に使用されます。 4.matplotlibは、さまざまなグラフと視覚的な結果を生成するために使用されます。

Web開発用のPython:主要なアプリケーション Web開発用のPython:主要なアプリケーション Apr 18, 2025 am 12:20 AM

Web開発におけるPythonの主要なアプリケーションには、DjangoおよびFlaskフレームワークの使用、API開発、データ分析と視覚化、機械学習とAI、およびパフォーマンスの最適化が含まれます。 1。DjangoandFlask Framework:Djangoは、複雑な用途の迅速な発展に適しており、Flaskは小規模または高度にカスタマイズされたプロジェクトに適しています。 2。API開発:フラスコまたはdjangorestFrameworkを使用して、Restfulapiを構築します。 3。データ分析と視覚化:Pythonを使用してデータを処理し、Webインターフェイスを介して表示します。 4。機械学習とAI:Pythonは、インテリジェントWebアプリケーションを構築するために使用されます。 5。パフォーマンスの最適化:非同期プログラミング、キャッシュ、コードを通じて最適化

See all articles