Advent of Code 2024, Day 12

This is again a flood fill exercise with some curveball thrown in for good measure to check their perimeter. Nothing hard.

adventofcode2024/day12 at main · javorszky/adventofcode2024

Contribute to javorszky/adventofcode2024 development by creating an account on GitHub.

GitHubjavorszky

Spoilers

Part 1

Given a map with different plants (letters), find the distinct regions that are made up of fields where the same plant (letter) is grown and they touch on their sides. If they only touch diagonally, they don’t count as one region.

Then count the length of the perimeter, and give each region a price that’s calculated by multiplying its area with its perimeter.

Approach here is flood fill again: parse the input into a HashMap<Coordinate, String> where the value is the letter of the plant being grown.

Then for each entry (Coordinate) in the map, start by looking at all four of its neighbours: if it’s not the same letter as the one we started on, it doesn’t belong in the same region. Add the current coordinate to the visited HashSet, then pass each of the valid coordinates to the same function, so it will be recursive. Bail if we’ve visited that spot before.

What we’re left with if a bunch of regions which have a HashSet<Coordinate>. To count the area, we use the .len() method on the set, and we’re done. I made this into a method.

To get the perimeter I added a method that will visit each coordinates in a region exactly once, checks all 4 of their neighbours, and if those neighbour coordinates are not found in the region, adds +1 to the perimeter length.

Once we have these methods in place, the correct result is calling region.area() * region.perimeter() for each region and adding the results together.

Part 2

The only complication here is that occasionally perimeter items need to be merged.

Way I solved it is I normalised everything to the left or down.

First for every plot of a region, I check its neighbours. If there isn’t a neighbour that way, I add a directional fence tuple to a set that looks like this: HashSet<(Coordinate, Side>. That allows me to store all sides separately for the same coordinate.

Then for every entry in that set I check which way the fence goes. If it’s either Up or Down, I find the leftmost plot that still has a fence the same way. I go one by one, so I know the fence will be unbroken. Once I found that, I add the leftmost coordinate and fence location to a visited set, so if I land on a different part of the same side I won’t double count it.

Then I check to the right one by one, and once I run out of plots, I add the leftmost plot’s coordinate, the way the fence is, and its length to a HashMap<(Coordinate, Side), length>.

For Left and Right the process is exactly the same, except first I find the bottom–most plot, then work my way up.

All that’s left is to calculate the scores: multiple each region’s area with its sides that we just calculated. We don’t actually care how long those sides are.

After my ⭐️⭐️ I can finally go to sleep.

Spoiler photo by Lucas Degenhardt on Unsplash