Solution for Advent of Code 2018 - Day 8: Memory Maneuver

Link to the puzzle text

Part 1

In this puzzle, we have a list of numbers describing a tree structure of nodes. We have to parse this list into a usable form first. The first number of a list shows the number of child nodes and the second shows the number of meta data entries. After that are list entries for the child nodes and the data entries. The child nodes have to be parsed recursively. Once that is done, the answer is the sum of all meta data entries.

For parsing, we created a simple Node class. The parse function keeps track of the current local offset and returns the length of the current node. This way, once we return from parsing a child node, we can skip over its entries:

def parse(data, node):
    num_children = data[0]
    num_meta_data = data[1]
    offset = 2
    for i in range(num_children):
        node.children.append(Node())
        offset += parse(data[offset:], node.children[i])
    for j in range(num_meta_data):
        node.data.append(data[offset + j])
    offset += num_meta_data
    return offset

The metadata sum is also done recursively.

Part 2 

In part 2, we have to calculate a value function. This is done by using the metadata entries as indizes into the child nodes. Invalid indizes are ignored and if a child has no child nodes, we return the sum of all meta data instead.

We can implement this recursively again using the previously parsed structure. We had to check for invalid indizes, otherwise iterate over the data entries, call the value function of the selected child and sum it up:

def value(node):
    if len(node.children) == 0:
        return sum(node.data)
    partial_sum = 0
    for index in node.data:
        if index - 1 < len(node.children):
            partial_sum += value(node.children[index - 1])
    return partial_sum

 

Link to my solutions