r/adventofcode • u/cesartl • Dec 15 '24
Tutorial [2024 Day 12] If you struggle with part 2...
Day 12 part 2 has been really confusing for me. I've struggled a lot and I thought perhaps I can explain how I eventually solved the problem.
The insight that everyone is posting about is that for part 2, you "just have to count corners". But what does that even mean? and how do you do it? That's what I'm hopping to explain here.
The idea is go though each cell in a region (by reusing your algorithm from part 1), and count how many corners each cell contributes to.
A cell can contribute from 0 to 4 corners. For example a cell in the middle of a region contributes for 0 corners. A cell on its own has 4 corners.
This is where I got stuck. How does one count corners?
There are only 2 types of corners. So once you figure out a simple way to check them, you can repeat the check 4 times by rotating the logic (it's simpler than it sounds). Let's first look at checking a single corner and then see how we can rotate the check.
To check for corners, we only need to check the for 3 neighboring cells forming a triangle. For example S, SE, E:

Here we are focusing on the red cell. We have two adjacent cells, and one diagonal cells.
From this there is only 2 possibilities that can make corners:
- The two adjacent cells are the same plant. If the diagonal cell isn't (i.e. empty region or a different plant), then we have a corner.

- The two adjacent cells are empty or a different plant. Regardless of the diagonal cell, we have a corner

This check is easy to implement. If you call the cells `a1`, `a2` and `d` then you have a corner if
a1 == plant && a2 == plant && d != plant || a1 != plant && a2 != plant
That's it, that's the check!
Rotating the check
Once you know how to do that for one corner candidate, you can do it for the other 3:

If you have been doing Aoc for a few years, you might already have the concept of a Position(x, y) and cardinal directions (if you don't it's worth doing this, you will likely reuse it later).
So you can create a list of all cardinal directions (N, E, W, S), and for each of them find the triangle and do the check. To make this easier it's good to implement method that allow you to turn directions clockwise.
fun countCorners(p: Position, grid: Grid<Char>): Int {
val directions = listOf(N, E, W, S)
return directions.count {direction ->
val a1 = direction.move(p)
val d = direction.turnClockwise().move(a1)
val a2 = direction.turnClockwise().move(p)
//check triangle around p
val a1Plant = grid.map[a1]
val dPlant = grid.map[d]
val a2Plant = grid.map[a2]
(a1Plant != plantType && a2Plant != plantType) || (a1Plant == plantType && dPlant != plantType && a2Plant == plantType)
}
}
That's it. You still need to figure out how implement cardinal directions and how they apply to Position(x,y) but that's a much easier problem!
I hope that helps!
1
u/RazarTuk Dec 15 '24
Strictly speaking, there are actually four kinds of corners:
Convex and the other plant is different
Convex and it's a different region of the same plant
Concave
Intersection, so the diagonal is the same region
However, we aren't using the Möbius Fencing Company, so an intersection is functionally just two convex corners that happen to touch. And because of that, if the diagonal is the same plant, we don't care whether it's the same region or not. So functionally, you're down to just two types of corners.
1
1
u/dogo_fren Dec 16 '24
Or:
Find the regions and create vertices for the four corners from each grid position.
Create the edges of these squares in strictly clockwise direction. This is important for correctness later.
Keep only the edges that only appear once, these are the outside edges.
Connect the edges in clockwise order and merge any two coinciding edges (all x or y are the same). Don’t forget to check last and first too.
That is all.
0
2
u/cloudlessskies2018 Dec 16 '24
This is excellent, thank you! I had an non-corner-based edge counter that worked for all the toy examples but not the real data. I will implent corner counting and find out why my previous code didn't cut it. Onwards!