Advent of Code 2023 - Day 22, in Kotlin - Sand Slabs • Todd Ginsberg

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) }
                add(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 {
    add(this@topple)
    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)
                addAll(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!

⭐ Day 22, Part 1

⭐ Day 22, Part 2

Further Reading