Skip to Content

Advent of Code 2018 - Day 23, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 23: 'Experimental Emergency Teleportation'

Posted on

Today we’ll learn about finding cliques in a graph. This works for my input and the other sets of input I have tried it on, but there is some conjecture that it won’t work for all possible inputs you could throw at it. Hopefully it works on yours.

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

Problem Input

One file, with one nanobot per line, which we will parse in part 1.

Day 23, Part 1

Using your torch to search the darkness of the rocky cavern, you finally locate the man’s friend: a small reindeer.

You’re not sure how it got so far in this cave. It looks sick - too sick to walk - and too heavy for you to carry all the way back. Sleighs won’t be invented for another 1500 years, of course.

The only option is experimental emergency teleportation.

You hit the “experimental emergency teleportation” button on the device and push I accept the risk on no fewer than 18 different warning messages. Immediately, the device deploys hundreds of tiny nanobots which fly around the cavern, apparently assembling themselves into a very specific formation. The device lists the X,Y,Z position (pos) for each nanobot as well as its signal radius ® on its tiny screen (your puzzle input).

Each nanobot can transmit signals to any integer coordinate which is a distance away from it less than or equal to its signal radius (as measured by Manhattan distance). Coordinates a distance away of less than or equal to a nanobot’s signal radius are said to be in range of that nanobot.

Before you start the teleportation process, you should determine which nanobot is the strongest (that is, which has the largest signal radius) and then, for that nanobot, the total number of nanobots that are in range of it, including itself.

For example, given the following nanobots:

pos=<0,0,0>, r=4
pos=<1,0,0>, r=1
pos=<4,0,0>, r=3
pos=<0,2,0>, r=1
pos=<0,5,0>, r=3
pos=<0,0,3>, r=1
pos=<1,1,1>, r=1
pos=<1,1,2>, r=1
pos=<1,3,1>, r=1

The strongest nanobot is the first one (position 0,0,0) because its signal radius, 4 is the largest. Using that nanobot’s location and signal radius, the following nanobots are in or out of range:

The nanobot at 0,0,0 is distance 0 away, and so it is in range.
The nanobot at 1,0,0 is distance 1 away, and so it is in range.
The nanobot at 4,0,0 is distance 4 away, and so it is in range.
The nanobot at 0,2,0 is distance 2 away, and so it is in range.
The nanobot at 0,5,0 is distance 5 away, and so it is not in range.
The nanobot at 0,0,3 is distance 3 away, and so it is in range.
The nanobot at 1,1,1 is distance 3 away, and so it is in range.
The nanobot at 1,1,2 is distance 4 away, and so it is in range.
The nanobot at 1,3,1 is distance 5 away, and so it is not in range.

In this example, in total, 7 nanobots are in range of the nanobot with the largest signal radius.

Find the nanobot with the largest signal radius. How many nanobots are in range of its signals?

See!! I told you yesterday that we were in no way shape or form equipped to rescue this “friend” we just risked our lives in a set of caves for. I told you.

Anyway… it looks like our Point class won’t help us here, so let’s define a new one for 3D space and make it local to our Day23 class. We’ll pull it out later if we end up needing it in another puzzle.

// In Day23

private data class Point3d(val x: Int, val y: Int, val z: Int) {
    fun distanceTo(other: Point3d): Int =
        abs(x - other.x) + abs(y - other.y) + abs(z - other.z)
    
    companion object {
        val origin = Point3d(0, 0, 0)
    }
}

It should look pretty similar to Point in that it has a distanceTo function (except for 3 axis instead of 2) and defines the origin in the companion. Our original Point has a few more functions we don’t really need right now, so I didn’t convert them. YAGNI. Now we can use that to construct a Nanobot class, which we will also define within Day23. I don’t suspect we’ll need this again in the future, but we can always refactor if we do.

// In Day23

private data class Nanobot(val location: Point3d, val radius: Int) {

    fun inRange(other: Nanobot): Boolean =
        location.distanceTo(other.location) <= radius

    companion object {

        private val digitsRegex = """^pos=<(-?\d+),(-?\d+),(-?\d+)>, r=(\d+)$""".toRegex()

        fun of(input: String): Nanobot =
            digitsRegex.find(input)?.let {
                val (x, y, z, r) = it.destructured
                Nanobot(Point3d(x.toInt(), y.toInt(), z.toInt()), r.toInt())
            } ?: throw IllegalArgumentException("Cannot parse $input")

    }
}

You can see here how we parse the data - declare a regular expression, match against it, destructure our matched groups, convert each of them to Ints, and create our Nanobot. If we can’t parse it, we will throw an exception. We also have a function to see if one Nanobot is in range of another given Nanobot. Be careful here, just because bot A considers bot B in range, doesn’t mean the opposite is true, B might have a smaller radius!

