# Advent of Code 2021 - Day 19, in Kotlin - Beacon Scanner

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 19: 'Beacon Scanner'

Posted on

I had a really hard time getting today’s puzzle to work out but eventually managed to get it, thanks to a lot of searching and scratch paper. This solution won’t win any prizes for speed as it takes just under 10 seconds for each part on my computer, but I think it’s easy to understand.

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

Problem Input

Since we’ll be dealing with points in 3-D space, our `Point2d` class won’t cut it. So let’s define a `Point3d` class in `Geometry.kt` with an `x`, `y`, and `z` coordinate. We’ll add an `of` function in the `companion object` in order to parse a `String` into a `Point3d`.

``````// In Geometry.kt

data class Point3d(val x: Int, val y: Int, val z: Int) {

companion object {
fun of(rawInput: String): Point3d =
rawInput.split(",").let { part ->
Point3d(part[0].toInt(), part[1].toInt(), part[2].toInt())
}
}
}
``````

We’ll read our input in as a single `String` today, even though it is in multiple lines in the file. This will allow us to more easily parse each section out. We split on two newlines to get a `chunk` of input which represents the output of one single scanner. We don’t really care about the numbers so we `drop` that part entirely. We use our `Point3d.of` function to map the input rows into `Point3d` objects and then turn each chunk into a `Set`.

``````class Day19(input: String) {

private val scanners: List<Set<Point3d>> = parseInput(input)

private fun parseInput(input: String): List<Set<Point3d>> =
input.split("\n\n").map { singleScanner ->
singleScanner
.lines()
.drop(1)
.map { Point3d.of(it) }
.toSet()
}
}
``````

At the end, we have a `List<Set<Point3d>>` which represents the beacons scanned by each scanner.

#### ⭐ Day 19, Part 1

The puzzle text can be found here.

There is so much to cover in this section, so I’ll try to be as detailed as I can without being overwhelming. There are quite a few functions to be defined, so let’s dig right in. I’m trying to avoid using `Pair` so much this year, so let’s define our first class and call it `Transform`. When we eventually find a set of points that represent where a single `scanner` is located, and a set of `beacons` that the scanner has found.

``````// In Day19

private class Transform(val scanner: Point3d, val beacons: Set<Point3d>)
``````

Next, because we’ll be doing some addition and subtraction of `Point3d` objects to get the difference between two `Point3d`s, and then to apply that difference to other `Point3d` objects, we’ll define some operators to make this easier.

``````// In Point3d

operator fun plus(other: Point3d): Point3d =
Point3d(x + other.x, y + other.y, z + other.z)

operator fun minus(other: Point3d): Point3d =
Point3d(x - other.x, y - other.y, z - other.z)
``````

The calculations for `plus` and `minus` are to to either add or subtract each of the axis in one `Point3d` from the corresponding axis in another `Point3d`.

Now for the tricky part. I went around and around on implementations and settled on this. Each `Point3d` can have up to 24 different orientations. It can face six ways, and for each of those, be rotate four ways (for a total of 24). We’re going to add some more functions to `Point3d` to `face` our `Point3d` one of six ways, and another to `rotate` one of four ways. Given a number, we’ll rotate or face ourselves to the orientation desired. I’ll admit this section took me a while, and I had to do a lot of searching to figure out the right way to modify `x`, `y`, and `z` here.

``````// In Point3d

fun face(facing: Int): Point3d =
when (facing) {
0 -> this
1 -> Point3d(x, -y, -z)
2 -> Point3d(x, -z, y)
3 -> Point3d(-y, -z, x)
4 -> Point3d(y, -z, -x)
5 -> Point3d(-x, -z, -y)
else -> error("Invalid facing")
}

fun rotate(rotating: Int): Point3d =
when (rotating) {
0 -> this
1 -> Point3d(-y, x, z)
2 -> Point3d(-x, -y, z)
3 -> Point3d(y, -x, z)
else -> error("Invalid rotation")
}

``````

Now that we can combine `Point3d` objects and reorient them as well, we have what we need to determine if two arbitrary sets of `Point3d` objects intersect. The way we’ll determine if they intersect is if we can reorient all of the points in one set to match 12 or more (per instructions) points in the other set. Let’s write the code, and then we’ll go through it.

``````// In Day19

private fun findTransformIfIntersects(left: Set<Point3d>, right: Set<Point3d>): Transform? =
(0 until 6).firstNotNullOfOrNull { face ->
(0 until 4).firstNotNullOfOrNull { rotation ->
val rightReoriented = right.map { it.face(face).rotate(rotation) }.toSet()
left.firstNotNullOfOrNull { s1 ->
rightReoriented.firstNotNullOfOrNull { s2 ->
val difference = s1 - s2
val moved = rightReoriented.map { it + difference }.toSet()
if (moved.intersect(left).size >= 12) {
Transform(difference, moved)
} else null
}
}
}
}
``````

