Skip to Content

Advent of Code 2022 - Day 18, in Kotlin - Boiling Boulders

Kotlin solutions to parts 1 and 2 of Advent of Code 2022, Day 18: 'Boiling Boulders'

Posted on

Today we finally bust out of the second dimension and start working with Frinkahedrons ! This was a nice puzzle to solve on a sunny Sunday morning, drinking some good coffee that my daughter brought back for me from a recent trip.

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

Puzzle Input

Because we’re now being given points in 3-dimensional space, the Point2D class we’ve been using up until won’t work for this puzzle. Let’s solve this problem like we have in prior years by introducing a Point3D class to capture a single point in 3-dimensional space. It works just like Point2D except we’ll add a z dimension.

// In Point3D.kt

data class Point3D(val x: Int = 0, val y: Int = 0, val z: Int = 0) {
    fun cardinalNeighbors(): Set<Point3D> =
        setOf(
            copy(x = x - 1),
            copy(x = x + 1),
            copy(y = y - 1),
            copy(y = y + 1),
            copy(z = z - 1),
            copy(z = z + 1)
        )

    companion object {
        fun of(input: String): Point3D =
            input.split(",").let { (x, y, z) -> Point3D(x.toInt(), y.toInt(), z.toInt()) }
    }
}

I’ve chosen only to implement the cardinalNeighbors() function (which, I guess, isn’t a great name but is somewhat consistent with Point2D) and the of parsing function in the companion. These work the same as their Point2D counterparts, but also account for z.

And we can use Point3D.of() to parse our input and put all the resulting Point3D objects in a Set of points.

// In Day18.kt

class Day18(input: List<String>) {

    private val points: Set<Point3D> = input.map { Point3D.of(it) }.toSet()

}

⭐ Day 18, Part 1

The puzzle text can be found here.

Once we’ve parsed our input, we have everything we need to solve Part One. Imagining each Point3D represents a cube, if it isn’t touching any other points, then six sides are exposed. If all our cubes were this way, the answer would be 6 times the number of cubes. In our puzzle, however, we need to account for the fact that the cubes may be touching, and to remove a side from the total count (from each cube!) when they are.

To do this, we’ll calculate the sumOf sides each point is exposing to air. We calculate the number of sides per point by finding all the cardinalNeighbors and figuring out how many of those are also points. If we find any, subtract that number from 6 (total sides of a cube).

// In Day18

fun solvePart1(): Int =
    points.sumOf { point ->
        6 - point.cardinalNeighbors().count { neighbor -> neighbor in points }
    }

Star earned! Onward!

⭐ Day 18, Part 2

The puzzle text can be found here.

Before we get into our Part Two solution, let’s figure out a clever way to limit how much searching we need to do. What we want is to know is a maximum number of cubes we’ll have to search through around our ball of lava. To do this, we need to know the full range of all three axes (x, y, and z) plus one in each direction. This is because if the full range of the ball of lava is a solid cube, we’ll need one space around that to search for. On the other hand. Basically we need to know what is the least additional space, other than the points themselves, that we can use to represent “air”.

To do this, let’s write an extension function on our Set<Point3D> called rangeOf that takes in a function and uses that to calculate the full range (plus and minus 1) that we care about. We make this function take a function in because we’ll end up needing to call it three times (once for each axis).

// In Day18

private fun Set<Point3D>.rangeOf(function: (Point3D) -> Int): IntRange =
    this.minOf(function) - 1..this.maxOf(function) + 1

I really considered making rangeOf more generic and putting it in our Extensions.kt file, but let’s see if there is another use case for it before we do that. The fact that we have to expand the range by one in each direction I think is what’s limiting me to keeping it in Day18.

To solve Part Two, we’ll use something we’ve used in previous puzzles - a breadth-first search. Meaning, given a spot in space, search through all of its neighbors before searching their neighbors. We do this until we run out of places we haven’t visited. Since our search space will fully encompass the cube of lava, we are guaranteed to visit every outer point.

// In Day18

fun solvePart2(): Int {
    val xRange = points.rangeOf { it.x }
    val yRange = points.rangeOf { it.y }
    val zRange = points.rangeOf { it.z }

    val queue = ArrayDeque<Point3D>().apply { add(Point3D(xRange.first, yRange.first, zRange.first)) }
    val seen = mutableSetOf<Point3D>()
    var sidesFound = 0
    queue.forEach { lookNext ->
        if (lookNext !in seen) {
            lookNext.cardinalNeighbors()
                .filter { it.x in xRange && it.y in yRange && it.z in zRange }
                .forEach { neighbor ->
                    seen += lookNext
                    if (neighbor in points) sidesFound++
                    else queue.add(neighbor)
                }
        }
    }
    return sidesFound
}

First, we use our rangeOf function, passing in a lambda function for each axis to set up the xRange, yRange, and zRange. We’ll use these later to test to make sure we aren’t evaluating spots that are well outside our area of concern (wasted work). Next, we set up a queue, choosing the ArrayDequeue implementation, and seeding it with a Point3D that we know is not in points (meaning - it is air). We can guarantee this by picking the first element of each of our ranges.

We also set up a seen set (so we don’t re-evaluate the same points over and over), and a counter to store the sidesFound during our search.

We know that we have more points to look at if the queue is not empty. In days past we’ve used while(queue.isNotEmpty()) but I was playing around today and was delighted to discover that queue.forEach (when called on ArrayDequeue) works fine. I’m not sure I’ll do it this way in the future (while(queue.isNotEmpty() seems clearer to me), I wanted to throw this out there as a possibility. Note that using forEach on something that doesn’t support concurrent modifications (meaning: reading from an iterator and writing to the queue at the same time) won’t work.

Anyway, we pick where to lookNext off the front of the queue and make sure we haven’t seen it already. If we have, we go back to the queue for more work. If lookNext is an entirely new spot for us we get its cardinalNeihbors and filter out the ones that aren’t in the search space by checking against the ranges we set up. This is so we don’t search out into infinity. Now that we know we’re looking at a neighbor that we haven’t seen and is in the search area, we add it to the seen set so we don’t have to look at it again in the future. If this neighbor is in the set of points we know we’re looking at a place where air touches lava, so we add one to our sidesFound counter. Otherwise, we’ve found more air, so we add the neighbor to the queue for future evaluation.

Executing this function quickly gives us the answer to Part Two.

Star earned! See you tomorrow.

Further Reading

  1. Index of All Solutions - All posts and solutions for 2022, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 18
  4. Advent of Code - Come join in and do these challenges yourself!