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 the end of each straight side in the clockwise direction.
9//! A side ends when the next plot along it is outside the region (an outer corner), or
10//! the diagonal plot across the edge is inside the region (an inner corner).
11use crate::util::grid::*;
12use crate::util::point::*;
13
14type Input = (usize, usize);
15
16pub fn parse(input: &str) -> Input {
17    // A newline border allows us to avoid boundary checks.
18    let grid = Grid::parse_with_border(input);
19
20    let mut todo = Vec::new();
21    let mut seen = grid.same_size_with(false);
22
23    let mut part_one = 0;
24    let mut part_two = 0;
25
26    // Iterate over every point, skipping the border.
27    for y in 1..grid.height - 1 {
28        for x in 1..grid.width {
29            let start = Point::new(x, y);
30            let same = |point| grid[point] == grid[start];
31
32            // Skip already filled points.
33            if seen[start] {
34                continue;
35            }
36
37            // Flood fill.
38            let mut area = 0;
39            let mut perimeter = 0;
40            let mut sides = 0;
41
42            todo.push(start);
43            seen[start] = true;
44
45            while let Some(point) = todo.pop() {
46                area += 1;
47
48                for direction in ORTHOGONAL {
49                    let next = point + direction;
50
51                    if same(next) {
52                        if !seen[next] {
53                            todo.push(next);
54                            seen[next] = true;
55                        }
56                    } else {
57                        let clockwise = direction.clockwise();
58                        perimeter += 1;
59                        sides += usize::from(!same(point + clockwise) || same(next + clockwise));
60                    }
61                }
62            }
63
64            part_one += area * perimeter;
65            part_two += area * sides;
66        }
67    }
68
69    (part_one, part_two)
70}
71
72pub fn part1(input: &Input) -> usize {
73    input.0
74}
75
76pub fn part2(input: &Input) -> usize {
77    input.1
78}
aoc/year2024/day12.rs

aoc/year2024/
day12.rs
