aoc/year2022/
day12.rs

1//! # Hill Climbing Algorithm
2//!
3//! Pretty much textbook implementation of a BFS (Breadth First Search). If you're not familar 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
9//!   than [`vec`] when used as a FIFO queue.
10//! * [`Grid`] is used to store both the height information and visited nodes.
11//!
12//! For Part 2 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 the the fact that BFS always explores closest nodes first this will find the
15//! closest `a` location in a single search. For part 1 it will have the same result, so we
16//! can re-use the same code.
17//!
18//! [`Grid`]: crate::util::grid
19//! [`Point`]: crate::util::point
20use crate::util::grid::*;
21use crate::util::point::*;
22use std::collections::VecDeque;
23
24type Input = (Grid<u8>, Point);
25
26/// Uses the utility [`Grid`] class to parse a 2D array of ASCII characters.
27///
28/// [`Grid`]: crate::util::grid
29pub fn parse(input: &str) -> Input {
30    let grid = Grid::parse(input);
31    let start = grid.find(b'E');
32    (grid, start.unwrap())
33}
34
35/// Find the shortest path from `E` to `S`
36pub fn part1(input: &Input) -> u32 {
37    bfs(input, b'S')
38}
39
40/// Find the shortest path from `E` to closest `a`
41pub fn part2(input: &Input) -> u32 {
42    bfs(input, b'a')
43}
44
45/// BFS algorithm implementation with the reversed height transition rules baked in.
46fn bfs(input: &Input, end: u8) -> u32 {
47    let (grid, start) = input;
48    let mut todo = VecDeque::from([(*start, 0)]);
49    let mut visited = grid.same_size_with(false);
50
51    while let Some((point, cost)) = todo.pop_front() {
52        if grid[point] == end {
53            return cost;
54        }
55        for next in ORTHOGONAL.iter().map(|&x| x + point) {
56            if grid.contains(next)
57                && !visited[next]
58                && height(grid, point) - height(grid, next) <= 1
59            {
60                todo.push_back((next, cost + 1));
61                visited[next] = true;
62            }
63        }
64    }
65
66    unreachable!()
67}
68
69/// Map `S` to `a` and `E` to `z`, otherwise use the value unchanged.
70fn height(grid: &Grid<u8>, point: Point) -> i32 {
71    match grid[point] {
72        b'S' => 'a' as i32,
73        b'E' => 'z' as i32,
74        b => b as i32,
75    }
76}
aoc/year2022/day12.rs

aoc/year2022/
day12.rs
