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

year2024/
day12.rs
