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            let mut sides = 0;
51
52            todo.push(point);
53            seen[point] = true;
54
55            while area < todo.len() {
56                let point = todo[area];
57                area += 1;
58
59                for direction in ORTHOGONAL {
60                    let next = point + direction;
61
62                    if check(next) {
63                        if !seen[next] {
64                            todo.push(next);
65                            seen[next] = true;
66                        }
67                    } else {
68                        edge.push((point, direction));
69                        perimeter += 1;
70                    }
71                }
72            }
73
74            // Sum sides for all plots in the region.
75            for &(p, d) in &edge {
76                let r = d.clockwise();
77                let l = d.counter_clockwise();
78
79                sides += (!check(p + l) || check(p + l + d)) as usize;
80                sides += (!check(p + r) || check(p + r + d)) as usize;
81            }
82
83            todo.clear();
84            edge.clear();
85
86            part_one += area * perimeter;
87            part_two += area * (sides / 2);
88        }
89    }
90
91    (part_one, part_two)
92}
93
94pub fn part1(input: &Input) -> usize {
95    input.0
96}
97
98pub fn part2(input: &Input) -> usize {
99    input.1
100}
aoc/year2024/day12.rs

aoc/year2024/
day12.rs
