Mendaki bukit pencarian yang paling dalam, Advent of Code hari ke-10

Cabaran hari ini menangani teka-teki Hari 10, grid 2D yang serupa dengan Hari 6, tetapi memerlukan penerokaan berbilang laluan. Teka-teki ini dengan elegan mempamerkan kuasa carian depth-first (DFS).

Ilustrasi teka-teki yang dijana AI

Peta diwakili sebagai kamus; kunci ialah koordinat (x, y) dan nilai ialah integer satu digit (0-9) yang menunjukkan ketinggian, dengan 9 mewakili puncak. Fungsi penghuraian mengendalikan struktur data ini dengan cekap:

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

Denai naik dari kepala denai (ketinggian 0) ke puncak (ketinggian 9), meningkatkan ketinggian dengan tepat 1 setiap langkah. Fungsi next_step mengenal pasti langkah seterusnya yang sah:

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

Trailheads (ketinggian 0) terletak menggunakan 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)

Inti penyelesaian ialah fungsi climb, yang melaksanakan carian mendalam-dahulu. Mengikuti takrifan Wikipedia tentang DFS, kami meneroka setiap cawangan sepenuhnya sebelum berundur.

Perwakilan visual carian mendalam-pertama

Mata peta ialah "nod" kami dan kami naik satu paras ketinggian pada satu masa. Fungsi climb menguruskan proses 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

Klausa else break mengendalikan jalan buntu, menghalang gelung tak terhingga. Fungsi ini mengembalikan semua laluan dari setiap denai ke puncak.

Bahagian 1 mengira destinasi puncak yang unik:

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

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

Bahagian 2 mengira semua laluan unik:

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

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

Walaupun pendekatan alternatif wujud (mis., menyepadukan pengesanan kepala jejak ke dalam penghuraian), prestasi penyelesaian ini boleh diterima. Kemunduran pencarian kerja baru-baru ini tidak melemahkan semangat saya; Saya tetap berharap. Jika anda sedang mencari pembangun Python pertengahan senior, sila hubungi. Sehingga minggu hadapan!

Atas ialah kandungan terperinci Mendaki bukit pencarian yang paling dalam, Advent of Code hari ke-10. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!