Solution for Advent of Code 2017 - Day 7: Recursive Circus

Link to the puzzle text

Part 1

In this puzzle, we have a tree of nodes each with a weight. The tree is written in an inconvenient format, consisting of an unordered list of each node with their child nodes. We are asked to find the root node.

After parsing each line, we got two dictionaries: one mapping the nodes to its weights, one mapping the node to its children. For getting the root node, we follow from a random starting node upwards until the end.

To find the parent root, we iterate over all nodes and find a node, in whose child node list we are. This is repeated until we find a root without a parent. This must be the root node.

def get_root(tree):
    root_name = list(tree.keys())[0]
    while True:
        new_root = root_name
        for name in tree.keys():
            if new_root in tree[name]:
                new_root = name
                break
        if new_root == root_name:
            return root_name
        root_name = new_root

Part 2

In part 2, we look at the weights of the nodes. In each node, the total weights of each child should be the same to stay balanced. We should find the single node preventing the tree to be balanced and what its weight should be.

To find the node causing the tree to be unbalanced, we start at the root. We get the total weights of each child nodes and descend into the one with a weight different to the others. This is continued until each children are balanced again, then we are at the correct node.

def balance_tree(root):
    node = root
    while True:
        child_nodes = tree[node]
        node_weights = [get_weight(child) for child in child_nodes]
        
        if len(set(node_weights)) == 1:
            # we found the node with wrong weight
            break
        i = index_of_different(node_weights)
        node = child_nodes[i]

To find its correct weight, we kept track of the diff amount between the children until now and can use that to calculate the correct weight.

Link to my solutions