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'
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
- Index of All Solutions - All posts and solutions for 2022, in Kotlin.
- My Github repo - Solutions and tests for each day.
- Solution - Full code for day 18
- Advent of Code - Come join in and do these challenges yourself!