year2025/
day04.rs

1use utils::grid;
2use utils::prelude::*;
3
4/// Iteratively removing cells with less than 4 neighbours.
5#[derive(Clone, Debug)]
6pub struct Day04 {
7    rows: usize,
8    cols: usize,
9    grid: Vec<bool>,
10}
11
12impl Day04 {
13    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
14        let (rows, cols, grid) = grid::parse(
15            input,
16            1,
17            false,
18            |c| c == b'@',
19            |c| c == b'@' || c == b'.',
20            |_, _| Err("expected '.' or '@'"),
21        )?;
22
23        Ok(Self { rows, cols, grid })
24    }
25
26    #[must_use]
27    pub fn part1(&self) -> u32 {
28        // Avoids bounds checks, allowing the inner loop to be vectorized
29        let mut total = 0;
30        for ((above, row), below) in self
31            .grid
32            .chunks_exact(self.cols)
33            .zip(self.grid.chunks_exact(self.cols).skip(1))
34            .zip(self.grid.chunks_exact(self.cols).skip(2))
35        {
36            for i in 1..self.cols - 1 {
37                let neighbours = u8::from(above[i - 1])
38                    + u8::from(above[i])
39                    + u8::from(above[i + 1])
40                    + u8::from(row[i - 1])
41                    + u8::from(row[i + 1])
42                    + u8::from(below[i - 1])
43                    + u8::from(below[i])
44                    + u8::from(below[i + 1]);
45                total += u32::from(row[i] & (neighbours < 4));
46            }
47        }
48        total
49    }
50
51    #[must_use]
52    pub fn part2(&self) -> u32 {
53        let mut total = 0;
54        let mut grid = self.grid.clone();
55
56        // Store which rows need to be recomputed, reducing the number of row updates by >50%
57        let mut rows_to_update = vec![true; self.rows];
58
59        // Each cell can be updated in-place as the update rule only ever removes rolls and the
60        // order they are removed does not matter.
61        // However, doing this prevents vectorization, as each inner loop iteration now depends on
62        // the previous iteration.
63        // Instead, write the new row to a separate buffer to allow vectorization, then copy it back
64        // before processing the following row.
65        // This still allows more removals to be done per grid iteration compared to writing to a
66        // second grid.
67        let mut new_row = vec![false; self.cols];
68
69        loop {
70            let prev_total = total;
71
72            for r in 1..self.rows - 1 {
73                if !rows_to_update[r] {
74                    continue;
75                }
76
77                let above = &grid[(r - 1) * self.cols..r * self.cols];
78                let row = &grid[r * self.cols..(r + 1) * self.cols];
79                let below = &grid[(r + 1) * self.cols..(r + 2) * self.cols];
80
81                let before_row_total = total;
82                for i in 1..self.cols - 1 {
83                    let neighbours = u8::from(above[i - 1])
84                        + u8::from(above[i])
85                        + u8::from(above[i + 1])
86                        + u8::from(row[i - 1])
87                        + u8::from(row[i + 1])
88                        + u8::from(below[i - 1])
89                        + u8::from(below[i])
90                        + u8::from(below[i + 1]);
91                    let remove = row[i] & (neighbours < 4);
92                    total += u32::from(remove);
93                    new_row[i] = row[i] & !remove;
94                }
95
96                grid[r * self.cols..(r + 1) * self.cols].copy_from_slice(&new_row);
97
98                if before_row_total != total {
99                    // Row has been updated, need to update it again as well as its neighbours
100                    rows_to_update[r - 1] = true;
101                    rows_to_update[r + 1] = true;
102                } else {
103                    rows_to_update[r] = false;
104                }
105            }
106
107            if total == prev_total {
108                return total;
109            }
110        }
111    }
112}
113
114examples!(Day04 -> (u32, u32) [
115    {file: "day04_example0.txt", part1: 13, part2: 43},
116]);
year2025/day04.rs

year2025/
day04.rs
