Advent of Code 2024 - Day 12, in Kotlin - Garden Groups • Todd Ginsberg

So far, Advent of Code 2024 has been really enjoyable for me. This puzzle lets us write another Breadth-First Search, and we do some fun checks to find patterns in our garden.

If you’d rather just view the code, my GitHub Repository is here.

Puzzle Input

We will take today’s input as a List<String> and unlike previous days, we’ll call it garden to make the code below look better. We’ll declare this as a private val local to the class, rather than parse it any further here.

class Day12(private val garden: List<String>) {

}

⭐ Day 12, Part 1

The puzzle text can be found here.

Once again we need a couple of extension functions to make working with our garden easier, and once again I am going to declare them private to the Day12 class rather than put them in a general extensions file.

First up, we’ll implement the contains operator so we can say things like point in garden or point !in garden to test if a point is in the garden.

// In Day12

private operator fun List<String>.contains(at: Point2D): Boolean =
    at.y in indices && at.x in get(at.y).indices

Next, we’ll implement the get operator which unlike previous days returns a nullable Char?. This is because we’re doing a lot of comparisons like “is this char the same as that other char, or null?” and returning null makes these tests look better.

// In Day12

private operator fun List<String>.get(at: Point2D): Char? =
    if (at in this) this[at.y][at.x] else null

We also need a data class to store data about each Region. We absolutely need the area and the perimeter. You can leave off the region’s name if you want, I found it helpful for debugging but it isn’t used for any of the calculations.

// In Day12

private data class Region(
	val name: Char, val area: Int, val perimeter: Int
)

Next we need to know, given a start point, how to find the entire region that Point2D is part of. We also want to make sure that we keep track of the places we’ve seen, so we’ll also take in a MutableSet<Point2D>. This will be used to track the set of points that make up regions we’ve already evaluated. Another way to do this would have been to null out places in the garden, but this seemed more clear to me and kept our garden immutable.

We will call our region finding function findRegion and it will be implemented as a Breadth-First Search.

// In Day12

private fun findRegion(start: Point2D, seen: MutableSet<Point2D>): Region {
    val target: Char = garden[start]!!
    val queue = mutableListOf(start)
    var area = 0
    var perimeter = 0

    while (queue.isNotEmpty()) {
        val place = queue.removeFirst()
        if (garden[place] == target && place !in seen) {
            seen += place
            area++
            val neighbors = place.cardinalNeighbors()
            queue.addAll(neighbors)
            perimeter += neighbors.count { garden[it] != target }
        }
    }
    return Region(target, area, perimeter)
}

The first thing we want to do is get the target, or the letter of the region at the start point. We also need a work queue of places to examine, which we will seed with the start point. We’ll declare vars for both total area and total perimeter.

While we have work to do (the queue.isNotEmpty), we will remove the first place from the queue. If the place in the garden is the same as our target, and we haven’t seen it yet, we will consider this new place part of the region we’re working on.

In that case, we’ve now seen this place, and we can consider it part of our area, which we increment by 1. Next, we find all of the cardinalNeighbors() and add them to the work queue. We could filter out places outside the garden here but since we account for that when pulling places off of the work queue as part of the target equality test, it isn’t really required here. Next we count how many of the neighbors do not match the target (either because they are a different region or they are outside of the garden) and add that number to our perimeter count.

Finally, we return the Region with its area total and perimeter total.

Now we need to go through the garden and find all of the regions, which we will do with findRegions.

// In Day12

private fun findRegions(): List<Region> {
    val seen = mutableSetOf<Point2D>()
    return garden.flatMapIndexed { y, row ->
        row.mapIndexedNotNull { x, _ ->
            val place = Point2D(x, y)
            if (place !in seen) findRegion(place, seen)
            else null
        }
    }
}

Because we don’t want to find the same region more than once, we need to keep track of all the places that we’ve seen already. As we saw above when we implemented findRegion, we have a single seen set that we share between invocations that findRegion uses to say “I’m claiming this place for a region”. We’ll declare that set here.

Next, we map/index through all of the x/y spots in the garden and if we haven’t seen them yet, we know we’re looking at a new region. We’ll create a Point2D and use it to call findRegion. If we have seen the place, we can return null from this inner loop, indicating this place is already part of some other region we’ve found.

Because the inner loop uses mapIndexedNotNull, we can safely return null there, which means findRegions can safely return a List<Region>, which are all non-null.

