Advent of Code 2024 Day 12

Day 12: Garden Groups

https://adventofcode.com/2024/day/12

Today’s input is the layout of the huge garden plot you are at.

An example input looks like this:

RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE

It’s a 2D-grid again where each letter signals a type of crop that grows in that location.

Parsing

If you’ve been following along, you know what I do when I see a grid puzzle by now, Point!

`Point`

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct Point {
    row: i32,
    col: i32,
}

impl Point {
    fn new(row: i32, col: i32) -> Self {
        Self { row, col }
    }
}

I stored each letter in a map again. This is not the most efficient way to store this, but it’s very nice to work with and think about.

fn parse(input: &str) -> HashMap<Point, char> {
    let mut map = HashMap::new();
    for (row, line) in input.lines().enumerate() {
        for (col, c) in line.chars().enumerate() {
            let point = Point::new(row as i32, col as i32);
            map.insert(point, c);
        }
    }
    map
}

Part 1

The elves want to put up fences around regions of plots that grow the same crop. A plot that touches another plot (up/right/down/left) that grows the same crop belongs to the same region.

You need to figure out each plot’s area and perimeter. The price for an amount of fence is area * perimeter. Don’t ask why, the answer is ✨reasons✨.

The question asks for the sum of all region prices.

Some skeleton/pseudo-code

let map = parse(input);
let mut sum = 0;
for (point, crop) in &map {
  // ignore points that are already contributing to the sum
  let shape = shape(point, crop);
  let area = area(shape);
  let circumference = circumference(shape);
  sum += area * circumference;
}
sum

Helpers

Time to write the code that can make my skeleton-code a reality.

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct Point {
    row: i32,
    col: i32,
}

impl Point {
    fn new(row: i32, col: i32) -> Self {
        Self { row, col }
    }

    fn add(&self, other: &Self) -> Self {
        Self::new(self.row + other.row, self.col + other.col)
    }

    fn same_neighbours(&self, map: &HashMap<Point, char>, target_crop: char) -> Vec<Self> {
        let mut neighbours = Vec::new();
        for dir in Self::dirs() {
            let next = self.add(&dir);
            if map.get(&next).is_some_and(|&crop| crop == target_crop) {
                neighbours.push(next);
            }
        }
        neighbours
    }

    fn dirs() -> [Point; 4] {
        [
            // up
            Self::new(-1, 0),
            // right
            Self::new(0, 1),
            // down
            Self::new(1, 0),
            // left
            Self::new(0, -1),
        ]
    }
}

fn shape(
    start: Point,
    crop: char,
    map: &HashMap<Point, char>,
    seen: &mut HashSet<Point>,
) -> HashSet<Point> {
    let mut q = VecDeque::new();
    let mut shape = HashSet::new();
    q.push_back(start);
    shape.insert(start);

    while let Some(point) = q.pop_front() {
        for neighbour in point.same_neighbours(map, crop) {
            if seen.insert(neighbour) {
                shape.insert(neighbour);
                q.push_back(neighbour);
            }
        }
    }

    shape
}

fn circumference(map: &HashMap<Point, char>, shape: &HashSet<Point>) -> usize {
    shape
        .iter()
        .map(|point| 4 - point.same_neighbours(map, map[point]).len())
        .sum()
}

Code

A global set makes sure I don’t count garden plots that already contribute to the sum twice. Each time a shape (a set of Points) is calculated, those Points are added to the set so they can’t be included in future shapes.

You might have noticed the distinct lack of area(), well, that’s a oneliner and making a function for it would be a bit silly.

fn part_1(input: &str) -> usize {
    let map = parse(input);
    let mut seen = HashSet::new();
    let mut sum = 0;
    for (point, crop) in &map {
        if seen.contains(point) {
            continue;
        }
        let shape = shape(*point, *crop, &map, &mut seen);
        let area = shape.len();
        let circumference = circumference(&map, &shape);
        sum += area * circumference;
    }
    sum
}

Part 2

Instead of the circumference of garden plots, use the amount of sides the plot has.

The question asks for the sum of all region prices again.

Some skeleton/pseudo-code again, changing circumference to sides:

let map = parse(input);
let mut sum = 0;
for (point, crop) in &map {
  // ignore points that are already contributing to the sum
  let shape = shape(point, crop);
  let area = area(shape);
  let sides = sides(shape);
  sum += area * sides;
}
sum

Helpers

Updating the helpers from part 1. The most interesting is the sides function, which I adapted from solutions I saw only. It chooses a direction, goes in it until the garden plot ends, and then follows the side in the perpendicular direction until that ends.

impl Point {
    // -- snip --
    fn perp(&self) -> Self {
        // turn and face a perpendicular direction
        // does not matter if (row, col) turns into (-col, row) or (col, row) for this algorithm
        Point::new(-self.col, self.row)
    }
}

fn sides(shape: HashSet<Point>) -> usize {
    let mut sides = HashSet::new();
    for point in &shape {
        for dir in Point::dirs() {
            // look for first out of bounds element in dir
            if shape.contains(&point.add(&dir)) {
                continue;
            }
            // perpendicular dir
            let perp = dir.perp();
            let mut curr = *point;

            // keep moving in the perpendicular direction while:
            // - a block in the perpendicular direction exists
            // - a block in the original direction doesn't exist
            while shape.contains(&curr.add(&perp)) && !shape.contains(&curr.add(&dir)) {
                curr = curr.add(&perp);
            }
            // when edge was followed, add this (point, dir) to the sides.
            // include dir because 1 point has 4 sides
            sides.insert((curr, dir));
        }
    }
    sides.len()
}

