aoc/year2024/
day12.rs

1//! # Garden Groups
2//!
3//! Solves both parts simultaneously by flood filling each region.
4//!
5//! For part one we increment the perimeter for each neighboring plot belonging to a different
6//! region or out of bounds.
7//!
8//! For part two we count each plot on the edge as either 0, 1 or 2 sides then divide by 2.
9//! An edge plot contributes nothing if it has 2 edge neighbors facing the same way,
10//! one if it has a single neighbor and two if it has no neighbors.
11//!
12//! For example, considering the right edge:
13//!
14//! ```none
15//! ...        ...        .#. > 1
16//! .#. > 2    .#. > 1    .#. > 0
17//! ...        .#. > 1    .#. > 1
18//! ```
19use crate::util::grid::*;
20use crate::util::point::*;
21
22type Input = (usize, usize);
23
24pub fn parse(input: &str) -> Input {
25    // A newline border allows us to avoid boundary checks.
26    let grid = Grid::parse_with_border(input);
27
28    let mut todo = Vec::new();
29    let mut edge = Vec::new();
30    let mut seen = grid.same_size_with(false);
31
32    let mut part_one = 0;
33    let mut part_two = 0;
34
35    // Iterate over every point, skipping the border.
36    for y in 1..grid.height - 1 {
37        for x in 1..grid.width {
38            // Skip already filled points.
39            let point = Point::new(x, y);
40            if seen[point] {
41                continue;
42            }
43
44            // Flood fill, using area as an index.
45            let kind = grid[point];
46            let check = |point| grid[point] == kind;
47
48            let mut area = 0;
49            let mut perimeter = 0;
50
51            todo.push(point);
52            seen[point] = true;
53
54            while area < todo.len() {
55                let point = todo[area];
56                area += 1;
57
58                for direction in ORTHOGONAL {
59                    let next = point + direction;
60
61                    if check(next) {
62                        if !seen[next] {
63                            todo.push(next);
64                            seen[next] = true;
65                        }
66                    } else {
67                        edge.push((point, direction));
68                        perimeter += 1;
69                    }
70                }
71            }
72
73            // Sum sides for all plots in the region.
74            let mut sides = 0;
75
76            for &(p, d) in &edge {
77                for t in [d.clockwise(), d.counter_clockwise()] {
78                    sides += usize::from(!check(p + t) || check(p + t + d));
79                }
80            }
81
82            todo.clear();
83            edge.clear();
84
85            part_one += area * perimeter;
86            part_two += area * (sides / 2);
87        }
88    }
89
90    (part_one, part_two)
91}
92
93pub fn part1(input: &Input) -> usize {
94    input.0
95}
96
97pub fn part2(input: &Input) -> usize {
98    input.1
99}
aoc/year2024/day12.rs

aoc/year2024/
day12.rs
