Advent of Code 2021 - Day 22, in Kotlin - Reactor Reboot • Todd Ginsberg

I went around and around on part two of today’s puzzle. I had something working but it was very messy and I wasn’t proud of the code I’d written. I’m not ashamed to say that I peeked in on /r/adventofcode on Reddit and found a description for a really nice and succinct solution. The solution hinges on the idea that we have volumes of positive area and volumes of negative area. While I’d had a similar solution, I maintained two lists of cubes, evaluated way more use cases than I needed to, and the work to evaluate them all was really clunky.

This solution is much cleaner and (I hope) easier to follow. Lesson for the day: never be too proud to ask for help.

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

Problem Input

I’ve managed to avoid writing a regular expression this entire time, and today I finally broke. It’s not that I’m bad at them, I actually know what I’m doing. I just find them really hard to explain, and for most parsing problems we’ve had so far, basic String manipulation has worked out fine. With that in mind, let’s define a Cuboid class and a companion object to parse it:

class Day22(input: List<String>) {

    private val cubes: List<Cuboid> = input.map { Cuboid.of(it) }
    private val part1Cube = Cuboid(true, -50..50, -50..50, -50..50)

    private class Cuboid(val on: Boolean, val x: IntRange, val y: IntRange, val z: IntRange) {
        companion object {
            private val pattern =
                """^(on|off) x=(-?\d+)\.\.(-?\d+),y=(-?\d+)\.\.(-?\d+),z=(-?\d+)\.\.(-?\d+)$""".toRegex()

            fun of(input: String): Cuboid {
                val (s, x1, x2, y1, y2, z1, z2) = pattern.matchEntire(input)?.destructured
                    ?: error("Cannot parse input: $input")
                return Cuboid(
                    s == "on",
                    x1.toInt()..x2.toInt(),
                    y1.toInt()..y2.toInt(),
                    z1.toInt()..z2.toInt(),
                )
            }
        }
    }
}

Our regular expression pattern has seven groups. One for for the on/off flag and six for the x, y, and z ranges (a begin and end for each). In our Cuboid class, we’ll use IntRange to hold the x, y, and z ranges to make things a bit cleaner, rather than having an x1 and x2 Integer, for example.

While we’re here, we’ll define a cubes variable to hold all of the cubes we’ve parsed, and define a Cuboid to make filtering cleaner for part one.

⭐ Day 22, Part 1

The puzzle text can be found here.

After reading the problem, it occurred to me that even though we could define a 3-D array and flag on/off all of the cuboids we find, that won’t work for part two. Some of the ranges we ignore (“for now”) are massive, and when we have to deal with them in 3 dimensions, it adds up. So let’s just skip that part and write something that can handle cuboids of any size right from the start.

Let’s think about our algorithm. Picture a cube with all of its squares marked “on”. We know that we have X * Y * Z “on” squares now. Now picture another cube, also an “on” cube that overlaps our first cube. If we add the volumes together, we’ll have too much. The area where they overlap needs to be subtracted. Picture another case where we have a cube of “on” squares and another cube of “off” squares that overlaps the first. Again, we have an area of the first cube that needs to be subtracted out (because they turned off). The third case I want to examine is if we have an “off” cube and another “off” cube intersects it. We can’t count that whole area twice for the same reason we can’t count them in the two “on” cubes case - we’ll double count. So we need the anti-cube of the first one (turning them back on!).

To accomplish this, we’ll introduce the concept of “negative volume”. An X by Y by Z area either has a positive volume (for “on”) or a negative volume (for the case where we’ve got an overlap of some kind). We will go through the cubes one at a time. If it is “on” we set it aside. We then compare it to all of the other set-aside cubes we know about. If we intersect with any of them, we create a new cube that represents the intersected area but that has the opposite on/off flag set. So if we have an “on” cube, and another cube comes along and intersects it, we need to subtract out (negative volume!) the area that intersects between the two cubes.

Because we’re dealing a lot with intersections, let’s define some extension functions:

// In Extensions.kt

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

