Advent of Code 2021 - Day 25, in Kotlin - Sea Cucumber • Todd Ginsberg

We’re finally here, December 25th, the last day of Advent of Code for 2021. I enjoyed this year and learned a few things about problem solving and the Kotlin standard library. I want to first and foremost thank Eric Wastl for creating and running Advent of Code for seven years. The amount of work he puts in to come up with puzzles and generate all of the inputs must be staggering. If you personally or maybe even the company you work for are in a position to support his efforts next year, I’m sure that would be most welcome.

Also, thank you to everybody who has read along as I’ve solved these. Hopefully y’all learned something or was able to get past a tricky spot. I appreciate all of you who managed to contact me to say kind things.

Finally, thanks to the Kotlin community, one of the friendliest and helpful programming communities you’ll ever find.

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

Problem Input

Our data structure today is going to be a Map<Point2d, Char> where the key is the x,y value of a Sea Cucumber, and the value is which herd they belong to (either > or v). We won’t record empty spaces. Since the map we are creating is sparse (meaining not every point we read in will result in an entry), we can use buildMap to make our code a bit clearer. we’ll loop through the List<String> representing our input much like on other days and convert the x and y values to Point2d objects.

class Day25(input: List<String>) {

    private val initialState: Map<Point2d, Char> = parseInput(input)
    private val gridMax: Point2d = Point2d(input.first().lastIndex, input.lastIndex)

    private fun parseInput(input: List<String>): Map<Point2d, Char> =
        buildMap {
            input.forEachIndexed { y, row ->
                row.forEachIndexed { x, c ->
                    if (c != '.') put(Point2d(x, y), c)
                }
            }
        }
}

We will also store the maximum indexes for both the x and y directions in gridMax. We could use a Pair<Int,Int> here but I think having x and y as the property names makes the intent clearer. I really like the fact that Kotlin has lastIndex so we don’t have to do size-1 like we would in other languages.

⭐ Day 25, Part 1

The puzzle text can be found here.

Because the grid we have wraps around so the magical Sea Cucumbers can suddenly appear on the other side of the cave, we’ll need to handle wrapping in both the east and south directions. Let’s add two private extension functions to Point2d for this. If the next east or south point would run off the end of the map, we wrap it around to zero. Otherwise, we add one and return a new Point2d.

// In Day25

private fun Point2d.east(): Point2d =
    if (x == gridMax.x) Point2d(0, y) else Point2d(x + 1, y)

private fun Point2d.south(): Point2d =
    if (y == gridMax.y) Point2d(x, 0) else Point2d(x, y + 1)

To do the bulk of the work, we need a function to turn one Map<Point2d, Char> into the next iteration. This function will implement all the move rules and return a new map, rather than manipulating the map in-place.

// In Day25

private fun Map<Point2d, Char>.next(): Map<Point2d, Char> {
    val nextMap = this.toMutableMap()
    filterValues { it == '>' }
        .keys
        .map { it to it.east() }
        .filter { it.second !in this }
        .forEach { (prev, east) ->
            nextMap.remove(prev)
            nextMap[east] = '>'
        }
    nextMap.filterValues { it == 'v' }
        .keys
        .map { it to it.south() }
        .filter { it.second !in nextMap }
        .forEach { (prev, south) ->
            nextMap.remove(prev)
            nextMap[south] = 'v'
        }
    return nextMap
}

I tried to write this function using buildMap but found the code to be more complicated than I would otherwise have liked. Even though I try to write functions as single expressions (mostly as a way to force myself to keep them simple), sometimes it’s best not to push it. If things are clearer as a sequence of statements, go for it. In this case, we’ll start by creating the nextMap which is identical to the existing (current) map. The nextMap is also mutable, so we can change it as we discover movement.

The first step is to find all of the eastbound herd and move them one step. We do this by filtering the values from the current map, and then creating a pair of the current spot and the next spot (to the east!) that the Sea Cucumbers will move. Because the Sea Cucumbers will only move if they have a valid place to go, we’ll filter out anything that isn’t moving by checking that their destination (the second part of the pair) is not in the map. This gives us all of the eastern-moving Sea Cucumbers, along with their previous and next locations, if they can move. Anything that can’t move doesn’t make it to the forEach loop, where we remove the previous Sea Cucumber from our new map, and add the next (east) location.

We do almost identical work for the southbound herd except we’re checking against the nextMap rather than the source map. This is because a) nextMap originates as a copy of the source map and b) We’ve just moved a bunch of eastbound Sea Cucumbers and they might be in our way.

We now have enough to solve our puzzle:

// In Day25

fun solvePart1(): Int =
    generateSequence(initialState) { it.next() }
        .zipWithNext()
        .indexOfFirst { it.first == it.second } + 1

Because we want to keep generating maps of the sea floor until it stops moving, we’ll set up a generateSequence and pass in the initialState. We hand it a lambda that tells generateSequence how to generate the next element in the sequence (in this case, calling the next() function we just wrote). We’ll consume the sequence via zipWithNext which will allow us to pair up subsequent iterations from the sequence. So iteration 1 and 2 are paired, and then 2 and 3, and then 3 and 4 and so on. We’ll take the indexOfFirst element in which the first and second elements in the zipped pair match. This means the Sea Cucumbers have stopped moving if we generate two identical caves in a row. Because indexOfFirst is zero-indexed, we have to add 1 for our answer.

Star earned!

⭐ Day 25, Part 2

As is tradition, there is no coding for part two on Christmas Day.

Thank you all who have read my blog this year, especially to those who have contacted me in some way. Hopefully, we’ll do this all again next year!

⭐ Day 25, Part 1

⭐ Day 25, Part 2

Further Reading