Advent of Code 2024, Day 20

I first tried a “multi-dimensional” variant of Dijkstra’s algorithm: imagine a graph consisting of three layered copies of the map, where the ground layer means that no cheat has started yet, the middle layer means that a cheat is in progress (which must end in the next move), and the top layer means that the cheat is finished (so that no new cheat can start). Once you add directed edges between the layers that accurately model the rules, you can simply run Dijkstra’s algorithm on it. In practice, you wouldn’t construct an entire new graph in memory; you would just add more entries to the position tuples in the priority queue and in the distance map and adapt the discovery mechanism (like on day 16, where I modeled the direction that the character is facing as an additional dimension).

But that approach was too slow, because the queue kept growing and growing. I then thought about running a modified version of Dijkstra’s algorithm for each shortcut, where I would force the algorithm to take exactly that shortcut, no more and no less, so that I could compare the resulting distances. But then I found a tip: you can simply compare the finishing distances of the two ends of a shortcut without having to actually traverse that specific shortcut path in its entirety. The resulting algorithm runs only a single breadth-first search from the end. I merely lost time because I had a bug where I didn’t apply “abs_di” and “abs_dj” simultaneously.

I found that first iterating over the cheat targets in the distance map and then checking whether they are within cheating distance is significantly slower than fixing the targets within cheating distance and then checking whether they are in the distance map (like I do here, which I intuitively did from the beginning) — which makes sense, because it adds a linear factor. On the other hand, I did not find any significant speedup from shuffling the three loop headers (probably because Python is too far away from any cache effects).

Both parts

For part 1, give “2” as the second argument. For part 2, give “20” as the second argument.

import sys

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

max_d = int(sys.argv[2])
min_saved = int(sys.argv[3]) if len(sys.argv) > 3 else 100

for i, line in enumerate(lines):
    for j, c in enumerate(line):
        if c == "E": ei, ej = i, j

q = [(ei, ej)]
d = {(ei, ej): 0}
while len(q) > 0:
    i, j = q.pop(0)
    for ni, nj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
        if lines[ni][nj] == "#": continue
        if (ni, nj) in d: continue
        q.append((ni, nj))
        d[(ni, nj)] = d[(i, j)]+1

s = 0
for ai, aj in d:
    for abs_d in range(2, max_d+1):
        for abs_di in range(0, abs_d+1):
            abs_dj = abs_d - abs_di
            bs = set([
                (ai-abs_di, aj-abs_dj),
                (ai-abs_di, aj+abs_dj),
                (ai+abs_di, aj-abs_dj),
                (ai+abs_di, aj+abs_dj)
            ])
            for bi, bj in bs:
                if (bi, bj) not in d: continue
                s += d[(ai, aj)] - (d[(bi, bj)] + abs_d) >= min_saved
print(s)

2024-12-22