Why couldn't it just have been Djiktra's 🥲
| Part 1 | Part 2 | Total | |
|---|---|---|---|
| Time | 12:46:19 | 1:32:51 | 14:19:10 |
I got Djikstra's right away, but I was struggling with wrapping my head around how to constrain it to require a turn after 3 consecutive moves in the same direction.
Originally, I wasn't keeping track of direction, but rather using a prev[] list (from traditional Djikstra's implementations). For the current node, I grabbed the 3 previous and checked if they were all on the same X or all on the same Y as the current node.
You might notice that's a total of 4, but - I figured - that accounts for a turn between the first and second one in the chain.
This worked well, but it was slightly off because once a node was visited, I was removing it from an unvisited set. The code would never go back and check what would have happened if it had made a different turn when it was required, or turned early, or anything. A huge subset of possible moves was greedily discarded by the algorithm.
I worked on it for 2 hours and 15 minutes, before I shut my laptop in defeat and went to bed. Doing Advent of Code on the east coast of the United States has its perks, the current time is the time I've spent so far. But when it gets that high, it gets annoying!
I knew what I had to do, but I didn't know how to do it and didn't feel like modifying my existing code enough to make it work.
Ten hours later, I had some time to start at 12:40 PM. The big breakthrough was switching the unvisited set to a visited set and incorporating a priority queue of nodes to visit. Then, crucially, I could distinguish visited nodes not just by their position, but also by their direction and the previous two nodes' directions as well. This ensures that every possible set of directions to get to a certain node is available for the algorithm to test. This effectively adds all the valid edges to the graph.
After a fresh sleep and spending some time thinking about it, it took me 7 minutes to modify my code in that way:
from helpers.datagetter import aocd_data_in
import heapq
din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0
for i in range(len(din)):
din[i] = [c for c in din[i]]
visited = set()
q = [(0, (0, 0), 1, (None, None))]
while q:
node = heapq.heappop(q)
heat, current, direction, prev = node
x, y = current
if x == len(din) - 1 and y == len(din[0]) - 1:
ans = heat
break
if (current, direction, prev) in visited:
continue
visited.add((current, direction, prev))
for i in range(-1, 2):
for j in range(-1, 2):
if abs(i) + abs(j) != 1 or (x + i) < 0 or (x + i) >= len(din) or (y + j) < 0 or (y + j) >= len(din[0]):
continue
d = [(-1, 0), (0, 1), (1, 0), (0, -1)].index((i, j))
if None not in prev and prev[0] == prev[1] == direction == d:
continue
if abs(direction - d) == 2:
continue
alt = heat + int(din[x + i][y + j])
new_node = (alt, (x + i, y + j), d, (prev[1], direction))
heapq.heappush(q, new_node)
aocd_submit(ans)A simple change, right?? Change the constraint to 10 and add a minimum constraint, and only trigger reaching the end (bottom-right) if the minimum constraint is satisfied there too. Apparently that last bit is what tripped up a lot of people, but not me!
No, my problem was much sillier, and I must have gotten lucky because I didn't notice it in Part 1. I had started my initial node out with a direction pointing to the right, when in reality the path at the starting point has no direction. Add in a simple check for that (which would also make Part 1 more correct) and then it's golden.
In all, finding this error from Part 1 took another unfortunate hour and a half. Hoping for a quick one tonight! I still have exams.
from helpers.datagetter import aocd_data_in
import heapq
din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0
for i in range(len(din)):
din[i] = [c for c in din[i]]
visited = set()
q = [(0, (0, 0), None, (None, None, None, None, None, None, None, None, None))]
while q:
node = heapq.heappop(q)
heat, current, direction, prev = node
x, y = current
if x == len(din) - 1 and y == len(din[0]) - 1 and [*prev[-3:], direction].count(direction) == 4:
ans = heat
break
if (current, direction, prev) in visited:
continue
visited.add((current, direction, prev))
for i in range(-1, 2):
for j in range(-1, 2):
if abs(i) + abs(j) != 1 or (x + i) < 0 or (x + i) >= len(din) or (y + j) < 0 or (y + j) >= len(din[0]):
continue
d = [(-1, 0), (0, 1), (1, 0), (0, -1)].index((i, j))
if direction is not None:
if abs(direction - d) == 2 and direction != -1:
continue
if None not in prev and prev.count(prev[0]) == len(prev) and prev[0] == direction == d:
continue
if [*prev[-3:], direction].count(direction) != 4 and direction != d:
continue
alt = heat + int(din[x + i][y + j])
new_node = (alt, (x + i, y + j), d, (*prev[1:], direction))
heapq.heappush(q, new_node)
aocd_submit(ans)