infix fun IntRange.intersect(other: IntRange): IntRange =
    maxOf(first, other.first)..minOf(last, other.last)

We now have two infix extension functions on IntRange. The first one determines if one range intersects another. The next one, assumes two ranges intersect and creates a new IntRange that represents the areas that overlap (intersect).

Now that we have the ability to test for and perform intersections between ranges, we need to do the same for Cuboids. So we’ll add these functions to Cuboid:

// In Cuboid

fun intersects(other: Cuboid): Boolean =
    x.intersects(other.x) && y.intersects(other.y) && z.intersects(other.z)

fun intersect(other: Cuboid): Cuboid? =
    if (!intersects(other)) null
    else Cuboid(!on, x intersect other.x, y intersect other.y, z intersect other.z)

These functions behave similarly. The first one tests whether one Cuboid intersects another by testing whether all of the X, Y, and Z ranges intersect. We perform the intersect by using our IntRange.intersect function. One critical piece to point out here is the handling of the on/off flag. We always want the opposite of the cube being intersected. If we have an “on” cube, we want the intersection to represent “off” (to generate negative volume). So rather than making the caller deal with that, we’ll do it ourselves here. In the “real” world, we probably wouldn’t make this assumption if we were providing a general purpose geometry library. We probably wouldn’t have on/off as a concept in that case, frankly.

One more thing to add to Cuboid is how to calculate its volume:

// In Cuboid

fun volume(): Long =
    (x.size().toLong() * y.size().toLong() * z.size().toLong()) * if (on) 1 else -1

This function adds up the sizes of each of the X, Y, and Z ranges and either multiplies by 1 for positive volume or -1 for negative volume. If you know the Kotlin standard library well enough, you might be asking where IntRange.size() came from. We could have used (as I did originally) count(). The thing I don’t like about count is that it adds every Int in the range to a Set<Int> and then figures out how big the set it. It works, but there’s no reason to do that for a range with no gaps.

To speed that up (just a bit), we’ll define another extension function on IntRange:

// In Extensions.kt

fun IntRange.size(): Int =
    last - first + 1

Remember to take care to add the 1 here, or you won’t get the full range, it will be off by one.

Now that we have the ability to define a Cuboid, determine if it intersects, perform an intersect and calculate its volume (positive or negative), we have enough to implement the algorithm discussed above:

// In Day22

private fun solve(cubesToUse: List<Cuboid> = cubes): Long {
    val volumes = mutableListOf<Cuboid>()

    cubesToUse.forEach { cube ->
        volumes.addAll(volumes.mapNotNull { it.intersect(cube) })
        if (cube.on) volumes.add(cube)
    }

    return volumes.sumOf { it.volume() }
}

Our solve function takes in a list of Cuboids to work with because part one and two use different sets (we’ll default to the full set). First things first, we create a MutableList<Cuboid> called volumes so we can add Cuboids to it as we determine they need to be kept. Then we go through each of our input Cuboids. For each one of those, we test it against all of the Cuboids we’ve kept around in volumes. If the new cuboid intersects with anything we know about, we add a new cuboid to the volumes. Remember, these new cuboids will be the opposite of the cuboid we are examining. If we’re examining an “on” cuboid, we want to keep it so we add it to volumes as well. The “off” cuboids can be dropped because we’ve either determined they don’t overlap anything we know about yet, or we’ve accounted for the intersecting parts that need to be turned off by creating negative volumes.

At the end, we get a sumOf all the volumes we’ve kept and that’s our answer.

Because part one only has us looking at small Cuboids, we’ll have to do some filtering:

// In Day22

fun solvePart1(): Long =
    solve(cubes.filter { it.intersects(part1Cube) })

I am much happier with this solution than the unwieldy beast I had doing effectively the same thing but a lot more data structures and handling more use cases than needed.

Star earned! Onward!

⭐ Day 22, Part 2

The puzzle text can be found here.

Nothing to do but solve the unfiltered list:

// In Day 22

fun solvePart2(): Long =
   solve()

Star earned!

⭐ Day 22, Part 1

⭐ Day 22, Part 2

Further Reading