Solution to the 5th problem

Problem A

I approached this problem using Dijkstra's algorithm , which is a graph algorithm that helps finding the shortest path. The problem defines a matrix, with a start (S) and end point (E). The shortest path has to be found, but the algorithm can only go to:

• Up, down, left and right
• The value of the next cell can only be one more, equal, or simply lower

Each cell is a char and, based on their position in the alphabet, it's either higher or lower (i.e. b is lower than c, but higher than a).

Therefore, we build a graph, to determine which nodes can be acessed from which, and we run Dijkstra's algorithm from S to E.

» cargo build -p aoc-22 --release && hyperfine ./target/release/aoc-22 -N --warmup 5
Benchmark 1: ./target/release/aoc-22
Time (mean ± σ):       4.8 ms ±   1.7 ms    [User: 1.1 ms, System: 0.9 ms]
Range (min … max):     3.1 ms …  18.5 ms    511 runs

Problem B

The initial implementation was executing the algorithm for each a char. While this requires minimum changes to the initial algorithm, while developing this visualization I realised that it's really no the most eficient way. Since the part B implies finding the closest E from any a, we can simply reverse the graph (i.e. invert all edges) and run Dijkstra's algorithm from E. The first time we reach an a we can stop the algorithm, since it's guaranteed to be the closest one. This solution implies other changes, for example, in which nodes can be the next ones.

» cargo build -p aoc-23 --release && hyperfine ./target/release/aoc-23 -N --warmup 5
Benchmark 1: ./target/release/aoc-22
Time (mean ± σ):       8.2 ms ±   4.0 ms    [User: 2.1 ms, System: 1.0 ms]
Range (min … max):     4.0 ms …  44.3 ms    196 runs