Code

fn part_2(input: &str) -> usize {
    let map = parse(input);
    let mut seen = HashSet::new();
    let mut sum = 0;
    for (point, crop) in &map {
        if seen.contains(point) {
            continue;
        }
        let shape = shape(*point, *crop, &map, &mut seen);
        let area = shape.len();
        let sides = sides(shape);
        sum += area * sides;
    }
    sum
}

Final code

1
use std::collections::{HashMap, HashSet, VecDeque};
2

3
#[derive(PartialEq, Eq, Hash, Clone, Copy)]
4
struct Point {
5
    row: i32,
6
    col: i32,
7
}
8

9
impl Point {
10
    fn new(row: i32, col: i32) -> Self {
11
        Self { row, col }
12
    }
13

14
    fn add(&self, other: &Self) -> Self {
15
        Self::new(self.row + other.row, self.col + other.col)
16
    }
17

18
    fn same_neighbours(&self, map: &HashMap<Point, char>, target_crop: char) -> Vec<Self> {
19
        let mut neighbours = Vec::new();
20
        for dir in Self::dirs() {
21
            let next = self.add(&dir);
22
            if map.get(&next).is_some_and(|&crop| crop == target_crop) {
23
                neighbours.push(next);
24
            }
25
        }
26
        neighbours
27
    }
28

29
    fn dirs() -> [Point; 4] {
30
        [
31
            // up
32
            Self::new(-1, 0),
33
            // right
34
            Self::new(0, 1),
35
            // down
36
            Self::new(1, 0),
37
            // left
38
            Self::new(0, -1),
39
        ]
40
    }
41

42
    fn perp(&self) -> Self {
43
        // does not matter if (row, col) turns into (-col, row) or (col, row) for this algorithm
44
        Point::new(-self.col, self.row)
45
    }
46
}
47

48
fn parse(input: &str) -> HashMap<Point, char> {
49
    let mut map = HashMap::new();
50
    for (row, line) in input.lines().enumerate() {
51
        for (col, c) in line.chars().enumerate() {
52
            let point = Point::new(row as i32, col as i32);
53
            map.insert(point, c);
54
        }
55
    }
56
    map
57
}
58

59
fn shape(
60
    start: Point,
61
    crop: char,
62
    map: &HashMap<Point, char>,
63
    seen: &mut HashSet<Point>,
64
) -> HashSet<Point> {
65
    let mut q = VecDeque::new();
66
    let mut shape = HashSet::new();
67
    q.push_back(start);
68
    shape.insert(start);
69

70
    while let Some(point) = q.pop_front() {
71
        for neighbour in point.same_neighbours(map, crop) {
72
            if seen.insert(neighbour) {
73
                shape.insert(neighbour);
74
                q.push_back(neighbour);
75
            }
76
        }
77
    }
78

79
    shape
80
}
81

82
fn circumference(map: &HashMap<Point, char>, shape: &HashSet<Point>) -> usize {
83
    shape
84
        .iter()
85
        .map(|point| 4 - point.same_neighbours(map, map[point]).len())
86
        .sum()
87
}
88

89
fn sides(shape: HashSet<Point>) -> usize {
90
    let mut sides = HashSet::new();
91
    for point in &shape {
92
        for dir in Point::dirs() {
93
            // look for first out of bounds element in dir
94
            if shape.contains(&point.add(&dir)) {
95
                continue;
96
            }
97
            // perpendicular dir
98
            let perp = dir.perp();
99
            let mut curr = *point;
100

101
            // keep moving in the perpendicular direction while:
102
            // - a block in the perpendicular direction exists
103
            // - a block in the original direction doesn't exist
104
            while shape.contains(&curr.add(&perp)) && !shape.contains(&curr.add(&dir)) {
105
                curr = curr.add(&perp);
106
            }
107
            // when edge was followed, add this (point, dir) to the sides.
108
            // include dir because 1 point has 4 sides
109
            sides.insert((curr, dir));
110
        }
111
    }
112
    sides.len()
113
}
114

115
pub fn part_1(input: &str) -> usize {
116
    let map = parse(input);
117
    let mut seen = HashSet::new();
118
    let mut sum = 0;
119
    for (point, crop) in &map {
120
        if seen.contains(point) {
121
            continue;
122
        }
123
        let shape = shape(*point, *crop, &map, &mut seen);
124
        let area = shape.len();
125
        let circumference = circumference(&map, &shape);
126
        sum += area * circumference;
127
    }
128
    sum
129
}
130

131
pub fn part_2(input: &str) -> usize {
132
    let map = parse(input);
133
    let mut seen = HashSet::new();
134
    let mut sum = 0;
135
    for (point, crop) in &map {
136
        if seen.contains(point) {
137
            continue;
138
        }
139
        let shape = shape(*point, *crop, &map, &mut seen);
140
        let area = shape.len();
141
        let sides = sides(shape);
142
        sum += area * sides;
143
    }
144
    sum
145
}

Date

Tagged

Part of series

Older post

Newer post

Advent of Code 2024 Day 12

Day 12: Garden Groups

Parsing

`Point`

Part 1

Helpers

Code

Part 2

Helpers

Code

Final code