aoc/year2021/
day09.rs

1//! # Smoke Basin
2//!
3//! Part two is the classic [flood fill](https://en.wikipedia.org/wiki/Flood_fill) algorithm with a
4//! twist to return the size of the filled area. This algorithm can be implemented either as a
5//! [DFS](https://en.wikipedia.org/wiki/Depth-first_search) using recursion or as a
6//! [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) using an auxiliary data structure
7//! such as a [`VecDeque`].
8//!
9//! This solution uses a DFS approach as it's faster and Rust's stack size limit seems enough
10//! to accommodate the maximum basin size. Note that when masked, newline can be treated
11//! the same as `'9'` for a natural barrier that eliminates bounds checking. The [`Grid`] and
12//! [`Point`] modules make it easy to perform a flood fill that tracks the lowest value seen along
13//! the way, to share the work between part one and part two.
14//!
15//! [`VecDeque`]: std::collections::VecDeque
16//! [`Grid`]: crate::util::grid
17//! [`Point`]: crate::util::point
18use crate::util::grid::*;
19use crate::util::point::*;
20
21pub struct Basin {
22    lowest: u32, // Lowest integer seen within basin so far.
23    size: u32,   // Number of cells in the basin.
24}
25
26pub fn parse(input: &str) -> Vec<Basin> {
27    // A newline border allows us to avoid boundary checks.
28    let mut grid = Grid::parse_with_border(input);
29
30    // Collect all basins in the grid. Masking with 15 turns '0' through '9' into their numeric
31    // value, and '\n' into 10, so that we can use newline as a second barrier character.
32    let mut basins = Vec::with_capacity(256);
33    for y in 0..grid.height {
34        for x in 0..grid.width {
35            let point = Point::new(x, y);
36            if grid[point] & 0xf < 9 {
37                basins.push(flood_fill(&mut grid, point));
38            }
39        }
40    }
41
42    // Note that select_nth_unstable will partition the array faster than a full sort. With the
43    // partition in place, the final three elements are the largest.
44    let pivot = basins.len() - 3;
45    basins.select_nth_unstable_by_key(pivot, |b| b.size);
46
47    basins
48}
49
50pub fn part1(basins: &[Basin]) -> u32 {
51    basins.iter().map(|b| b.lowest + 1).sum()
52}
53
54pub fn part2(basins: &[Basin]) -> u32 {
55    // The list of basins is not sorted overall, but does have the largest three at the end.
56    basins[basins.len() - 3..].iter().map(|b| b.size).product()
57}
58
59fn flood_fill(grid: &mut Grid<u8>, point: Point) -> Basin {
60    let mut lowest = (grid[point] & 0xf) as u32;
61    let mut size = 1;
62    grid[point] = b'9';
63
64    for next in ORTHOGONAL.map(|d| point + d) {
65        if grid[next] & 0xf < 9 {
66            let basin = flood_fill(grid, next);
67            lowest = lowest.min(basin.lowest);
68            size += basin.size;
69        }
70    }
71
72    Basin { lowest, size }
73}
aoc/year2021/day09.rs

aoc/year2021/
day09.rs
