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

Day 7 is all about parsing strings and walking trees. 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 parsed this into an List<String> that we will parse into a useful structure.

⭐ Day 7, Part 1

The puzzle text can be found here.

I can’t really think of a good reason not to model our data as a tree. Even the example shows it as a tree. The only trick is going to be parsing this into the structure we see above. First, let’s define what we think a node in our tree looks like:

data class Node(val name: String,
                private val weight: Int,
                val children: MutableList<Node> = mutableListOf(),
                var parent: Node? = null)

Each node has a name, weight, a list of children, and possibly a parent. I’m defining that parent as a var because due to the nature of the input, I might not have the name of a parent when I create one of its children. And rather than doing a bunch of .copy() calls on our data class, I’d rather just make it a var. If this Node were going to be used in an external library, I’d probably make it a val and figure out a better way to parse it.

Why do we track the weight and child nodes at all? Good question! I know a little something about part two that you don’t know yet. Both of them are required to solve that part, so let’s just store them now.

On to parsing the input. The way I’m going to do this is to read the first part of the mapping where we get the name and the weight, and store the names of any children mapped to the parent. Once we’ve created a Node for each parent, we can go through and link all of the child Node objects back up. If we wanted to just represent children as Strings, and go look them up by name when traversing our tree, we could do that. But I feel having a fully-formed data structure is cleaner ultimately.


private val headOfTree: Node = parseInput(input)

private fun parseInput(input: List<String>): Node {
    val nodesByName = mutableMapOf<String, Node>()
    val parentChildPairs = mutableSetOf<Pair<Node, String>>()
    val rowRegex = """\w+""".toRegex()

    input.forEach {
        val groups = rowRegex.findAll(it).toList().map { it.value }
        val node = Node(groups[0], groups[1].toInt())
        nodesByName.put(node.name, node)

        groups.drop(2).forEach {
            parentChildPairs.add(Pair(node, it))
        }
    }

    parentChildPairs.forEach { (parent, childName) ->
        with(nodesByName.getValue(childName)) {
            parent.children.add(this)
            this.parent = parent
        }
    }

    // Find the one node we have without a parent. Or freak out.
    return nodesByName.values.firstOrNull { it.parent == null }
        ?: throw IllegalStateException("No head node?!")
}

That might look like a lot, so let me go over it section by section.

Declare a Map to store each one of our Node objects, by name. This saves lookup time later.
Declare a Set of Pairs of parent Node to child name (String). In the diagram above, these are the edges.
Create a regular expression to parse our row. This one says “give me only the tokens that are all letters or numbers”. This will allow us to filter out stuff like ->, commas, and whitespace.
For each input we’re going to:
1. Tell the regex to break our input row up into tokens.
2. Create a Node from the first two tokens (the name and weight!).
3. Store the node in the Map, by its name.
4. For all remaining tokens, if any, create a parent/child record to come back to.
At this point, we will link parents with children, so go through all of our parent/child pairs, find the corresponding Node objects and link them up.
We now have a fully-formed tree! Find the one node that doesn’t have a parent and that’s the root of the tree!

And of course, that solves part one, just return the name of the root node!

fun solvePart1(): String =
    headOfTree.name

I want to point out a couple of things about the parsing code. First, I’m using Kotlin’s triple-quote syntax ("""). That makes my regular expression look cleaner because I don’t have to escape backslashes like ths: \\w+. That’s not a big deal in this example, but as expressions get more complicated it makes sense to use triple-quote.

Another thing to call out is my use of Map.getValue(). Why us that over Map[name]? Because that would return a possibly null value, and if I know for a fact that the value is there (like in this case), I can use getValue(), which will throw an exception if I’m wrong. I’m happy to make that trade here.

All that parsing has earned us our first star of the day. Let’s take a peek at part two!

⭐ Day 7, Part 2

The puzzle text can be found here.

This isn’t as hard as it looks thanks to the way the problem input is defined. First, any parent that has children has at least three. This means that any child out of balance will stand out. If child structures came in pairs, we wouldn’t really know which one is “off”. But because of this, we can always find the out-of-balance child because it’s the only one with a distinct total weight.

Speaking of weights, let’s add some code to our Node class to weigh our subtrees:

// Node
private val totalWeight: Int by lazy {
    weight + children.sumBy { it.totalWeight }
}

private val childrenAreBalanced: Boolean by lazy {
    children.map { it.totalWeight }.distinct().size == 1
}

What kind of evil sorcery is this? OK, calm down. We could have defined these as functions, but since the values don’t change, I’ll define them as properties. The by lazy bit is a Delegated Property , a nice Kotlin feature that comes in handy quite often. Because our weights don’t ever change, and we only want to calculate them when we ask for it, we can wrap them this way (in a lazy delegate). The lazy delegate will take care of calculating the answer the first time we ask and returning it every other time. We don’t strictly have to make this a lazy property, we could have made it a function, but since we don’t actually know the child Nodes at construction time, this is clearer.

To get the total weight of subtree, we will add our weight and the weight of all our children’s subtrees. We also want to know if our children are all balanced. This comes in handy when figuring out where the imbalance is, so we just weigh them all and count how many distinct values we have. They should all be the same.

Now we need to decide how to find the imba lance itself. If you read the description above enough times (like I did), it becomes clear that we’re looking at an imbalanced node if:

The parent tells the node that it’s part of an imbalanced sub-tree.
ALL of it’s children have equal weight.

If we hit that state, the node we’re looking at is the problem. Otherwise, we should go off and find which one of the node’s children are imbalanced and repeat the process. It might not surprised you to find out that I’ve written this as a recursive function. Recursive functions and trees go together.

// Node
fun findImbalance(imbalance: Int? = null): Int =

    if (imbalance != null && childrenAreBalanced) {
        // We end when I have a positive imbalance and my children are balanced.
        weight - imbalance
    } else {
        // Find the child tree that is off.
        val subtreesByWeight = children.groupBy { it.totalWeight }

        // Find the imbalanced child tree (they will be the lone node in the list, when grouped by weight)
        val badTree = subtreesByWeight.minBy { it.value.size }?.value?.first()
            ?: throw IllegalStateException("Should not be balanced here.")

        // Recurse, passing down our imbalance. If we don't know the imbalance, calculate it.
        // Calculate the imbalance as the absolute value of the difference of all distinct weights
        badTree.findImbalance(imbalance ?: subtreesByWeight.keys.reduce { a, b -> a - b }.absoluteValue)
    }

I’ve annotated this code inline, but let’s go through it. Notice that we carry around an imbalance, which we can calculate right away because only one node is wrong. The first thing to do in any recursive function is to test your end condition (carrying an imbalance, all children are balanced). If that’s true, we’ll return the node weight minus the imbalance and get our answer. In principle, I could ignore the null check of imbalance, but I like that checking for it gives me a smart cast when calculating the answer on the next line.

If we need to keep searching, we group all of our children but their total weight. One of them stands out as the badTree because they are the only one with that weight. That’s because our input guarantees it. Once we find the badTree recurse, asking it to find the imbalance, and pass the already calculated imbalance to it. If we don’t know what the imbalance is yet, calculate it. To do that, it’s the absolute value of the difference between all of the child subtrees.

This returns our correct answer and performs very fast (around 15ms including parsing, for me).

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

7 days, one full week completed! We’ve earned 14 stars with 36 left to go!

⭐ Day 7, Part 1

⭐ Day 7, Part 2

Further Reading