Day15b runtime can be improved by bucket queue

[JLHwung]

The pathfinding library implements classic dijkstra's algorithm by a BinaryHeap.

It can be further improved, some of my thoughts are:

1. We can use a bucket queue because all weights are small integer, so the cost must be an integer between (0, 9 * V), where V is the number of vertex.
2. We can pre-compute a tighter cost upper bound than 9 * V thanks to the graph setup. Generally we don't know the path from start to end without traversing. However in the aoc setup, we do know a path from start to end: so we can sum up the risk from (0, 0) -- (W - 1, 0) -- (W - 1, H - 1) and use that as the bucket size.

I implemented the bucket queue dijkstra and it's around 20% faster than the binary heap approach on day15b setup.

[timvisee]

Fantastic suggestion. Thanks so much for sharing this.

I wasn't aware of the bucket queue structure.

I'd like to focus on the other days first. I'll likely try to implement this afterwards. Feel free to PR in the mean time.

[benschneider]

Nice one solution! I can actually also recommend using the astar method (from the same library), got a 2x speedup over Dijkstra. (finds the same path) ;) Had fun testing this over much larger maps.

[timvisee]

Interesting. I got slightly slower times while using A*. I actually started with A*, but switched to Dijkstra due to better timings.

I wonder what may have caused this. Maybe my implementation was broken. But it could also be hardware configuration related.

[benschneider]

hmm, could it be due to distance calculations?

[timvisee]

Possibly. What did you use?

[benschneider]

fn distance(&self, other: &Pos) -> i32 {
        let square_dist = (self.0 - other.0).abs().pow(2) + (self.1 - other.1).abs().pow(2);
        (square_dist as f64).sqrt() as i32
    }

But I wonder if it would be possible to profile the timing.