# Advent of Code 2022 - Day 17, in Kotlin - Pyroclastic Flow

Kotlin solutions to parts 1 and 2 of Advent of Code 2022, Day 17: 'Pyroclastic Flow'

Posted on

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!