Now that we have our Nanobot, we can move directly to solving part 1 by finding the fattest one (the one with the largest radius - in my mind radius is proportional to their size, but that might not be true in reality):

fun solvePart1(): Int {
    val fattestBot = swarm.maxBy { it.radius }!!
    return swarm.count { fattestBot.inRange(it) }
}

Star earned! Onward!

Day 23, Part 2

Now, you just need to figure out where to position yourself so that you’re actually teleported when the nanobots activate.

To increase the probability of success, you need to find the coordinate which puts you in range of the largest number of nanobots. If there are multiple, choose one closest to your position (0,0,0, measured by manhattan distance).

For example, given the following nanobot formation:

pos=<10,12,12>, r=2
pos=<12,14,12>, r=2
pos=<16,12,12>, r=4
pos=<14,14,14>, r=6
pos=<50,50,50>, r=200
pos=<10,10,10>, r=5

Many coordinates are in range of some of the nanobots in this formation. However, only the coordinate 12,12,12 is in range of the most nanobots: it is in range of the first five, but is not in range of the nanobot at 10,10,10. (All other coordinates are in range of fewer than five nanobots.) This coordinate’s distance from 0,0,0 is 36.

Find the coordinates that are in range of the largest number of nanobots. What is the shortest manhattan distance between any of those points and 0,0,0?

I really had a hard time with this one and went to Reddit for helpful hints. One of the hints that I got was to treat the swarm of Nanobots as a graph and find the largest clique. A clique is the set of vertexes in a graph that all connect to one another. By doing so, we can find where in the swarm we would have a chance at being in range of the most nanobots.

The algorithm we’re going to implement is called the Bron-Kerbosch algorithm, and is especially nice because I was able to understand it quickly and implement it with not very much code. We’ll define a new class for this, and make it generic so we can potentially reuse it.

class BronKerbosch<T>(private val neighbors: Map<T, Set<T>>) {

    private var bestR: Set<T> = emptySet()

    fun largestClique(): Set<T> {
        execute(neighbors.keys)
        return bestR
    }

    private fun execute(
        p: Set<T>,
        r: Set<T> = emptySet(),
        x: Set<T> = emptySet()
    ) {
        if (p.isEmpty() && x.isEmpty()) {
            // We have found a potential best R value, compare it to the best so far.
            if (r.size > bestR.size) bestR = r
        } else {
            val mostNeighborsOfPandX: T = (p + x).maxBy { neighbors.getValue(it).size }!!
            val pWithoutNeighbors = p.minus(neighbors[mostNeighborsOfPandX]!!)
            pWithoutNeighbors.forEach { v ->
                val neighborsOfV = neighbors[v]!!
                execute(
                    p.intersect(neighborsOfV),
                    r + v,
                    x.intersect(neighborsOfV)
                )
            }
        }
    }
}

The execute method is the real guts of the implementation and it is recursive. I tried to name the variables as precisely as possible (except for r, p, and x, which are part of the description of this algorithm everywhere I’ve seen it described). Modifications that can be made to this class are to make it stateless, or to have it return all of the sets which could be considered the largest in the event of a tie. That might help make this solution work on a wider set of AoC inputs if there are issues.

In order for this algorithm to work we need to know which bots each bot shares a point in space with. Imagine bot A and bot B hovering in their place. We need to know which pairs have a radius that overlaps a specific point in space in order to effectively calculate the neighborhood data. So we’ll add that function to Nanobot:

// In Nanobot, in Day23

fun withinRangeOfSharedPoint(other: Nanobot): Boolean =
    location.distanceTo(other.location) <= radius + other.radius

No we can generate our neighbor map and feed it to our BronKerbosch class, asking it for the largest clique (again, there might be ties, I’m not handling that, there is room for improvement):

val neighbors: Map<Nanobot, Set<Nanobot>> = swarm.map { bot ->
    Pair(bot, swarm.filterNot { it == bot }.filter { bot.withinRangeOfSharedPoint(it) }.toSet())
}.toMap()

val clique: Set<Nanobot> = BronKerbosch(neighbors).largestClique()

Once we have the clique, we map each Nanobot to an Int describing its distance from the origin minus its radius. Finding the maximum value of this calculation will give us our answer. What is interesting to me is this gives us the Manhattan distance to the point we need but not the point itself!

// Part 2 solution:

return clique.map { it.location.distanceTo(Point3d.origin) - it.radius }.max()!!

Star earned!

Further Reading

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