Skip to Content

Advent of Code 2018 - Day 7, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 7: 'The Sum of Its Parts'

Posted on

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

“We do need to find our way back to the North Pole, but we have higher priorities at the moment. You see, believe it or not, this box contains something that will solve all of Santa’s transportation problems - at least, that’s what it looks like from the pictures in the instructions.” It doesn’t seem like they can read whatever language it’s in, but you can: “Sleigh kit. Some assembly required.”

”‘Sleigh’? What a wonderful name! You must help us assemble this ‘sleigh’ at once!” They start excitedly pulling more parts out of the box.

The instructions specify a series of steps and requirements about which steps must be finished before others can begin (your puzzle input). Each step is designated by a single letter. For example, suppose you have the following instructions:

Step C must be finished before step A can begin.
Step C must be finished before step F can begin.
Step A must be finished before step B can begin.
Step A must be finished before step D can begin.
Step B must be finished before step E can begin.
Step D must be finished before step E can begin.
Step F must be finished before step E can begin.

Visually, these requirements look like this:

  -->A--->B--
 /    \      \
C      -->D----->E
 \           /
  ---->F-----

Your first goal is to determine the order in which the steps should be completed. If more than one step is ready, choose the step which is first alphabetically. In this example, the steps would be completed as follows:

  • Only C is available, and so it is done first.
  • Next, both A and F are available. A is first alphabetically, so it is done next.
  • Then, even though F was available earlier, steps B and D are now also available, and B is the first alphabetically of the three.
  • After that, only D and F are available. E is not available because only some of its prerequisites are complete. Therefore, D is completed next.
  • F is the only choice, so it is done next.
  • Finally, E is completed.

So, in this example, the correct order is CABDFE.

In what order should the steps in your instructions be completed?

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.

```kotlin
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

As you’re about to begin construction, four of the Elves offer to help. “The sun will set soon; it’ll go faster if we work together.” Now, you need to account for multiple people working on steps simultaneously. If multiple steps are available, workers should still begin them in alphabetical order.

Each step takes 60 seconds plus an amount corresponding to its letter: A=1, B=2, C=3, and so on. So, step A takes 60+1=61 seconds, while step Z takes 60+26=86 seconds. No time is required between steps.

To simplify things for the example, however, suppose you only have help from one Elf (a total of two workers) and that each step takes 60 fewer seconds (so that step A takes 1 second and step Z takes 26 seconds). Then, using the same instructions as above, this is how each second would be spent:

Second   Worker 1   Worker 2   Done
   0        C          .        
   1        C          .        
   2        C          .        
   3        A          F       C
   4        B          F       CA
   5        B          F       CA
   6        D          F       CAB
   7        D          F       CAB
   8        D          F       CAB
   9        D          .       CABF
  10        E          .       CABFD
  11        E          .       CABFD
  12        E          .       CABFD
  13        E          .       CABFD
  14        E          .       CABFD
  15        .          .       CABFDE

Each row represents one second of time. The Second column identifies how many seconds have passed as of the beginning of that second. Each worker column shows the step that worker is currently doing (or . if they are idle). The Done column shows completed steps.

Note that the order of the steps has changed; this is because steps now take time to finish and multiple workers can begin multiple steps simultaneously.

In this example, it would take 15 seconds for two workers to complete these steps.

With 5 workers and the 60+ second step durations described above, how long will it take to complete all of the steps?

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!

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 7
  4. Advent of Code - Come join in and do these challenges yourself!