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 neighbouring 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 neighbours facing the same way,
10//! one if has a single neighbour and two if it has no neighbours.
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    let grid = Grid::parse(input);
26
27    let mut todo = Vec::new();
28    let mut edge = Vec::new();
29    let mut seen = grid.same_size_with(false);
30
31    let mut part_one = 0;
32    let mut part_two = 0;
33
34    for y in 0..grid.height {
35        for x in 0..grid.width {
36            // Skip already filled points.
37            let point = Point::new(x, y);
38            if seen[point] {
39                continue;
40            }
41
42            // Flood fill, using area as an index.
43            let kind = grid[point];
44            let check = |point| grid.contains(point) && grid[point] == kind;
45
46            let mut area = 0;
47            let mut perimeter = 0;
48            let mut sides = 0;
49
50            todo.push(point);
51            seen[point] = true;
52
53            while area < todo.len() {
54                let point = todo[area];
55                area += 1;
56
57                for direction in ORTHOGONAL {
58                    let next = point + direction;
59
60                    if check(next) {
61                        if !seen[next] {
62                            todo.push(next);
63                            seen[next] = true;
64                        }
65                    } else {
66                        edge.push((point, direction));
67                        perimeter += 1;
68                    }
69                }
70            }
71
72            // Sum sides for all plots in the region.
73            for &(p, d) in &edge {
74                let r = d.clockwise();
75                let l = d.counter_clockwise();
76
77                sides += (!check(p + l) || check(p + l + d)) as usize;
78                sides += (!check(p + r) || check(p + r + d)) as usize;
79            }
80
81            todo.clear();
82            edge.clear();
83
84            part_one += area * perimeter;
85            part_two += area * (sides / 2);
86        }
87    }
88
89    (part_one, part_two)
90}
91
92pub fn part1(input: &Input) -> usize {
93    input.0
94}
95
96pub fn part2(input: &Input) -> usize {
97    input.1
98}
aoc/year2024/day12.rs

aoc/year2024/
day12.rs
