# Advent of Code 2023 - Day 22, in Kotlin - Sand Slabs

Kotlin solutions to parts 1 and 2 of Advent of Code 2023, Day 22: 'Sand Slabs'

Posted on

I enjoyed this one. I went through a few different implementations and am happy where I ended up on this one. It’s been refreshing to solve this one as I’ve been struggling with Days 19 and 21.

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

Puzzle Input

Today we will take our `input` as a `List<String>` and parse each row into a `List<Brick>` (with `Brick` being a data class we will see shortly). After creating each `Brick` we put them in z-increasing order and `settle` them (compact them down so everything is resting on something else).

``````class Day22(input: List<String>) {

private val bricks: List<Brick> = input
.mapIndexed { index, row -> Brick.of(index, row) }
.sorted()
.settle()

}
``````

The `Brick` class has a lot going on, so I’ll explain it below.

``````// In Day22

private data class Brick(val id: Int, val x: IntRange, val y: IntRange, val z: IntRange) : Comparable<Brick> {
val supporting = mutableSetOf<Brick>()
val supportedBy = mutableSetOf<Brick>()

override fun compareTo(other: Brick): Int =
z.first - other.z.first

fun supports(other: Brick) {
supporting += other
other.supportedBy += this
}

fun canSupport(other: Brick): Boolean =
x intersects other.x && y intersects other.y && z.last + 1 == other.z.first

fun onGround(): Boolean =
z.first == GROUND

fun fall(restingPlace: Int): Brick =
copy(
z = restingPlace..(restingPlace + (z.last - z.first))
)

companion object {

const val GROUND = 1

fun of(index: Int, input: String): Brick =
input.split("~")
.map { side -> side.split(",").map { it.toInt() } }
.let { lists ->
val left = lists.first()
val right = lists.last()
Brick(
index,
left[0]..right[0],
left[1]..right[1],
left[2]..right[2]
)
}
}
}
``````

The `Brick` class has three `IntRanges`, one for each of `x`, `y`, and `z`. Originally I had created a `Point3D` class for this and maintained two of them but it just got confusing so I abandoned that effort. For the purpose of debugging, I have given each `Brick` an `id`.

The first thing to notice is the `companion object`. We need to know where the `GROUND` is (it is NOT at 0, it is at 1, and this kept screwing me up so I made a constant for it). The `of` function parses out a single row of `input` and returns a new `Brick`.

`Brick` implements `Comparable<Brick>` so we can order them by z-order, which is done in the `compareTo` function. We also declare two sets, those bricks that are `supportedBy` this brick and those bricks that are `supporting` this brick. We have a `supports` function to maintain the two-way relationship here, as well as a `canSupport` function to determine if two bricks are oriented in such a way that one can support the other.

The only other function of note in here is `fall`, which creates a new `Brick` with the same `id`, `x`, and `y` values but a new `z` value that starts at the `restingPlace`.

Because `IntRange.intersection()` in Kotlin involves enumerating the range and creating a `Set<Int>`, I’ve created an `intersects` function in `Extensions.kt` which shortcuts this and returns a `Boolean` which tells us if the ranges intersect or not. For fun, this is an `infix` function.

``````// In Extensions.kt

infix fun IntRange.intersects(other: IntRange): Boolean =
first <= other.last && last >= other.first
``````

Since the bricks come to us as snapshots of them falling, we need to make sure when we model them that we put them in their proper final orientation. To do this, we’ll write an extension function on `List<Brick>` called `settle`, whose job is to make the bricks fall into place.

``````// In Day22

private fun List<Brick>.settle(): List<Brick> = buildList {
this@settle.forEach { brick ->
var current = brick
do {
var settled = false
val supporters = filter { below -> below.canSupport(current) }
if (supporters.isEmpty() && !current.onGround()) {
val restingPlace = filter { it.z.last < current.z.first - 1 }
.maxOfOrNull { it.z.last }?.let { it + 1 } ?: GROUND
current = current.fall(restingPlace)
} else {
settled = true
supporters.forEach { below -> below.supports(current) }
}
} while (!settled)
}
}
``````

