Skip to Content

Advent of Code 2017 - Day 12, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 12: 'Digital Plumber'

Posted on

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

Walking along the memory banks of the stream, you find a small village that is experiencing a little confusion: some programs can’t communicate with each other.

Programs in this village communicate using a fixed system of pipes. Messages are passed between programs using these pipes, but most programs aren’t connected to each other directly. Instead, programs pass messages between each other until the message reaches the intended recipient.

For some reason, though, some of these messages aren’t ever reaching their intended recipient, and the programs suspect that some pipes are missing. They would like you to investigate.

You walk through the village and record the ID of each program and the IDs with which it can communicate directly (your puzzle input). Each program has one or more programs with which it can communicate, and these pipes are bidirectional; if 8 says it can communicate with 11, then 11 will say it can communicate with 8.

You need to figure out how many programs are in the group that contains program ID 0.

For example, suppose you go door-to-door like a travelling salesman and record the following list:

0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5

In this example, the following programs are in the group that contains program ID 0:

  • Program 0 by definition.
  • Program 2, directly connected to program 0.
  • Program 3 via program 2.
  • Program 4 via program 2.
  • Program 5 via programs 6, then 4, then 2.
  • Program 6 via programs 4, then 2.

Therefore, a total of 6 programs are in this group; all but program 1, which has a pipe that connects it to itself.

How many programs are in the group that contains program ID 0?

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

There are more programs than just the ones in the group containing program ID 0. The rest of them have no way of reaching that group, and still might have no way of reaching each other.

A group is a collection of programs that can all communicate via pipes either directly or indirectly. The programs you identified just a moment ago are all part of the same group. Now, they would like you to determine the total number of groups.

In the example above, there were 2 groups: one consisting of programs 0,2,3,4,5,6, and the other consisting solely of program 1.

How many groups are there in total?

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!

Further Reading

  1. Index of All Solutions - All solutions for 2017, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 12.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Dance of the Reed Pipes, by Tchaikovsky.