Advent of Code 2022 - Day 17, in Kotlin - Pyroclastic Flow • Todd Ginsberg

I really hope you like extension functions, because I ended up writing a lot of them. I like them because generally, they can help make our code cleaner and more expressive. When defining private extensions, we can really take advantage of the fact that we can name them in a way that might only make sense to our code and not a broader audience. I had fun with today’s puzzle, certainly more fun than yesterday (which I still have not published, it’s runtime is a bit… long. I’ll get to it soon!).

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

Puzzle Input

I don’t normally like to create a lot of instance variables for these kinds of puzzles, but we’re going to do it anyway today.

First, let’s talk about how we’re representing things. Just about every aspect of today’s puzzle is some kind of reference to a Point2D (which we defined a few days ago). Our cave is going to be a MutableSet<Point2D> representing places in the cave that are taken up. Our jets (the things on the side that blow our shapes) around will be Point2D instances representing the difference in direction. The shapes themselves will also be Set<Point2D>.

We will define the cave and draw the floor by mapping a range of 0 to 6 as a series of Point2D instances. While we’re at it we’ll define up and down which we need for our logic to drop blocks into place. These are also Point2D,and like the jets, represent differences in direction.

The jetCounter and blockCounter are instance variables to help us keep track of how many of each we’ve seen. We’ll need this to loop through the inputs.

// In Day17

class Day17(input: String) {

    private val jets: List<Point2D> = parseJets(input)
    private val shapes: List<Set<Point2D>> = generateShapes()
    private val cave: MutableSet<Point2D> = (0..6).map { Point2D(it, 0) }.toMutableSet()
    private val down: Point2D = Point2D(0, 1)
    private val up: Point2D = Point2D(0, -1)
    private var jetCounter: Int = 0
    private var blockCounter: Int = 0
}

To parse our jets, we’ll map the input to the appropriate directional offset.

// In Day17

private fun parseJets(input: String): List<Point2D> =
    input.map {
        when (it) {
            '>' -> Point2D(1, 0)
            '<' -> Point2D(-1, 0)
            else -> throw IllegalStateException("No such jet direction $it")
        }
    }

And we’ll hard code the shapes as a list of Set<Point2D>. The bottom left corner of each shape is at 0, 0.

// In Day17

private fun generateShapes(): List<Set<Point2D>> =
    listOf(
        setOf(Point2D(0, 0), Point2D(1, 0), Point2D(2, 0), Point2D(3, 0)),
        setOf(Point2D(1, 0), Point2D(0, -1), Point2D(1, -1), Point2D(2, -1), Point2D(1, -2)),
        setOf(Point2D(0, 0), Point2D(1, 0), Point2D(2, 0), Point2D(2, -1), Point2D(2, -2)),
        setOf(Point2D(0, 0), Point2D(0, -1), Point2D(0, -2), Point2D(0, -3)),
        setOf(Point2D(0, 0), Point2D(1, 0), Point2D(0, -1), Point2D(1, -1))
    )

⭐ Day 17, Part 1

The puzzle text can be found here.

Get ready for a bunch of extension functions.

First, we’ll save this one in our Extensions.kt file because this seems generally useful. Given a List<T>, find the nth element, and loop around if you have to. So if we have a list of 10 elements, and we ask for element 11, it will loop around to the start to get it. This is done via the modulus operator.

// In Extensions.kt

fun <T> List<T>.nth(n: Int): T =
    this[n % size]

Before we can start jetting and dropping a block (a Set<Point2D>), we need to be able to move it to the right place in the cave. There is a gap from the top of the cave to the bottom of our shape of 3, so we want to lift it 4 spaces higher than the celiingHeight, and always 2 over from the left-hand wall. We’ll implement this logic in a function called moveToStart, which takes the celiingHeight (I guess we could just go look in caves if we want). For every Point2D in the set, we map it to a point that is 2 over from the left and 4 up from the ceilingHeight.

// In Day17

private fun Set<Point2D>.moveToStart(ceilingHeight: Int): Set<Point2D> =
    map { it + Point2D(2, ceilingHeight - 4) }.toSet()

You might notice that we’re adding Point2D objects together. How does that work? Kotlin lets us override the plus function as an operator. Since this operation (adding two Point2D objects together) is generally useful for Point2D, we’ll implement it in that class:

// In Point2D

operator fun plus(other: Point2D): Point2D =
    Point2D(this.x + other.x, this.y + other.y)

