aoc/year2021/
day09.rs

1//! # Smoke Basin
2//!
3//! Part 2 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 auxilary 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. 2 dimensional grids are common in Advent of Code
11//! problems so we use our utility [`Grid`] and [`Point`] modules.
12//!
13//! [`VecDeque`]: std::collections::VecDeque
14//! [`Grid`]: crate::util::grid
15//! [`Point`]: crate::util::point
16use crate::util::grid::*;
17use crate::util::parse::*;
18use crate::util::point::*;
19
20pub fn parse(input: &str) -> Grid<u8> {
21    Grid::parse(input)
22}
23
24pub fn part1(grid: &Grid<u8>) -> u32 {
25    let mut risk_levels = 0;
26
27    for x in 0..grid.width {
28        for y in 0..grid.height {
29            let point = Point::new(x, y);
30            let cur = grid[point];
31            let low_point = ORTHOGONAL
32                .iter()
33                .map(|&n| point + n)
34                .filter(|&n| grid.contains(n))
35                .all(|n| grid[n] > cur);
36
37            if low_point {
38                risk_levels += 1 + cur.to_decimal() as u32;
39            }
40        }
41    }
42
43    risk_levels
44}
45
46pub fn part2(input: &Grid<u8>) -> u32 {
47    let mut grid = input.clone();
48    let mut basins = Vec::new();
49
50    for x in 0..grid.width {
51        for y in 0..grid.height {
52            let next = Point::new(x, y);
53            if grid[next] < b'9' {
54                basins.push(flood_fill(&mut grid, next));
55            }
56        }
57    }
58
59    basins.sort_unstable();
60    basins.iter().rev().take(3).product()
61}
62
63fn flood_fill(grid: &mut Grid<u8>, point: Point) -> u32 {
64    grid[point] = b'9';
65    let mut size = 1;
66
67    for next in ORTHOGONAL.iter().map(|&n| point + n) {
68        if grid.contains(next) && grid[next] < b'9' {
69            size += flood_fill(grid, next);
70        }
71    }
72
73    size
74}
aoc/year2021/day09.rs

aoc/year2021/
day09.rs
