Module day12 

Hill Climbing Algorithm

Pretty much textbook implementation of a BFS (Breadth-first search). If you’re not familiar with BFS, this blog post is a great introduction to the algorithm, plus some others that come in handy for Advent of Code.

Implementation notes:

• A VecDeque of Point is used to store the frontier as it gives better performance than vec when used as a FIFO queue.
• Grid is used to store both the height information and seen nodes.

For part two we could search for all a locations and repeatedly start a BFS search from there, then find the lowest value. However, a much faster approach is to search backwards from the end location. Due to the fact that BFS always explores closest nodes first this will find the closest a location in a single search. In fact, we can just run one single search, finding the part two answer first, then continuing on to the S location for part one.

Functions

parse

Uses the utility Grid module to parse a 2D array of ASCII characters.

part1

Find the shortest path from E to S.

part2

Find the shortest path from E to closest a.

Type Aliases

Input 🔒