First off, I love that Kotlin has `firstNotNullOfOrNull` so I could write this as a single expression. It might be a long name for a function, and I don’t know that I’ve used it more than a handfull of times, but being able to nest it like this makes sense to me. Our outer two loops allow us to iterate through all of the possible orientations (facing and rotation). Once we have selected one of the 24 orientations, we reorient all of the points in one of our sets (we’ll use the `right` set for this). We now have `rightReoriented` which represents all of the points from the `right `set, reoriented to one of 24 possible orientations. Being oriented in the same direction isn’t enough, we need to account for the fact that the `left` scanner and `right` scanner work from different frames of reference. To account for that we’ll calculate the `difference` between one of the points in the `left` set with one of the points in the `right` set. We then move each point in our `rightReoriented` set to a new place, given the offset (`difference`) we’ve just calculated. If 12 or more of the newly moved spots exist in the `left` set, we’ve found a match! We can return a `Transform` here with the offset `difference` between the `left` and `right` sets, and the `moved` points, which represent beacons.

If we apply this function enough times, we can solve part one (and most of part two). Again, since I’m avoiding `Pair`, let’s define `Solution` to carry where our `scanners` are located and where our `beacons` are located.

``````// In Day19

private class Solution(val scanners: Set<Point3d>, val beacons: Set<Point3d>)
``````

To solve, we’ll define a `baseSector` and try to find sets of scanners that overlap it. Over time, the `baseSector` will fill up with beacons that we translate from one orientation to another, and the queue of work (`unmappedSectors`) will trend towards zero. Once we’ve discovered the translation rules for each sector, we’ll both a full set of `beacons` and a full set of `scanner` locations!

``````// In Day19

private fun solve(): Solution {
val baseSector = scanners.first().toMutableSet()
val foundScanners = mutableSetOf(Point3d(0,0,0))
val unmappedSectors = ArrayDeque<Set<Point3d>>().apply { addAll(scanners.drop(1)) }
while(unmappedSectors.isNotEmpty()) {
val thisSector = unmappedSectors.removeFirst()
when (val transform = findTransformIfIntersects(baseSector, thisSector)) {
else -> {
}
}
}
return Solution(foundScanners, baseSector)
}
``````

This is where our `findTransformIfIntersects` function does its thing. We pick out any sector (the first one) to be our `baseSector` and put the rest in a queue called `unmappedSectors`. Since we’ve “found” the base sector, we’ll say that it’s scanner is at `0,0,0` and seed that into a `foundScanners` set.

While we still have `unmappedSectors` to look at, we’ll pick the first one off the list and see if there exists a `Transform` between it and the base sector. If so, great - we can add all of the `beacons` we just found to the `baseSector` set. The great part is that since we’ll always be comparing points from the base sector to a candidate sector, the `difference` between them will actually be the location of the scanner in the candidate sector! So we can go ahead and add that to `foundScanners`. On the other hand, if the candidate sector does not have a transform to the base sector, we need to throw it back into the queue, we’ll try to find a match for it later.

We work our way though the queue until we’ve found the transform from every candidate sector, transformed their coordinates to base coordinates, and added all the beacons to the base set.

And now we can solve part one:

``````// In Day19

fun solvePart1(): Int =
solve().beacons.size
``````

Taking the count of the `beacons` solves part one!

Star earned! Onward!

#### ⭐ Day 19, Part 2

The puzzle text can be found here.

The extra work we did in Part one to keep track of the scanner locations pays off for part two. We just need to compare the scanner locations to each other in order to solve part two! In order to do that, let’s first define an extension function called `pairs` to pair up all of the elements in a `Collection`. We might reuse this, so we’ll define it generally in `Extensions.kt`:

``````// In Extensions.kt

fun <T> Collection<T>.pairs(): List<Pair<T,T>> =
this.flatMapIndexed { index, a ->
this.drop(index).map { b -> a to b }
}
``````

Next, we’ll add a distance function to our `Point3d` object:

``````// In Point3d

infix fun distanceTo(other: Point3d): Int =
(this.x - other.x).absoluteValue + (this.y - other.y).absoluteValue + (this.z - other.z).absoluteValue
``````

If you’ve done Advent of Code before, you’ve probably run into Manhattan Distance. I think it’s finally stuck in my head and this was the first year I didn’t have to look up the formula. With that out of the way, we can solve part two by pairing up all the scanner locations and finding the `maxOf` them:

``````// In Day19

fun solvePart2(): Int =
solve().scanners.pairs().maxOf { it.first distanceTo it.second }
``````

Star earned!