On the other hand, later on we’ll need to move all of the Point2D instances in a Set<Point2D> by a single Point2D representing an offset. We will absolutely use our plus function to do this, but I found it easier to call that whole operation times and treat it like a multiplication. So we’ll override the times operator on Set<Point2D> when given a Point2D to multiply by. Again, under the covers we’re doing a bunch of plus operations. Since this kind of thing doesn’t seem useful outside of this context (the name, for one, is perhaps awkward in the general case), we’ll define it as a private extension function in Day17, rather than in Point2D.

// In Day17

private operator fun Set<Point2D>.times(point: Point2D): Set<Point2D> = 
    map { it + point }.toSet()

When we simulate our block drops, we need to see if the jet blows our shape into the wall of the cave. We’ll override another operator as an extension function, this time on IntRange when given a Set<Point2D>. This function checks that all of the x values of the points are in the range. If so, the shape is safely in the cave. If not, it has run into a wall.

// In Day17

private operator fun IntRange.contains(set: Set<Point2D>): Boolean = set.all { it.x in this }

Finally, we’ll define some functions to help us figure out the height of the cave. Since we’re building our cave up (instead of down), the y axis of the Point2D objects will be negative values. So to calculate the overall height of the cave, we want to know the minimum Y value in our Set<Point2D>. We’ll call that function minY, and we’ll write a version of that function called height that does the same work except returning the absolutelValue. Sometimes we need to know the height as a positive integer, and sometimes we need to know the true minimum y value.

// In Day17

private fun Set<Point2D>.minY(): Int = minOf { it.y }
private fun Set<Point2D>.height(): Int = minY().absoluteValue

Now we can simulate the dropping of a single shape into our cave:

// In Day17

private fun simulate() {
    var thisShape = shapes.nth(blockCounter++).moveToStart(cave.minY())
    do {
        val jettedShape = thisShape * jets.nth(jetCounter++)
        if (jettedShape in (0..6) && jettedShape.intersect(cave).isEmpty()) {
            thisShape = jettedShape
        }
        thisShape = thisShape * down
    } while (thisShape.intersect(cave).isEmpty())
    cave += (thisShape * up)
}

The simulation I’ve written uses side effects, which I have tried to avoid. However, when we get to Part Two, it will be easier to understand if we do it this way.

First, to simulate the dropping of a single block, we need to know theShape we are dropping. To do this, we get the nth shape (using our extension function), and pass in blockCounter. We’ll use a postfix increment operator (++) here to increment the blockCounter after we get theShape. Once we have the shape, we call moveToStart and pass in the tallest (minY) point in the cave.

We’ll set up a do / while loop here to drop theShape so long as it doesn’t run into anything. First, we have to apply the effect of the jets by getting the nth jet setting (and also incrementing the jetCounter) and multiplying the entire shape by the jet offset and storing it in jettedShape. This is theShape with the jet effect applied. Since the jettedShape can only be used when it is fully within the cave and has not run into another shape, we test its presence in a range (using the contains extension we wrote above) and whether the shape intersects the cave or not. If neither of those apply, we take the jettedShape and call it our current shape by setting it to theShape.

Next, the shape needs to drop so we’ll multiply theShape by the down offset. This time, we’ll assume it works and just assign it to thisShape.

The while loop ends when theShape we just dropped intersects with the cave. That means it has landed, but since we want it one spot up, we need to undo the effect of our down by multiplying it back by up. We could have set a flag to apply down or something like that, but this isn’t that much of a performance hit, and I feel like I understand this better.

Once we know the final resting position of theShape, we add it to the cave. This ends the simulation of dropping one single block.

All that’s left is to solve the puzzle:

// In Day17

fun solvePart1(): Int {
    repeat(2022) {
        simulate()
    }
    return cave.height()
}

Simulate for 2022 rounds and then return the height of the cave.

Star earned! Onward!

⭐ Day 17, Part 2

The puzzle text can be found here.

It’s not unusual for Advent of Code puzzles to do something simple and then make us do it some unreasonable number of times. The general way to solve this problem is to simulate moves until we detect a loop, and then extrapolate the answer from there. So we’ll do that with block dropping as well.

In order to detect the same state again, we want to take a view of the very top of the cave and see if we run into it again. We can’t take the y values because they’ll change as we drop blocks. But what we can do is calculate their values relative to one another. We’ll do that with yet another extension function called normalizedCaveCeiling. This function returns a List<Int> (note: we’ll use List here because if we use IntArray we’ll need to provide a hashcode and equals implementation for our State object a bit later). The values in the List<Int> are the y values, normalized to the hightest point in the cave and reduced.

