Advent of Code 2021 - Day 9, in Kotlin - Smoke Basin • Todd Ginsberg

Today we’ll use Kotlin’s support for operators and extension functions to make our code much easier to read. We’ll also get to reuse and extend the Point2d class we made the other day.

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

Problem Input

Our input today is a multi-line String of integers that represents our cave. In order to represent our cave, we’ll use Array<IntArray>. We could also go with List<List<Int>> but I think what we’ve picked looks a bit better. I’m not sure we’ll get much of a performance boost by using an array given the small size of the input, but it might be a factor to consider for real workloads. As usual, we’ll import our input as a List<String> and then convert it.

class Day09(input: List<String>) {

    private val caves: Array<IntArray> = parseInput(input)

}

The code to convert it is a nested map structure.

// In Day09

private fun parseInput(input: List<String>): Array<IntArray> =
    input.map { row ->
        row.map { it.digitToInt() }.toIntArray()
    }.toTypedArray()

One function I want to point out is Char.digitToInt() which is a new addition in Kotlin 1.5. If you’ve followed my Advent of Code posts in years past, we’ve always had to write this ourselves and it was always something I’d wish Kotlin would provide. So I’m really happy this is here.

⭐ Day 9, Part 1

The puzzle text can be found here.

In order to make our code easier to read, let’s define some operators as extension functions. We’ll start with defining get on our Array<IntArray> so we can do things like caves[somePoint] and treat our caves as an indexed resource.

// In Day09

private operator fun Array<IntArray>.get(point: Point2d): Int =
    this[point.y][point.x]

Another helpful operator to define on our Array<IntArray> is to determine if a Point2d is contained in the cave. We can do this by defining a contains function and marking it with the operator keyword. This allows us to write code like somePoint in caves, which I think looks cleaner than the code we’ve written in contains.

// In Day09

private operator fun Array<IntArray>.contains(point: Point2d): Boolean =
    point.y in this.indices && point.x in this[point.y].indices

As part of our cave traversal we’ll need to determine which points in the cave are the neighbors to any given Point2d. So let’s go back to the Point2d class we created the other day and add a neighbors function to return the list of adjacent points.

// In Point2d

fun neighbors(): List<Point2d> =
    listOf(
        Point2d(x , y + 1),
        Point2d(x , y - 1),
        Point2d(x + 1 , y),
        Point2d(x - 1 , y)
    )

We won’t do any sort of filtering or validation of neighboring points within Point2d.neighbors(), instead we’ll do that as an extension function in our Day09 class, because we don’t want to make Point2d become responsible for what a valid point is. The Day09 class knows what a valid point is for its problem domain.

// In Day09

private fun Point2d.validNeighbors(): List<Point2d> =
    neighbors().filter { it in caves }

The validNeighbors function gets the neighbors for a given Point2d and filters it using the contains function we wrote above. This function will only return points that are in the caves.

Now that we have all that out of the way, we can traverse our caves and find all of the individual low points:

// In Day09

private fun Array<IntArray>.findLowPoints(): List<Point2d> =
    flatMapIndexed { y, row ->
        row.mapIndexed { x, height ->
            Point2d(x, y).takeIf { point ->
                point.validNeighbors().map { caves[it] }.all { height < it }
            }
        }.filterNotNull()
    }

Our findLowPoints function returns Point2d objects rather than the heights because we’ll reuse this function in part two and that part needs places not values. This function goes through every Point2d in the cave and does a takeIf if all of the valid neighbors of that point are higher. Because most points don’t actually meet that criteria, our inner mapIndexed lambda can return nulls. We’ll filter those out with filterNotNull, ending up with List<Point2d> of low points.

And now we can solve part one:

// In Day09

fun solvePart1(): Int =
    caves.findLowPoints().sumOf {
        caves[it] + 1
    }

We’ll find all of the low points, find the value of their locations within the caves, add 1 to that value (per instructions) and get the sumOf those values.

Star earned! Onward!

⭐ Day 9, Part 2

The puzzle text can be found here.

Part two has us finding the sizes of all the basins in the cave system. In order to do that, we’ll need a way to expand out from a given Point2d (representing a low point) until it hits either the edge of the cave or a spot that is height 9.

// In Day09

private fun getBasinSize(point: Point2d): Int {
    val visited = mutableSetOf(point)
    val queue = mutableListOf(point)

    while (queue.isNotEmpty()) {
        val newNeighbors = queue.removeFirst()
            .validNeighbors()
            .filter { it !in visited }
            .filter { caves[it] != 9 }

        visited.addAll(newNeighbors)
        queue.addAll(newNeighbors)
    }

    return visited.size

This function is something we’ve seen in past Advent of Code problems, and it’s possible we’ll see it again. However, I don’t want to make it generic so we’ll define it in Day09. First, we create a visited set, representing all of the points in the cave that we’ve already seen. Otherwise, we’ll end up revisiting places we’ve already evaluated. Next, we’ll define a work queue, which will contain places in the cave that we have not visited but know about and need to visit in the future. So long as the queue has work for us, we’ll remove a place from the front of the queue and find its valid neighbors. Since we only care about paces we haven’t visited yet, we’ll filter out anything that is already in the visited set. We’ll also filter out anything that is height 9 because that is not part of the basin (it is a wall of the basin). Now that we have a list of neighboring points, we can mark them all as having been visited and add them to our work queue. Once the queue runs out of places to evaluate, we know we’ve looked at everything in the given basin. We can return the size of the visited set, which is the size of the basin.

And now we can use that to solve part two:

// In Day09

fun solvePart2(): Int =
    caves.findLowPoints()
        .map { getBasin(it).size }
        .sortedDescending()
        .take(3)
        .reduce { a, b -> a * b }

First, we reuse our findLowPoints to get a list if starting points, and then get the size of the basins found at those points. To get the largest three basins, we’ll use sortDescending() to sort the list and take the first 3 values (we could have done sorted().takeLast(3) instead). To get the product of these three numbers, we’ll use reduce.

Star earned!

⭐ Day 9, Part 1

⭐ Day 9, Part 2

Further Reading