Advent of Code 2018 Day 8: Memory Maneuver

This post originally appeared on steadbytes.com
Complete solution can be found on GitHub

Part One

Our puzzle input is a license file (unfortunately not an open source one) for the navigation software on Santa's sleigh. The license is comprised of a list of numbers representing a serialised tree data structure. Unfortunately, the creators of the software either haven't heard of standard serialisation formats or have a case of Not Invented Here Syndrome (I will dig into the exact format shortly). We are asked to parse the license file to find the total sum of all the metadata entries present in the license file.

Input Format

The tree is serialised in the license file by 'nesting' the values for each node in the tree according to their hierarchical structure. We are told that a node consists of:

• A header
• Zero or more child nodes
  • Nested within their parent nodes, immediately following the header.
• One or more metadata entries
  • Immediately following all child nodes.

The header consists of exactly two numbers representing the quantities of:

• Child nodes
• Metadata entries

Using the example input from the puzzle:

# license file
2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2

# tree
A -> [1, 1, 2]
|
|-B -> [10, 11, 12]
|
|-C -> [2]
  |
  |-D -> [99]

Parsing Input

Since we only need to calculate the sum of the metadata entries, de-serialising the license file into a full tree data structure isn't necessary. The algorithm outlined below requires only the list of numbers from the license file. This can be done using a list comprehension to convert each number in the file to an integer:

with open("input.txt") as f:
    entries = [int(e) for e in f.read().split()]

For the example input, this produces list:

[2, 3, 0, 3, 10, 11, 12, 1, 1, 0, 1, 99, 2, 1, 1, 2]

Algorithm

As is often the case with problems involving trees, a recursive algorithm is a natural approach. The total metadata in the tree is given by the following recursion:

children(node) == []: sum(meta(node))
children(node) == [child_1, child_2,..., child_n]: sum(meta(child_1), meta(child_2), ..., meta(child_n))

More concretely, given a list of entries (numbers in the license file):

1. Retrieve the header of the first node
2. If the header indicates no child nodes, return the sum of the metadata values
   • i.e. sum of all remaining entries in the list after the header
3. Else, recurse with the header from step 1 removed from the list of entries

def part_1(entries):
    def recurse(entries):
        # retrieve header of current node
        n_child, n_meta = entries[:2]
        # remove header (move to next node)
        remaining = entries[2:]

        # total metadata from current node -> leaves
        meta_total = 0

        # node has children: recurse to find total metadata from children -> leaves
        # removes all entries between current node header and current node metadata
        for _ in range(n_child):
            child_total, remaining = recurse(remaining)
            meta_total += child_total

        # calculate total metadata for the current node
        current_node_meta = remaining[:n_meta]
        current_node_meta_total = sum(current_node_meta)

        meta_total += current_node_meta_total

        return meta_total, remaining[n_meta:]

    meta_total, _ = recurse(entries)
    return  meta_total

For my puzzle input, the answer is 48260.

Part Two

Now we are asked to find the value of the root node in the tree. The value of a node is specified as:

children(node) == []: sum(meta(node))

children(node) == [child_1, child_2,..., child_n], meta(node) = [meta_1, meta_2, ..., meta_n]:
    sum(value(children(node)[meta_1]), (children(node)[meta_2]), ..., (children(node)[meta_n]))

• If a node has children, each metadata value represents an index of a child node. The value of the node is then the sum of the values of all the child nodes represented by the metadata.
  • Non-existent child node indexes are skipped
  • 0 indexes are skipped

Algorithm

1. Retrieve the header of the first node
2. If the header indicates no child nodes, return the sum of the metadata values
   • i.e. sum of all remaining entries in the list after the header
3. Else, find the value of each child node by recursing with the header from step 1 removed from the list of entries
4. Sum up the value of each child node referenced in the metadata of the node

def part_2(entries):
    def recurse(entries):
        # retrieve header of current node
        n_child, n_meta = entries[:2]
        # remove header (move to next node)
        remaining = entries[2:]

        # values of all children of the current node -> leaves
        child_node_values = []

        # node has children: recurse to find values from children -> leaves
        # removes all entries between current node header and current node metadata
        for _ in range(n_child):
            child_value, remaining = recurse(remaining)
            child_node_values.append(child_value)

        # calculate total metadata for the current node
        current_node_meta = remaining[:n_meta]
        current_node_meta_total = sum(current_node_meta)

        if n_child == 0:
            current_node_value = current_node_meta_total
        else:
            # sum up all values of children nodes referenced be index in metadata
            current_node_value = sum(
                child_node_values[i - 1]  # account for 0 based index
                for i in current_node_meta
                # skip 0 index and non-existent indexes
                if i > 0 and i <= len(child_node_values)
            )

        return current_node_value, remaining[n_meta:]

    root_node_value, _ = recurse(entries)
    return root_node_value

For my puzzle input, the answer is 25981.

This algorithm is very similar to that of part one, in fact all the work to sum up the metadata for
each node in the tree from part 1 is still required. As such, the repeated logic for part_1 and part_2 can be refactored into a single function:

def parse_entries(entries):
    """ Find sum of all metadata entries (part 1) and the root node value (part 2)
    from the list of entries in the license file.

    Returns:
        (int, int): sum of all metadata entries, root node value - see puzzle
            description
    """

    def recurse(entries):
        # retrieve header of current node
        n_child, n_meta = entries[:2]
        # remove header (move to next node)
        remaining = entries[2:]

        # total metadata from current node -> leaves
        meta_total = 0
        # values of all children of the current node -> leaves
        child_node_values = []

        # node has children: recurse to find values from children -> leaves
        # removes all entries between current node header and current node metadata
        for _ in range(n_child):
            child_total, child_value, remaining = recurse(remaining)
            meta_total += child_total
            child_node_values.append(child_value)

        current_node_meta = remaining[:n_meta]
        current_node_meta_total = sum(current_node_meta)

        meta_total += current_node_meta_total

        if n_child == 0:
            current_node_value = current_node_meta_total
        else:
            # sum up all values of children nodes referenced be index in metadata
            current_node_value = sum(
                child_node_values[i - 1]  # account for 0 based index
                for i in current_node_meta
                # skip 0 index and non-existent indexes
                if i > 0 and i <= len(child_node_values)
            )

        return meta_total, current_node_value, remaining[n_meta:]

    return recurse(entries)[:2]


def part_1(entries):
    return parse_entries(entries)[0]


def part_2(entries):
    return parse_entries(entries)[2]

Resources

• Trees
• Recursion
• OSS Licenses
• Not Invented Here Syndrome