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

Day 7 was pretty tricky for me, I had a lot of trouble understanding what we being asked for in part 2. Thanks to the gang in the #advent-of-code channel on the Kotlin Slack for helping me helping me understand the problem!

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

Problem Input

Today’s input is another list of strings, which we will parse below. It’s very regular data, so no regular expressions required!

⭐ Day 7, Part 1

The puzzle text can be found here.

First things first, let’s parse our input. Because we’re going to look at the relationships between the nodes two ways (parent to child and child to parent), we’ll make two maps, one is the reverse of the other.

class Day07(input: List<String>) {

    private val allPairs = parseInput(input)
    private val childrenOf: Map<Char, Set<Char>> = generateDependencies(allPairs)
    private val parentsOf: Map<Char, Set<Char>> = generateDependencies(allPairs.map { it.second to it.first })
    private val allKeys = childrenOf.keys.union(parentsOf.keys)

    private fun parseInput(input: List<String>): List<Pair<Char, Char>> =
        input.map { row ->
            row.split(" ").run { this[1].first() to this[7].first() }
        }

    private fun generateDependencies(input: List<Pair<Char, Char>>): Map<Char, Set<Char>> =
        input
            .groupBy { it.first }
            .mapValues { (_, value) -> value.map { it.second }.toSet() }

}

The function to parse the input takes advantage of the fact that it is regular input and the node names are single characters in predictable places (1 and 7). So we end up with a List<Pair<Char, Char>>. We then take the pairs we created and turn them into a map called childrenOf, which answers the question “for the key, which nodes are its children”. Then we reverse the pairs and use that same generateDependencies function to create a map called parentsOf which answers the question “for the key, which nodes are its parents”. This should let us avoid some scanning by only having this map one way, or just using allPairs and fishing out what we want. Finally, we create a list of all of the keys, because we don’t want to assume anything about the input.

This brings us to the part where we have to go through this and figure out how to traverse the graph. The most important point to remember is that no node can be considered ready to be traversed if any of the nodes that it depends on have not been traversed already. More succinctly, you can’t visit a child node until all of the parents have been visited.

fun solvePart1(): String {
    val ready = allKeys.filterNot { it in parentsOf }.toMutableList()
    val done = mutableListOf<Char>()
    while (ready.isNotEmpty()) {
        val next = ready.sorted().first().also { ready.remove(it) }
        done.add(next)
        childrenOf[next]?.let { maybeReadySet ->
            ready.addAll(maybeReadySet.filter { maybeReady ->
                parentsOf.getValue(maybeReady).all { it in done }
            })
        }
    }
    return done.joinToString(separator = "")
}

Let’s walk through this. The ready list is a list of nodes that are considered ready to visit. We fill this with any of the “start” nodes in the graph, which we find by finding nodes that are not depended on by any other node. We also set up a list called done, which contains nodes we’ve already looked at. This will eventually become our output.

The main loop of the function will keep going as long as at least one node is in the ready list. When that’s true, we take the first node available alphabetically, remove it from the list, and add it to the done list. At this point, because some nodes have changed state, we can see if there was anything waiting on them. To do that, we take the node we just finished and find all of its children, thanks to our map. If we find any, we make sure that all of their parents also been finished. If so, we schedule the node for ready, otherwise we loop again, presuming there is something that still needs traversing.

After that’s done, we can stringify our done list and get our answer.

That earns us a star!

⭐ Day 7, Part 2

The puzzle text can be found here.

I’m going to confess that I found this super confusing. Thanks to the people in the #advent-of-code channel on the Kotlin Slack , I was able to piece together what was being asked for here. It all comes down to the fact that I just wasn’t reading it correctly. The salient part is that the example code above has different constraints (workers and costing function) than the real example.

fun solvePart2(workers: Int, costFunction: (Char) -> Int): Int {
    val ready = allKeys.filterNot { it in parentsOf }.map { it to costFunction(it) }.toMutableList()
    val done = mutableListOf<Char>()
    var time = 0

    while (ready.isNotEmpty()) {
        // Work on things that are ready.
        // Do one unit of work per worker, per item at the head of the queue.
        ready.take(workers).forEachIndexed { idx, work ->
            ready[idx] = Pair(work.first, work.second - 1)
        }

        // These are done
        ready.filter { it.second == 0 }.forEach { workItem ->
            done.add(workItem.first)

            // Now that we are done, add some to ready that have become unblocked
            childrenOf[workItem.first]?.let { maybeReadySet ->
                ready.addAll(
                    maybeReadySet.filter { maybeReady ->
                        parentsOf.getValue(maybeReady).all { it in done }
                    }
                        .map { it to costFunction(it) }
                        .sortedBy { it.first }
                )
            }
        }

        // Remove anything that we don't need to look at anymore.
        ready.removeIf { it.second == 0 }

        time++
    }
    return time
}

This really took me a while, and I did try to make this clearer than I originally had it, but I’m not sure it’s the best way to do this so that others can reason about it. However, I’ll attempt an explanation! We set up our function as above by creating a ready list and a done list. The only difference is that instead of dealing with a Char, we’re going to be dealing with a Pair<Char, Int>, where the Char is the node name and the Int is the cost it takes to traverse that node. The cost is calculated via a function passed in as an argument to our solution function. We do this because it differs based on the example vs. real data, and I have tests for both. For the sake of completeness, here are the cost functions, which are defined in a companion object:

companion object {
    fun exampleCostFunction(c: Char): Int = actualCostFunction(c) - 60
    fun actualCostFunction(c: Char): Int = 60 + (c - 'A' + 1)
}

Back to our original function! The first thing we do is look through ready to determine if our workers have anything to do. Since workers can only work on one thing at a time, we take one element from ready for each worker, if that much work is available. If not, any extra workers will sit idle. For every piece of work we find, we subtract one from its cost to indicate that one unit of time has passed. This leaves us in the state where one second of work has been done by each worker. These are updated in-place in our ready list.

The next major phase of this function is to find work that has been completed. Work has been completed when its time/cost is zero. So every time we find one of those, we move it to the done list. We’ll remove it from the ready list at the end of the block. Next, we do the same thing as part 1 - find new nodes that can be traversed. The only real difference from this is we have to account for a few things:

Because we’re using a Pair, we calculate the cost at this time.
Because this new work needs to stay in order (and not jump ahead of things already being worked on), we sort any eligible nodes we find.

At the end of the loop we increment the time and remove any finished nodes from the ready list. when there is no more work to do, we can return the time, which is our answer.

Second star more than earned!

⭐ Day 7, Part 1

⭐ Day 7, Part 2

Further Reading