Advent of Code 2018 - Day 23, in Kotlin • Todd Ginsberg

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

The puzzle text can be found here.

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

The puzzle text can be found here.

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!

⭐ Day 23, Part 1

⭐ Day 23, Part 2

Further Reading