Problem

Dzisiejsze zadanie polega na znalezieniu ścieżki w labiryncie która będzie miała najniższy score, gdzie score liczony jest w taki sposób że każdy ruch zwiększa go o jeden a każdy skręt o 90 stopni zwiększa go o 1000.

Zaczynamy w punkcie S a kończymy w punkcie E. Oto przykładowy labirynt:

###############
#.......#....E#
#.#.###.#.###.#
#.....#.#...#.#
#.###.#####.#.#
#.#.#.......#.#
#.#.#####.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S..#.....#...#
###############

Rozwiązanie

Jak tylko widzę zadanie ze znajdywaniem najkrótszej ścieżki to od razu myślę o algorytmie Dijkstry. Nasz labirynt możemy rozważać jako graf. Ważne jest to że każdym wierzchołkiem nie mogą być same koordynaty a także kierunek w którym jesteśmy zwróceni, lub bardziej powinienem powiedzieć orientacja, gdyż z punktu widzenia liczenia score nie ma znaczenia w którą stronę skręcamy a jedynie że zmieniamy orientację z pionowej na poziomą lub na odwrót.

Parsowanie

W miarę proste, nie ma co tu wiele tłumaczyć:

starting = end = None

grid = [line.strip() for line in sys.stdin.readlines()]
dist_grid = [list(row) for row in grid]

for i, row in enumerate(grid):
    for j, c in enumerate(row):
        if c == "S":
            starting = (i, j, HORIZONTAL)  # zaczynamy skierowani w prawo
        elif c == "E":
            end = (i, j)

assert starting is not None
assert end is not None

Algorytm Dijkstry

Zdefiniuję sobie funkcję pomocniczą zwracającą sąsiadujące pola wraz z orientacją w której się znajdziemy jeśli się na nie przesuniemy z aktualnego pola.

VERTICAL = 0
HORIZONTAL = 1

def neighborhood(i, j, grid):
    N = [
        (i + 1, j, VERTICAL),
        (i - 1, j, VERTICAL),
        (i, j - 1, HORIZONTAL),
        (i, j + 1, HORIZONTAL),
    ]

    for x, y, o in N:
        if grid[x][y] != "#":
            yield x, y, o

Algorytm dijkstry obliczy nam najkrótsze dystansy do każdego stanu na naszej mapie, czyli dla każdej możliwej orientacji w każdym możliwym punkcie (o ile da się do danego stanu dotrzeć).

visited = set()
distances = defaultdict(lambda: float("inf"))

# Tworzymy kolejkę priorytetową
pq = [(0, starting)]  # heapq wymaga żeby priorytet był pierwszym argumentem w krotce

while pq:
    dist, cur = heapq.heappop(pq)
    cur_i, cur_j, cur_ori = cur

    if dist > distances[cur]:
        continue

    if cur in visited:
        continue

    visited.add(cur)

    for n in neighborhood(cur_i, cur_j, grid):
        if n in visited:
            continue
        x, y, ori = n
        newdist = dist + 1
        if ori != cur_ori:  # zmieniamy orientację
            newdist += 1000
        heapq.heappush(pq, (newdist, n, cur))

# Zwracamy wartość która jest mniejsza (jak kończymy wertykalnie czy horyzontalnie)
print("Part 1:", min(distances[*end, HORIZONTAL], distances[*end, VERTICAL]))

Dostajemy poprawny wynik

Część 2

Tutaj sprawa się lekko komplikuje, teraz mamy znaleźć każdy punkt na mapie który należy do jednej z najkrótszych ścieżek i policzyć ilość takich punktów.

Postanowiłem że będę w każdym stanie trackował jaka ścieżka doprowadziła do niego, można to zrobić trzymając dla każdego stanę listę poprzedników, z najlepszym wynikiem.

Oto końcowy kod do obu części, w komentarzach postaram się wytłumaczyć o co chodzi:

import heapq
import sys
from collections import defaultdict

VERTICAL = 0
HORIZONTAL = 1


def neighborhood(i, j, grid):
    N = [
        (i + 1, j, VERTICAL),
        (i - 1, j, VERTICAL),
        (i, j - 1, HORIZONTAL),
        (i, j + 1, HORIZONTAL),
    ]

    for x, y, o in N:
        if grid[x][y] != "#":
            yield x, y, o


if __name__ == "__main__":
    # parsowanie
    starting = end = None

    grid = [line.strip() for line in sys.stdin.readlines()]
    dist_grid = [list(row) for row in grid]

    for i, row in enumerate(grid):
        for j, c in enumerate(row):
            if c == "S":
                starting = (i, j, HORIZONTAL)
            elif c == "E":
                end = (i, j)

    assert starting is not None
    assert end is not None

    visited = set()
    distances = defaultdict(lambda: float("inf"))

    # dla każdego stanu trzymamy najlepszych poprzedników
    prevs = defaultdict(lambda: list())

    pq = [(0, starting, [])]  # startowy punkt nie ma poprzedników
    while pq:
        dist, cur, prev = heapq.heappop(pq)
        cur_i, cur_j, cur_ori = cur

        if dist > distances[cur]:
            continue

        # mamy pewność że algorytm będzie przechodził tylko po najbardziej optymalnych
        # stanach, dlatego możemy ze spokojem zawsze dodać prev i zaktualizować dist
        prevs[cur].append(prev)
        distances[cur] = dist

        if cur in visited:
            continue

        visited.add(cur)

        for n in neighborhood(cur_i, cur_j, grid):
            if n in visited:
                continue
            x, y, ori = n
            newdist = dist + 1
            if ori != cur_ori:
                newdist += 1000
            heapq.heappush(pq, (newdist, n, cur))

    # Funkcja dfs stworzona po to żeby przejść się po wszystkich ścieżkach do tyłu
    # zaczynając od end i policzyć ilość unikalnych punktów z najlepszych ścieżek
    visited = set()
    part2 = set()
    def dfs(cur):
        if cur in visited or cur is None:
            return
        visited.add(cur)
        part2.add(cur[:2])
        for prev in prevs[cur]:
            dfs(prev)

    h_end = distances[*end, HORIZONTAL]
    v_end = distances[*end, VERTICAL]

    if h_end < v_end:
        print("Part 1:", h_end)
        dfs((*end, HORIZONTAL))
    elif h_end > v_end:
        print("Part 1:", v_end)
        dfs((*end, VERTICAL))
    else:
        dfs((*end, HORIZONTAL))
        dfs((*end, VERTICAL))

    print(len(part2))

Podsumowanie

Zadanie pierwsze było zadaniem w miarę standardowym, warto mieć gdzieś implementację algorytmu dijkstry pod ręką jak się robi advent of code gdyż tego typu zadanie pojawia się co rok. Druga część sprawiła mi trochę trudności, ciężko było wyłapać niektóre case ale gdy dłużej pomyślałem i uprościłem kod, rozwiązanie stało się w miarę przejrzyste.