Calling findRegions and taking the sumOf the products of area and perimeter gives us the answer to part 1.

// In Day12

fun solvePart1(): Int =
    findRegions().sumOf { it.area * it.perimeter }

Star earned! Onward!

⭐ Day 12, Part 2

The puzzle text can be found here.

We’re going to have to do a bit of refactoring to track the number of sides in each Region. First, we need to add a sides variable to our Region (highlighted below).

// In Day12

private data class Region(
	val name: Char, 
	val area: Int, 
	val perimeter: Int, 
	val sides: Int
)

How are we going to calculate the number of sides in a given region? Initially I had started off with something to find all of the edge places and count up the number of unique X and Y coordinates (depending on the orientation of the side), but that seemed really confusing when I coded it up. While drawing pictures of regions to get some insight, it occurred to me that ion order to count the number of sides one of our regions has, we can also count the number of corners it has. They’ll get us the same answer. Go ahead and try to draw a shape with 90 degree angles like today’s regions and not have sides equal corners.

This means we need a function that for every Point2D in a region, we can answer the question “how many corners does this represent?”.

We will do this by adding a countCorners() extension on Point2D, private to today’s solution class. Now to find a corner, we probably want to know what we’re looking for. Let’s look at a picture of an inner corner and an outer corner.


  Outer 

  BBBBBB
  BBaAAA
  BBAAAA
  BBAAAA

I’ve lowercased one of the A’s to make the example more clear, pretend it is uppercase. If we examine that “a”, we can see it is an outer corner. We can identify it because the spot immediately to the North (up) of it is from a different region, as is the spot immediately to the West (left) of it. The North and West spots may be in different regions from one another, the important part is they aren’t in the same region as “a”.


  Inner

  BBBBBB
  BBAAAA
  BAaAAA
  BAAAAA

Same deal as above, I’ve lowercased an A to make the example easier to follow. A spot can be an inner corner because both the North (up) and West (left) spots in are the same region but the NorthWest (up + left) spots is in a different region.

This is all well and good for North and West, but we need to try every adjacent combination: North & East, East & South, South & West, West & North for both methods. If we can code this, we can identify corners, which allows us to count the number of sides for reach region.

// In Day12

private fun Point2D.countCorners(): Int =
    listOf(Point2D.NORTH, Point2D.EAST, Point2D.SOUTH, Point2D.WEST, Point2D.NORTH)
        .zipWithNext()
        .map { (first, second) ->
            listOf(
                garden[this],
                garden[this + first],
                garden[this + second],
                garden[this + first + second]
            )
        }.count { (target, side1, side2, corner) ->
            (target != side1 && target != side2) || 
            (side1 == target && side2 == target && corner != target)
        }

The first thing countCorners does is set up a list of offset points. You’ll notice NORTH is in there twice, this is because we use zipWithNext to pair them up and we want a loop. Leaving off that last NORTH wouldn’t give us the WEST to NORTH relationship we want.

Next, we destructure the Pairs created by zipWithNext into first and second to make the code easier to read and map those into the values at each of the points we care about: the point we’re looking at, the point in one direction (say, North), the point in the adjacent direction (say, East), and the point in between (say, NorthEast). We can do this because our Point2D class implements the addition operator.

Finally, we count how many of these relationship pairs meet the criteria in the diagrams above. We’ll also deconstruct the list into target, side1, side2, and corner to make the code easier to read.

Now we can do some refactoring to findRegion to track corners (which I have highlighted below).

// In Day12 

private fun findRegion(start: Point2D, seen: MutableSet<Point2D>): Region {
    val target: Char = garden[start]!!
    val queue = mutableListOf(start)
    var area = 0
    var perimeter = 0
    var corners = 0

    while (queue.isNotEmpty()) {
        val place = queue.removeFirst()
        if (garden[place] == target && place !in seen) {
            seen += place
            area++
            val neighbors = place.cardinalNeighbors()
            queue.addAll(neighbors)
            perimeter += neighbors.count { garden[it] != target }
            corners += place.countCorners()
        }
    }
    return Region(target, area, perimeter, corners)
}

We will keep track of the number of corners a region has and increment that number for every new place in the region. Don’t forget to add it to the Region that gets returned.

Calling findRegions and taking the sumOf the products of area and side gives us the answer to part 2.

// In Day12

fun solvePart2(): Int =
    findRegions().sumOf { it.area * it.sides }

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 12, Part 1

⭐ Day 12, Part 2

Further Reading