Erklimmen eines Tiefensuchhügels, Advent of Code, Tag 10

Die heutige Herausforderung befasst sich mit dem Rätsel von Tag 10, einem 2D-Gitter ähnlich wie Tag 6, erfordert jedoch die Erkundung mehrerer Pfade. Dieses Rätsel demonstriert auf elegante Weise die Leistungsfähigkeit der Tiefensuche (DFS).

Eine KI-generierte Illustration des Puzzles

Die Karte wird als Wörterbuch dargestellt; Schlüssel sind (x, y)-Koordinaten und Werte sind einstellige Ganzzahlen (0-9), die die Höhe angeben, wobei 9 den Gipfel darstellt. Die Parsing-Funktion verarbeitet diese Datenstruktur effizient:

<code class="language-python">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)
    }</code>

Wege steigen vom Ausgangspunkt (Höhe 0) bis zum Gipfel (Höhe 9) an und erhöhen die Höhe um genau 1 pro Schritt. Die Funktion next_step identifiziert gültige nächste Schritte:

<code class="language-python">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)
        )
    )</code>

Wanderwege (Höhe 0) werden mit find_trailheads:

lokalisiert

<code class="language-python">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)</code>

Kern der Lösung ist die climb-Funktion, die eine Tiefensuche implementiert. Gemäß der Wikipedia-Definition von DFS untersuchen wir jeden Zweig vollständig, bevor wir einen Rückzieher machen.

Eine visuelle Darstellung der Tiefensuche

Kartenpunkte sind unsere „Knotenpunkte“, und wir steigen jeweils eine Höhenstufe auf. Die Funktion climb verwaltet den DFS-Prozess:

<code class="language-python">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</code>

Das else der break-Klausel behandelt Sackgassen und verhindert so Endlosschleifen. Die Funktion gibt alle Pfade von jedem Ausgangspunkt zum Gipfel zurück.

Teil 1 zählt die einzigartigen Gipfelziele auf:

<code class="language-python">def part1(input: str) -> int:
    topo_map = parse(input)

    return len(climb(topo_map, find_trailheads(topo_map)))</code>

Teil 2 zählt alle eindeutigen Pfade:

<code class="language-python">def part2(input: str) -> int:
    topo_map = parse(input)

    return sum(
        len(routes) for routes in climb(topo_map, find_trailheads(topo_map)).values()
    )</code>

Obwohl es alternative Ansätze gibt (z. B. die Integration der Trailhead-Erkennung in das Parsing), ist die Leistung dieser Lösung akzeptabel. Die jüngsten Rückschläge bei der Jobsuche haben meine Stimmung nicht getrübt; Ich bleibe hoffnungsvoll. Wenn Sie auf der Suche nach einem Python-Entwickler mittlerer Führungsebene sind, wenden Sie sich bitte an uns. Bis nächste Woche!

Das obige ist der detaillierte Inhalt vonErklimmen eines Tiefensuchhügels, Advent of Code, Tag 10. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!