// In Day17

private fun Set<Point2D>.normalizedCaveCeiling(): List<Int> =
    groupBy { it.x }
        .entries
        .sortedBy { it.key }
        .map { pointList -> pointList.value.minBy { point -> point.y } }
        .let {
            val normalTo = this.minY()
            it.map { point -> normalTo - point.y }
        }

We’ll use groupBy to create map (Map<Int, List<Point2D>>), take all the entires, sort them by the x value, convert the values in map from List<Point2D> to Int, where the Int represents the smallest y value. Then we figure out the minY for the entire cave, and normalize the minimum y values we just calculated against that.

Basically, if we have a cave whose top line looks like this: [-2, -3, -4, -5, -6, -7, -8] we want it normalized to [0, -1, -2, -3, -4, -5, -6]. This way, when a much higher (lower?) set of numbers comes along, we’ll be able to calculate their relative positions to one another.

Let’s simulate a dropping a trillion blocks, shall we?

// In Day17

private fun calculateHeight(targetBlockCount: Long): Long {
    data class State(val ceiling: List<Int>, val blockMod: Int, val jetMod: Int)

    val seen: MutableMap<State, Pair<Int, Int>> = mutableMapOf()
    while (true) {
        simulate()
        val state = State(cave.normalizedCaveCeiling(), blockCounter % shapes.size, jetCounter % jets.size)
        if (state in seen) {
            // Fast forward
            val (blockCountAtLoopStart, heightAtLoopStart) = seen.getValue(state)
            val blocksPerLoop: Long = blockCounter - 1L - blockCountAtLoopStart
            val totalLoops: Long = (targetBlockCount - blockCountAtLoopStart) / blocksPerLoop
            val remainingBlocksFromClosestLoopToGoal: Long =
                (targetBlockCount - blockCountAtLoopStart) - (totalLoops * blocksPerLoop)
            val heightGainedSinceLoop = cave.height() - heightAtLoopStart
            repeat(remainingBlocksFromClosestLoopToGoal.toInt()) {
                simulate()
            }
            return cave.height() + (heightGainedSinceLoop * (totalLoops - 1))
        }
        seen[state] = blockCounter - 1 to cave.height()
    }
}

So, first up - why did I define a data class (State) within a function? Two reasons. First, Andrew Byala and I had a discussion the other day about functions being defined in functions (totally legal in Kotlin!) and I wanted to up the ante a bit. Second, I wanted to show you that defining classes within functions is possible. I can’t recall ever having done this before, and I don’t see it too often. But it is a nice way to limit the scope of something, if you are concerned about it. We could have (and probably should have) made this a private class local to Day17. At any rate, we’ll use this class to find our cycle by storing what the top of the cave looks like (the offsets we just calculated), what block we’re on in the sequence (we call this blockMod because the block counter must be relative to the number of blocks we have (5), not blocks dropped), and the same for the jetMod (how many jets we’ve consumed).

We’ll store all of these in a seen set - a Map<State, Pair<Int,Int>> where the pair stores the number of blocks seen in total, and the height of the cave. Then we start looping through simulations until we find one that we’ve seen twice.

Once we detect a loop, we’re going to have to do the work to calculate the size of the loop, how many loops exist in the large targetBlockCount, and then how far that loop brings us to the end. It’s probable that the loop size doesn’t equally divide into our target count, so we have to account for the little bit of extra at the end.

To do this, we grab the state we stored previously and pick out the blockCountAtLoopStart and the heighAtLoopStart. We use these to calculate the blocksPerLoop, which tells us how many blocks we drop before the whole thing loops back on itself. With this, we can calculate the totalLoops in the targetBlockCount, and then with that, the remainingTurnsFromClosestLoopToGoal which is the extra bit left over. Before we simulate the partial loop, we calculate the heightGainedSinceLoop.

We simulate the remaining few blocks that need to drop to get us from one loop to the goal, and then return the cave’s height plus the heightGainedSinceLoop multiplied by the totalLoops minus one. This is our answer!

When we run the calculateHeight function, we need to remember to subtract 1 from our targetBlockCount because we start all our counters at zero and not one. This tripped me up for a while.

// In Day17

fun solvePart2(): Long =
    calculateHeight(1000000000000L - 1)

Star earned! See you tomorrow!

⭐ Day 17, Part 1

⭐ Day 17, Part 2

Further Reading