When I need to build a list iteratively I like to use the built-in `buildList` function instead of declaring a `MutableList` and altering it. In the end, it is the same effect but this also lets us implement `setttle` as a single expression. The only weird thing about using `buildList` is that within it, `this` is the list we’re creating. So in order to refer to the `this` that refers to the `List<Brick>` we called `settle` on, we have to refer to it via `this@settle`. At any rate, we go through all of the bricks one by one and either find them settled into place, or put them there.

Because we need to change the `z` range of a brick if it is not in place, we’ll need to define `current` as a `var` so we can overwrite it. While we have not fully settled the `current` brick, we check to see how many of the current list that we are creating (which is initially empty) would be able to support it. This is done because we can assume that those are already settled if they’re in the list we’re making. If the current brick doesn’t have any supporters and it is not on the ground, we need to calculate the `restingPlace` for the `current` brick. We do this by looking again at all the bricks we’ve put in our new list (read: have settled) and find any whose `z` is below ours, and take the max of all those. If none of them match, we assume the brick falls to the `GROUND`. Once we know where the brick falls to, we call the `fall` function, which returns a new `Brick` to replace the `current`.

If the brick has settled (or the above logic runs and then we loop back here from the `while` loop), we add the `supporters` to the brick that we’ve fallen onto. This takes care of setting both ends of the supporting/supported relationship.

At the end of this function, all bricks are in their right place z-wise.

#### ⭐ Day 22, Part 1

The puzzle text can be found here.

Thanks to all the parsing and settling, we’re mostly ready to solve part 1. The only thing we really need to do is identify which bricks are “structurally significant”. Meaning - if we remove them things break, not merely a “load bearing” brick. We define a brick as “structurally significant” if the bricks it supports are only supported by one brick.

``````// In Day22

private fun List<Brick>.structurallySignificant(): List<Brick> =
filter { brick -> brick.supporting.any { it.supportedBy.size == 1 } }
``````

We define `structurallySignificant` as a function on `List<Brick>` and use the `any` function to `filter` in the bricks we want.

Now we can solve part 1.

``````// In Day22

fun solvePart1(): Int =
bricks.size - bricks.structurallySignificant().size
``````

Subtract the number of structurally significant bricks from the total number of bricks and we’ve got our answer.

Star earned! Onward!

#### ⭐ Day 22, Part 2

The puzzle text can be found here.

Let’s topple some bricks! I really tried hard to write `topple` as a recursive function but I just could not get the actual answer I was looking for. The example values all worked out, but I’m missing something about how blocks are stacked and found it easier to do it iteratively.

We’ll write `topple` as an extension function on `Brick` rather than on `Brick` itself because we need to know all the `bricks` in the stack to do the toppling and I didn’t want to pass them in.

``````// In Day22

private fun Brick.topple(): Set<Brick> = buildSet {
val untoppled = (bricks - this).toMutableSet()
do {
val willFall = untoppled
.filter { it.supportedBy.isNotEmpty() }
.filter { it.supportedBy.all { brick -> brick in this } }
.also {
untoppled.removeAll(it)
}
} while (willFall.isNotEmpty())
}
``````

When we implement `topple` we will use `buildSet` which behaves similarly to how `buildList` works except with a `Set`. Again, I like this instead of defining my own `MutableSet` and adding to it because it lets me implement `topple` as a single expression.

In `topple` we add the current brick we want to topple to the “this has been toppled” set we’re building. Then we go through every other brick in the set (`untoppled`) and see if we have toppled them by removing the critical support. We keep attempting to make bricks fall until none do, and then we’re confident that the stack is in its end state. We do this by going through the as-yet `untoppled` bricks and finding bricks that have support and whose supports are all in the toppled set we’re currently building. If so, congratulations, we’ve toppled another brick. So add it to the current set and remove it from the `untoppled` set. When the `topple` function returns it returns a set containing all of the bricks that toppled by removing the brick the `topple` function was called on (including the one it was called on).

Now we can solve part 2.

``````// In Day22

fun solvePart2(): Int =
bricks.structurallySignificant().sumOf { it.topple().size - 1 }
``````

We find all of the structurally significant blocks and topple them. Since we return the structurally significant blocks from the `topple` function, we subtract 1 so we don’t include them in the eventual answer, which `sumOf` gives us.

Star earned! See you tomorrow!