I used Dijkstra’s shortest path algorithm for this question and implemented this using a min heap. Runtime for both the problems was around 30ms.
My solution for both parts: AdventOfCodeElixir/lib/advent/year2024/day16.ex at main · divxvid/AdventOfCodeElixir · GitHub

Benchee results:

Name ips average deviation median 99th %
part_1 29.20 34.25 ms ±11.38% 33.76 ms 50.57 ms
part_2 29.84 33.51 ms ±13.54% 32.51 ms 62.69 ms

For part 1, I used a fairly straightforward priority queue implementation - we’ve had quite a few puzzles like this before.

Part 2 was an interesting one… I ended up implementing some weird “store how we got here” logic as different paths reached the same point and then backtracking over all of those once I found the fastest solution.

I think it might not work correctly if there are two paths to the destination that don’t converge before the destination, but I don’t have that case in any of my inputs so yay!

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2024/day16.ex

Name                     ips        average  deviation         median         99th %
day 16, part 1         12.91       77.43 ms     ±5.49%       77.14 ms       86.71 ms
day 16, part 2         13.07       76.51 ms     ±5.00%       76.09 ms       85.69 ms

Now I have some boxes from yesterday to go and argue with some more…

Yeah the puzzles aren’t going anywhere, do them at your leisure

(I stopped a few days ago because a) Christmas and b) 40 degree weather the last few days so my brain is cooked. Might pick it up again when it cools down)