aoc/year2022/
day12.rs

1//! # Hill Climbing Algorithm
2//!
3//! Pretty much textbook implementation of a BFS (Breadth-first search). If you're not familiar with
4//! BFS, [this blog post is a great introduction](https://www.redblobgames.com/pathfinding/a-star/introduction.html)
5//! to the algorithm, plus some others that come in handy for Advent of Code.
6//!
7//! Implementation notes:
8//! * A [`VecDeque`] of [`Point`] is used to store the frontier as it gives better performance than
9//!   [`vec`] when used as a FIFO queue.
10//! * [`Grid`] is used to store both the height information and seen nodes.
11//!
12//! For part two we could search for all `a` locations and repeatedly start a BFS search from there,
13//! then find the lowest value. However, a much faster approach is to search *backwards* from the
14//! end location. Due to the fact that BFS always explores closest nodes first this will find the
15//! closest `a` location in a single search. In fact, we can just run one single search, finding
16//! the part two answer first, then continuing on to the `S` location for part one.
17//!
18//! [`Grid`]: crate::util::grid
19//! [`Point`]: crate::util::point
20use std::collections::VecDeque;
21
22use crate::util::grid::*;
23use crate::util::point::*;
24
25type Input = (u32, u32);
26
27/// Uses the utility [`Grid`] module to parse a 2D array of ASCII characters.
28///
29/// [`Grid`]: crate::util::grid
30pub fn parse(input: &str) -> Input {
31    // A newline border allows us to avoid boundary checks.
32    let mut grid = Grid::parse_with_border(input);
33
34    // Run the BFS algorithm implementation with the reversed height transition rules baked in.
35    // In fact, we don't need a separate seen grid; we can modify the original grid in place.
36    let start = grid.find(b'E').unwrap();
37    let mut todo = VecDeque::from([(start, b'z' - 1, 1)]);
38    grid[start] = 0;
39    let mut part_two = None;
40
41    while let Some((point, height, cost)) = todo.pop_front() {
42        for next in ORTHOGONAL.map(|d| d + point) {
43            if grid[next] == b'S' {
44                return (cost, part_two.unwrap());
45            }
46            if grid[next] >= height {
47                if grid[next] == b'a' {
48                    part_two = part_two.or(Some(cost));
49                }
50                todo.push_back((next, grid[next] - 1, cost + 1));
51                grid[next] = 0;
52            }
53        }
54    }
55
56    unreachable!()
57}
58
59/// Find the shortest path from `E` to `S`.
60pub fn part1(input: &Input) -> u32 {
61    input.0
62}
63
64/// Find the shortest path from `E` to closest `a`.
65pub fn part2(input: &Input) -> u32 {
66    input.1
67}
aoc/year2022/day12.rs

aoc/year2022/
day12.rs
