Module aoc::year2022::day12

Hill Climbing Algorithm

Pretty much textbook implementation of a BFS (Breadth First Search). If you’re not familar 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 visited nodes.

For Part 2 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 the the fact that BFS always explores closest nodes first this will find the closest a location in a single search. For part 1 it will have the same result, so we can re-use the same code.

Functions

• bfs 🔒
  BFS algorithm implementation with the reversed height transition rules baked in.
• height 🔒
  Map S to a and E to z, otherwise use the value unchanged.
• parse
  Uses the utility Grid class 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 🔒