# 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++
}
}
}
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.