Skip to Content

Advent of Code 2017 - Day 7, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 7: 'Recursive Circus'

Posted on

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

Get comfortable, this description is quite lengthy.

Wandering further through the circuits of the computer, you come upon a tower of programs that have gotten themselves into a bit of trouble. A recursive algorithm has gotten out of hand, and now they’re balanced precariously in a large tower.

One program at the bottom supports the entire tower. It’s holding a large disc, and on the disc are balanced several more sub-towers. At the bottom of these sub-towers, standing on the bottom disc, are other programs, each holding their own disc, and so on. At the very tops of these sub-sub-sub-…-towers, many programs stand simply keeping the disc below them balanced but with no disc of their own.

You offer to help, but first you need to understand the structure of these towers. You ask each program to yell out their name, their weight, and (if they’re holding a disc) the names of the programs immediately above them balancing on that disc. You write this information down (your puzzle input). Unfortunately, in their panic, they don’t do this in an orderly fashion; by the time you’re done, you’re not sure which program gave which information.

For example, if your list is the following:

pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)

…then you would be able to recreate the structure of the towers that looks like this:

                gyxo
              /     
         ugml - ebii
       /      \     
      |         jptl
      |        
      |         pbga
     /        /
tknk --- padx - havc
     \        \
      |         qoyq
      |             
      |         ktlj
       \      /     
         fwft - cntj
              \     
                xhth

In this example, tknk is at the bottom of the tower (the bottom program), and is holding up ugml, padx, and fwft. Those programs are, in turn, holding up other programs; in this example, none of those programs are holding up any other programs, and are all the tops of their own towers. (The actual tower balancing in front of you is much larger.)

Before you’re ready to help them, you need to make sure your information is correct. What is the name of the bottom program?

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.

  1. Declare a Map to store each one of our Node objects, by name. This saves lookup time later.
  2. Declare a Set of Pairs of parent Node to child name (String). In the diagram above, these are the edges.
  3. 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.
  4. 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.
  5. 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.
  6. 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 programs explain the situation: they can’t get down. Rather, they could get down, if they weren’t expending all of their energy trying to keep the tower balanced. Apparently, one program has the wrong weight, and until it’s fixed, they’re stuck here.

For any program holding a disc, each program standing on that disc forms a sub-tower. Each of those sub-towers are supposed to be the same weight, or the disc itself isn’t balanced. The weight of a tower is the sum of the weights of the programs in that tower.

In the example above, this means that for ugml's disc to be balanced, gyxo, ebii, and jptl must all have the same weight, and they do: 61.

However, for tknk to be balanced, each of the programs standing on its disc and all programs above it must each match. This means that the following sums must all be the same:

ugml + (gyxo + ebii + jptl) = 68 + (61 + 61 + 61) = 251
padx + (pbga + havc + qoyq) = 45 + (66 + 66 + 66) = 243
fwft + (ktlj + cntj + xhth) = 72 + (57 + 57 + 57) = 243

As you can see, tknk's disc is unbalanced: ugml's stack is heavier than the other two. Even though the nodes above ugml are balanced, ugml itself is too heavy: it needs to be 8 units lighter for its stack to weigh 243 and keep the towers balanced. If this change were made, its weight would be 60.

Given that exactly one program is the wrong weight, what would its weight need to be to balance the entire tower?

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:

  1. The parent tells the node that it’s part of an imbalanced sub-tree.
  2. 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!

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 7
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - The Trees, by Rush