Advent of Code 2021 - Day 19, in Kotlin - Beacon Scanner • Todd Ginsberg

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 Point3ds, 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)) {
            null -> unmappedSectors.add(thisSector)
            else -> {
                baseSector.addAll(transform.beacons)
                foundScanners.add(transform.scanner)
            }
        }
    }
    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!

⭐ Day 19, Part 1

⭐ Day 19, Part 2

Further Reading