Jo Wood

Solutions to https://adventofcode.com/2022

Ξ🎄Advent of Code 2022

Why should dijsktra be so slow? I have an  implementation [here]( https://observablehq.com/@fil/dijkstra) that seems efficient, and I wonder if I'm missing something? (Maybe there is a "vanilla dijkstra" that's suboptimal?)

Probably more likely I've missed something. The Dijkstra search I used as part of this general purpose graph class: https://observablehq.com/@jwolondon/gds-graph and there's a bit of an overhead in setting up the graph structure and priority queue that is more expensive than a simple BFS over the raster array with a small frontier. Combined with my initial attempt at a forward search for part 2 that tried from every `a` cell, this overhead was significant. I guess if I'd used Dijkstra directly on the raster cells, it would have been much quicker, although because we only need the distance, not the path itself, I don't think we need to keep track of the path as Dijkstra does.

Thanks! I only figured at the last minute (when my solution was rejected) that "up" was meant for position and not for elevation—so I thought I needed to keep track of all the costs :-)