year2024/
day12.rs

1use utils::grid;
2use utils::prelude::*;
3
4/// Counting area, perimeter and sides of shapes in a grid.
5#[derive(Clone, Debug)]
6pub struct Day12 {
7    part1: u32,
8    part2: u32,
9}
10
11impl Day12 {
12    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
13        let (_, cols, grid) =
14            grid::from_str_padded(input, 1, 0, |b| b.is_ascii_uppercase().then_some(b))?;
15        let offsets = [-(cols as isize), 1, cols as isize, -1];
16
17        let mut visited = vec![false; grid.len()];
18        let (mut part1, mut part2) = (0, 0);
19        for i in 0..grid.len() {
20            if grid[i] == 0 || visited[i] {
21                continue;
22            }
23
24            let (area, perimeter, corners) = FloodFill::fill_shape(&grid, offsets, &mut visited, i);
25            part1 += area * perimeter;
26            part2 += area * corners;
27        }
28
29        Ok(Self { part1, part2 })
30    }
31
32    #[must_use]
33    pub fn part1(&self) -> u32 {
34        self.part1
35    }
36
37    #[must_use]
38    pub fn part2(&self) -> u32 {
39        self.part2
40    }
41}
42
43struct FloodFill<'a> {
44    grid: &'a [u8],
45    offsets: [isize; 4],
46    visited: &'a mut [bool],
47    area: u32,
48    perimeter: u32,
49    corners: u32,
50}
51
52impl<'a> FloodFill<'a> {
53    fn fill_shape(
54        grid: &'a [u8],
55        offsets: [isize; 4],
56        visited: &'a mut [bool],
57        i: usize,
58    ) -> (u32, u32, u32) {
59        let mut instance = Self {
60            grid,
61            offsets,
62            visited,
63            area: 0,
64            perimeter: 0,
65            corners: 0,
66        };
67        instance.visit(i);
68        (instance.area, instance.perimeter, instance.corners)
69    }
70
71    fn visit(&mut self, i: usize) {
72        let plant = self.grid[i];
73        self.visited[i] = true;
74        self.area += 1;
75
76        for d in 0..4 {
77            let neighbour1 = i.wrapping_add_signed(self.offsets[d]);
78            if self.grid[neighbour1] == plant {
79                if !self.visited[neighbour1] {
80                    self.visit(neighbour1);
81                }
82            } else {
83                self.perimeter += 1;
84            }
85
86            let neighbour2 = i.wrapping_add_signed(self.offsets[(d + 1) % 4]);
87            let between = i.wrapping_add_signed(self.offsets[d] + self.offsets[(d + 1) % 4]);
88            if ((self.grid[neighbour1] == plant) == (self.grid[neighbour2] == plant))
89                && (self.grid[neighbour1] != plant || self.grid[between] != plant)
90            {
91                self.corners += 1;
92            }
93        }
94    }
95}
96
97examples!(Day12 -> (u32, u32) [
98    {file: "day12_example0.txt", part1: 140, part2: 80},
99    {file: "day12_example1.txt", part1: 772},
100    {file: "day12_example2.txt", part1: 1930, part2: 1206},
101    {file: "day12_example3.txt", part2: 236},
102    {file: "day12_example4.txt", part2: 368},
103]);
year2024/day12.rs

year2024/
day12.rs
