Skip to Content

Advent of Code 2021 - Day 11, in Kotlin - Dumbo Octopus

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 11: 'Dumbo Octopus'

Posted on

In today’s puzzle, we’ll get some help from some flashing Dumbo Octopuses (which look really cool and thankfully are not threatened). There are a lot of ways we could go about solving today’s puzzle, so today we’ll learn about sequences and how powerful they can be for puzzles where we need to generate an unknown number of something, based on a previous state.

Also, I really like where this storyline might be headed. According to the wikipedia page on Dumbo Octopuses

Although it has been suggested that species of Grimpoteuthis [the scientific name for Dumbo Octopuses] are capable of jet-propulsion, this has since been deemed unlikely.

Sorry today’s solution is a bit late. Formula One qualifying took priority this morning and then I had to run errands before refining and writing it all up.

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

Problem Input

Just like Day 9, we’re dealing with a grid of numbers. But unlike Day 9, I think today we’ll store our values as a Map<Point2d, Int> where the key is a Point2d object representing the location of an octopus, and the value is the energy level of that octopus. We’ll reuse Point2d, which we’ve previously written and used a couple of times already. The parsing logic looks almost like Day 9, and we’ll define a typealias to make Map<Point2d, Int> look a bit more friendly.

typealias OctopusCave = Map<Point2d, Int>

class Day11(input: List<String>) {

    private val startingCave: OctopusCave = parseInput(input)

    private fun parseInput(input: List<String>): OctopusCave =
        input.flatMapIndexed { y, row ->
            row.mapIndexed { x, energy -> Point2d(x, y) to energy.digitToInt() }
        }.toMap()
}

Since the puzzle text mentions that we need diagonal neighbors, we’ll have to add some code to our Point2d class to handle that.

// In Point2d

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

We could have refactored neighbors and given it a boolean argument which would default to false and determine whether or not to provide diagonal spots, but I prefer separate methods for this. If you find the other way more appealing, go for it. In this case we build on the list provided by neighbors and add the diagonals.

⭐ Day 11, Part 1

The puzzle text can be found here.

There are a lot of ways to solve today’s puzzle. Immediately after I woke up this morning and before I had my shower and coffee, I read the puzzle (as usual) and thought up a couple of different ways. We could write a recursive function to cascade all of the flashing. We could model each octopus as an object and keep their state within it, making function calls to one another when they flash. We could have used coroutines to represent each octopus and sent messages via flows. Lots of options.

When I see a problem that asks us to generate states one after the other, I think sequences, so that’s how we’ll model today’s solution. We’re going to define a sequence that hold some internal state (what the cave looks like) and generates the number of flashing octopuses for that step whenever we call it. Because our state transitions are encapsulated within the sequence function, I don’t worry so much about the mutability here.

Let’s look at the code, and then we’ll go over it.

private fun OctopusCave.steps(): Sequence<Int> = sequence {
    val cave = this@steps.toMutableMap()

    while (true) {
        cave.forEach { (point, energy) -> cave[point] = energy + 1 }
        do {
            val flashersThisRound = cave.filterValues { it > 9 }.keys
            flashersThisRound.forEach { cave[it] = 0 }

            flashersThisRound
                .flatMap { it.allNeighbors() }
                .filter { it in cave && cave[it] != 0 }
                .forEach { cave[it] = cave.getValue(it) + 1 }
        } while (flashersThisRound.isNotEmpty())
        
        yield(cave.count { it.value == 0 })
    }
}

Note: If you came here before and noticed different code, Andrew Byala pointed out a nice optimization which I’ve refactored to here. Thanks Andrew!

PS - Andrew is doing Advent of Code 2021 in Clojure and has a nice write-up every day. Unlike me, he stays up late to do these every night!

The first thing to notice is the sequence function we’re using. This is the Kotlin way to generate lazy sequences, and allows us to yield a value from the sequence whenever we want. In our case, we’ll yield (generate) the number of flashers once for every step.

Our first order of business is to make a mutable copy of the caves map. Alternatively we could make startingCave mutable and skip this if we don’t mind changing the state of the initial cave, but I think this makes more sense. According to the algorithm, we start by increasing the power level of each octopus by 1, so we’ll do that via a forEach. A more functional way might have been to return a new map.

This next part is where the real logic is. According to the instructions, a flashing octopus might trigger one of its neighbors to flash, and so on, and so on. So we’ll need to do this logic until we can run through it without any new neighbors flashing. For each time through we’ll find all of the octopuses in the cave that are ready to flash (have an energy level greater than 9) . Once we know which octopuses are going to flash, we can set their energy level to 0. This has the effect of marking them as already having flashed.

Next we need all of the neighbors of each of the octopuses that just flashed. Since allNeighbors can generate Point2ds outside of the cave, we’ll only take the ones that are inside the cave, and of those, only the ones that have not already flashed (anything with an energy level that is not 0). We then go through all of the valid neighbors and add 1 to their energy level.

If we found some flashers, we repeat this process. Once we don’t have any more work to do for this step we can yield the size of the flashersThisStep set, which will be the number of octopuses that flashed this step. We do that by counting the number of octopuses with energy level 0. Kotlin will pause here and not wrap back around to the top of our while loop unless we ask the sequence for another value. This is why sequences are nice, we can tell Kotlin “here is how you generate one of these” and use it as many subsequent times as we want. Want 100? Ask for 100. Want 1,000? Ask for 1,000. The logic doesn’t change and we don’t have to know how long the sequence will be (sequences are unbounded so it’s possible they never end!).

Now we can use the steps sequence to solve part one:

// In Day11

fun solvePart1(): Int =
    startingCave.steps().take(100).sum()

We will generate steps taking the first 100 of them using take. Summing the number of flashers returned from the sequence of 100 steps gives us our answer.

Star earned! Onward!

⭐ Day 11, Part 2

The puzzle text can be found here.

Because we wrote our steps function the way we did, we have everything for part two already written and can write our solution.

// In Day11

fun solvePart2(): Int =
    startingCave.steps().indexOfFirst { it == startingCave.size } + 1

We will keep generating steps until we generate one whose size matches the number of octopuses in the cave. We can do this via indexOfFirst, which will keep generating so long as a predicate does not hold true, and tells us the index of the first element in the sequence that does hold true. Once the predicate is true, it stops taking from the sequence and ends it. Because the index is zero-based, we need to add 1 to the count of steps. Thanks again to Andrew Byala for reminding me of indexOfFrist as well!

Star earned!

Further Reading

  1. Index of All Solutions - All posts and solutions for 2021, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 11
  4. Advent of Code - Come join in and do these challenges yourself!