Dzisiaj ponownie rozwiązanie nie było szczególnie skomplikowane, właściwie to pierwszy pomysł od razu zadziałał, a rozwinięcie go do wspierania także części drugiej było tak proste jak dodanie jednej dodatkowej zmiennej.

Zadanie

Na wejściu dostajemy mapę wysokościową przedstawioną jako macierz 2d, każdy punkt ma cyfrę, która oznacza wysokośc w danym miejscu. Naszym celem jest znalezienie ścieżek na szczyt. Nasze trasy powinny się zaczynać w punkcie o wysokości 0 i każdy krok który wyoknujemy (tylko prostopadle do osi x i y, nie ma przekątnych) powinien zwiększać naszą wysokośc o jeden aż dojdziemy do szczytu o cyfrze 9.

Rozwiązanie

Zaczniemy od parsowania wejściowej macierzy i znalezienia w niej punktów startowych.

import fileinput

grid = [list(map(int, line.strip())) for line in fileinput.input()]

trailheads = []
for y, row in enumerate(grid):
    for x, h in enumerate(row):
        if h == 0:
            trailheads.append((y, x))

Następnie dla każdego punktu startowego będziemy szukać wszystkich możliwych ścieżek, użyjemy do tego celu algorytmu DFS (Depth First Search), który implementuje się używając stosu.

part1 = 0

for starty, startx in trailheads:
    reachable = set()
    stack = [(starty, startx)]
    while stack:
        y, x = stack.pop()
        h = grid[y][x]
        if h == 9:
            reachable.add((y, x))
            continue

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx = x + dx
            ny = y + dy
            if (
                nx >= 0
                and ny >= 0
                and nx < len(grid)
                and ny < len(grid[0])
                and grid[ny][nx] - h == 1
            ):
                stack.append((ny, nx))
    part1 += len(reachable)

print(part1)

Część 2

W drugiej części musimy policzyć ilość wszystkich unikalnych ścieżek na szczyt z każdego pola startowego o numerze 0.

Nasz kod z części pierwszej i tak sprawdza każdą możliwą ścieżkę, dlatego wymagana jest jedynie dodatkowa zmienna licząca. Poniżej wrzucam kod dla obu części z zaznaczonymi linijkami które musiałem zmienić żeby rozwiązać drugą część:

import fileinput

grid = [list(map(int, line.strip())) for line in fileinput.input()]

trailheads = []
for y, row in enumerate(grid):
    for x, h in enumerate(row):
        if h == 0:
            trailheads.append((y, x))

part1 = 0
part2 = 0

for starty, startx in trailheads:
    reachable = set()
    stack = [(starty, startx)]
    while stack:
        y, x = stack.pop()
        h = grid[y][x]
        if h == 9:
            reachable.add((y, x))
            part2 += 1
            continue

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx = x + dx
            ny = y + dy
            if (
                nx >= 0
                and ny >= 0
                and nx < len(grid)
                and ny < len(grid[0])
                and grid[ny][nx] - h == 1
            ):
                stack.append((ny, nx))
    part1 += len(reachable)

print(part1)
print(part2)

Podsumowanie

Pisząc moje rozwiązanie do części pierwszej miałem wrażenie że będzie ono nieoptymalne, sprawdzanie każdej możliwej ścieżki nie jest konieczne żeby znaleźć każdy możliwy cel, więc rozwiązanie to jest praktycznie brute forcem. Ucieszyłem się kiedy w drugiej części okazało się że jednak będzie potrzebne sprawdzenie każdej opcji. Dobrze że przedwcześnie nie próbowałem zoptymalizować mojego pierwszego rozwiązania, gdyż zajęło by mi to więcej czasu a praca i tak nie byłbaby przydatna w drugiej części