Advent of Code 2023 - Day 17

45th on part 1; 18th on part 2; now 4th overall.

Slow part1 because I forgot to actually use Dijkstra instead of BFS. My final code is quite slow.

[CAG]

The way I encoded the graph is (row, col, dir), where dir is one of 4 directions.

The trick is that each node represents "the position at row, col, where you aren't allowed to move in a direction parallel to dir". So in fact, the neighbours of say (row, col, right) are

(row - 1, col, up)
(row - 2, col, up)
(row - 3, col, up)
and similar for down.

A friend also told me I could ditch "left, right, up, down" and just use "horizontal and vertical" which makes it even cleaner

[dylans]

It took me awhile to realize I needed to include direction of motion and how many times it had moved in that direction when tracking visited vertices. Just glad I got it done before I fell asleep 😃

[rastislavsvoboda]

I've just tested your solution with my input and P2 is wrong
you got lucky ;-)
because you are missing check "(or even before it can stop at the end)."

[every]

I lost a lot of time by not realizing that the cart also has to move a minimum of 4 tiles in a direction when it reaches the end too. Does your code account for that, I can't see where it does.

[sonatafrittata]

I can't believe this is running so fast. My example code runs in 1 second, yet the main input takes several hours, even though my code is pretty similar to yours, but OO. Still need to figure out what is different!

[dirkmiller]

One possible speedup is to test if you reached the end position in the loop and return the current cost there - the first time you hit it has to be the cheapest.

[rastislavsvoboda]

congrats, some messy P1, not sure why you did not make ints from inputs directly; but nice quick P2

I was not storing all costs for all positions, only waiting for (R-1, C-1), but I needed to add checking for s >= min_moves_before_turn
because problem stated "it needs to move a minimum of four blocks in that direction before it can turn (or even before it can stop at the end)."
maybe I did not understand if this is in your "valid" checking or you just got lucky
when I remove this condition, I get correct result for P2 for sample, but wrong for my input

def solve(lines, min_moves_before_turn, max_moves_straight):
D = [[int(ch) for ch in line.strip()] for line in lines]
R = len(D)
C = len(D[0])

res = None

seen = set()
q = []
# value, row, column, heading, steps
heapq.heappush(q, (0, 0, 0, -1, 0))

while q:
v, r, c, h, s = heapq.heappop(q)

if (r, c, h, s) in seen:
continue

seen.add((r, c, h, s))

if s >= min_moves_before_turn and r == R - 1 and c == C - 1:
res = v
break

for rr, cc, hh, ss in get_moves(r, c, h, s, min_moves_before_turn, max_moves_straight):
if 0 <= rr < R and 0 <= cc < C:
vv = v + D[rr][cc]
heapq.heappush(q, (vv, rr, cc, hh, ss))

return res

[gupta_samarth]

Btw, you didn't have the right braces for isvalid_part2 condition which would be the cause for the long time ( or maybe an infinite loop ), and not the assert / prints, I think

[terryaney]

Tried writing A* traversal...can't see a bug in my code. At a high level, would that traversal work as a search mechanism? If you said you are using dykstra...from what I understand a* is superset/better than dykstra?