Advent of Code 2017 - Day 12, in Kotlin • Todd Ginsberg

On Day 12 we will work with a classic graph traversal problem, and learn something about doing more work than we need to. If you’d rather jump straight to the code, it’s right here .

I’ve challenged myself to post each day’s solution to Github and blog about it. Like last year, I’m going to be solving these problems in Kotlin. I might go back and revise solutions, but I’ll be sure to annotate that fact in these posts.

Problem Input

We are given a set of input for this problem. I’ve loaded this into a List<String> called input, which we will do some further parsing on later.

⭐ Day 12, Part 1

The puzzle text can be found here.

This is a classic example of a graph traversal question, and of course we can solve it any number of ways. One way is to create some objects to represent our graph such as a Node and an Edge. Another way would be to just store the nodes and what they point to in a Map, which is what I’ve chosen to do.

We’ll start by parsing and converting our input, with the help of a regular expressions (surprise!):

private val splitter = """(\d+)""".toRegex()
private val nodes: Map<Int, Set<Int>> = parseInput(input)

private fun parseInput(input: List<String>): Map<Int, Set<Int>> =
    input
        .map { splitter.findAll(it) }
        .map { it.map { it.value.toInt() } }
        .associate { it.first() to it.drop(1).toSet() }

One handy function I’ve not used in Advent of Code before is associate . It combines a map operation in which you return a Pair, and a .toMap() call on the stream into one call. You provide a transform to turn an input into a Pair and it handles the rest. It’s a nice compact way to do that sort of work and conveys intent (which I feel is important when programming for other people).

Now that we have our map of nodes and what they connect to, we’ll need a way to traverse our graph and come up with all the nodes that any given starting node connects to. We’ll take advantage of the fact that our nodes are private, and just read from them in our function. We’ll also share a seen set among function invocations, which is going to be the set of all nodes we’ve traversed. This saves us work, and ultimately becomes our answer.

private fun getReachableFrom(from: Int, seen: MutableSet<Int> = mutableSetOf()): Set<Int> {
    if(from !in seen) {
        seen.add(from)
        nodes.getValue(from).forEach { getReachableFrom(it, seen) }
    }
    return seen
}

Surprise - it’s recursive! I didn’t make this tail recursive because thankfully the inputs weren’t so bad that we needed to. We also could easily have written this iteratively and had a nice easy to read solution. Do that, if you prefer it.

We have what we need in order to solve part one:

fun solvePart1(): Int =
    getReachableFrom(0).size

Let’s get our star and get out of here.

⭐ Day 12, Part 2

The puzzle text can be found here.

We already have everything we need to solve this. First let’s solve this with a completely valid but perhaps not quite as quick approach. We go through all the nodes we know about (they keys in our nodes map), call our getReachableFrom function, sort the results of each answer so [0,1,2] and [2,1,0] are the same, and count distinct sets.

fun solvePart2(): Int =
    nodes.keys
        .asSequence()
        .map { getReachableFrom(it) }
        .distinctBy { it.sorted() }
        .count()

We can do better because that does a ton of extra work. By that I mean we don’t need to call getReachableFrom with ANY value that we’ve seen in an answer before. Suppose we call getReachableFrom(100), and the answer is [100, 101, 102]. We won’t ever have to call getReachableFrom with 101 or 102, because the answer will be the same. Another bonus is that we won’t have to call sort or distinctBy on our results, because there will only ever be one of each set! Let’s explore that solution:

fun solvePart2(): Int {
    val seen = mutableSetOf<Int>()
    return nodes.keys
        .asSequence()
        .filter { it !in seen }
        .map {
            getReachableFrom(it).apply {
                seen.addAll(this)
            }
        }
        .count()
}

Both get the same answer, but the second approach where we remember all the nodes we’ve seen is about 6x faster! The code might not look as elegant, but it’s still quite compact and its function and intent are clear enough. I’m sure if we were willing to sacrifice a bit of readability, we could get solvePart2() down to a single expression.

Whatever route you go, it will earn us a second star!

I hope you’ve learned something and as always, feedback is welcome!

12 days and we’ve earned 24 stars with 26 left to go! Almost half way!

⭐ Day 12, Part 1

⭐ Day 12, Part 2

Further Reading