aoc/year2025/
day04.rs

1//! # Printing Department
2//!
3//! To speed things up, we build a queue of rolls to be removed. For part one, the length of the
4//! initial list is the answer. For part two, as we remove rolls from the list one at a time, we
5//! update neighboring rolls. If any neighbor drops below the threshold, then we add it to the
6//! list. This approach avoids a time-consuming scan of the entire grid to find new rolls to remove.
7//!
8//! Either [breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search) using a
9//! `VecDeque` or [depth-first search](https://en.wikipedia.org/wiki/Depth-first_search) using
10//! a `Vec` will work. The depth-first search is faster, so we choose that.
11use crate::util::grid::*;
12use crate::util::point::*;
13
14type Input = (Vec<Point>, Grid<u8>);
15
16pub fn parse(input: &str) -> Input {
17    let grid = Grid::parse(input);
18    let offset = Point::new(1, 1);
19    let mut todo = Vec::new();
20    // Build a grid with an empty edge to avoid boundary checks.
21    let mut padded = Grid::new(grid.width + 2, grid.height + 2, u8::MAX);
22
23    for y in 0..grid.height {
24        for x in 0..grid.width {
25            let point = Point::new(x, y);
26
27            if grid[point] == b'@' {
28                let count = DIAGONAL
29                    .iter()
30                    .map(|&d| point + d)
31                    .filter(|&next| grid.contains(next) && grid[next] == b'@')
32                    .count();
33
34                // Add rolls that can be removed to the initial list.
35                if count < 4 {
36                    todo.push(point + offset);
37                }
38                padded[point + offset] = count as u8;
39            }
40        }
41    }
42
43    (todo, padded)
44}
45
46pub fn part1(input: &Input) -> usize {
47    let (todo, _) = input;
48    todo.len()
49}
50
51pub fn part2(input: &Input) -> usize {
52    let (mut todo, mut padded) = input.clone();
53    let mut removed = 0;
54
55    // Update neighbors as rolls are removed. If they drop below the threshold, then add to the list.
56    while let Some(point) = todo.pop() {
57        removed += 1;
58
59        for next in DIAGONAL.map(|d| point + d) {
60            if padded[next] == 4 {
61                todo.push(next);
62            }
63            padded[next] -= 1;
64        }
65    }
66
67    removed
68}
aoc/year2025/day04.rs

aoc/year2025/
day04.rs
