Advent of Code 2024, Day 16

I used Dijkstra’s algorithm. In part 2, I extended it to track predecessors and computed the transitive closure of the end configurations under the predecessors. I lost time because I tried to come up with some custom recursive function at first (instead of just using Dijkstra’s algorithm) and because I had to look up how to extract a key from a dictionary whose value (not the key itself) is minimal.

Part 1

import sys
import math

with open(sys.argv[1]) as f:
    lines = [[c for c in line.strip()] for line in f]

for i in range(len(lines)):
    for j in range(len(lines[i])):
        if lines[i][j] == "S":
            si, sj = i, j
            lines[i][j] = "."
        elif lines[i][j] == "E":
            ei, ej = i, j
            lines[i][j] = "."

unvisited = {(si, sj, 0, 1): 0}
visited = {}
while len(unvisited) > 0:
    i, j, di, dj = min(unvisited, key=unvisited.get)
    d = unvisited.pop((i, j, di, dj))
    visited[(i, j, di, dj)] = d
    neighbors = [
        (i+di, j+dj, di, dj, d+1),
        (i, j, +dj, +di, d+1000),
        (i, j, -dj, -di, d+1000)
    ]
    for ni, nj, ndi, ndj, nd in neighbors:
        if lines[ni][nj] == "#": continue
        neighbor = (ni, nj, ndi, ndj)
        if neighbor in visited: continue
        if nd < unvisited.get(neighbor, math.inf):
            unvisited[neighbor] = nd

candidates = [
    (ei, ej, 0, -1),
    (ei, ej, 0, +1),
    (ei, ej, -1, 0),
    (ei, ej, +1, 0)
]
d = min([visited[c] for c in candidates])
print(d)

Part 2

import sys
import math

def extend(s, d):
    r, frontier = set(), s
    while len(frontier) > 0:
        r.update(frontier)
        frontier = [y for x in frontier for y in d.get(x, [])]
    return r

with open(sys.argv[1]) as f:
    lines = [[c for c in line.strip()] for line in f]

for i in range(len(lines)):
    for j in range(len(lines[i])):
        if lines[i][j] == "S":
            si, sj = i, j
            lines[i][j] = "."
        elif lines[i][j] == "E":
            ei, ej = i, j
            lines[i][j] = "."

unvisited = {(si, sj, 0, 1): 0}
visited = {}
pred = {}
while len(unvisited) > 0:
    i, j, di, dj = min(unvisited, key=unvisited.get)
    d = unvisited.pop((i, j, di, dj))
    visited[(i, j, di, dj)] = d
    neighbors = [
        (i+di, j+dj, di, dj, d+1),
        (i, j, +dj, +di, d+1000),
        (i, j, -dj, -di, d+1000)
    ]
    for ni, nj, ndi, ndj, nd in neighbors:
        if lines[ni][nj] == "#": continue
        neighbor = (ni, nj, ndi, ndj)
        if neighbor in visited: continue
        if nd < unvisited.get(neighbor, math.inf):
            unvisited[neighbor] = nd
            pred[neighbor] = {(i, j, di, dj)}
        elif nd == unvisited.get(neighbor, math.inf):
            pred[neighbor].add((i, j, di, dj))

candidates = [
    (ei, ej, 0, -1),
    (ei, ej, 0, +1),
    (ei, ej, -1, 0),
    (ei, ej, +1, 0)
]
d = min([visited[c] for c in candidates])
candidates = [c for c in candidates if visited[c] == d]
closure = extend(candidates, pred)
print(len(set([(i, j) for (i, j, _, _) in closure])))

2024-12-18