Advent of Code 2018 Day 8: Memory Maneuver
Tags: aoc2018, python, puzzle, challenge
Published: 2019-06-17 05:43:00

---
title: "Advent of Code 2018 Day 8: Memory Maneuver"
tags: ["aoc2018", "python", "puzzle", "challenge"]
published: true
categories: ["Advent of Code 2018"]
description: "Even Santa has to deal with software licensing and non standard serialisation formats."
---
> This post originally appeared on [steadbytes.com](https://steadbytes.com/blog/advent-of-code-2018/08/)
> Complete solution can be found on [GitHub](https://github.com/SteadBytes/advent-of-code-2018/blob/7087a1e89ae7424b63f38c137d36d24b56a2965b/08/solution.py)

## Part One

Our [puzzle input](https://github.com/SteadBytes/advent-of-code-2018/blob/1a02e64c19f485fd2730462a2e69cbe89c5ba136/08/input.txt) is a license file (unfortunately not an [open source](https://opensource.org/licenses) one) for the navigation software on Santa's sleigh. The license is comprised of a list of numbers representing a _serialised_ [tree](<https://en.wikipedia.org/wiki/Tree_(data_structure)>) data structure. Unfortunately, the creators of the software either haven't heard of standard [serialisation formats](https://en.wikipedia.org/wiki/Serialization#Serialization_formats) or have a case of [Not Invented Here Syndrome](https://en.wikipedia.org/wiki/Not_invented_here) (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:

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

For the example input, this produces list:

```python
[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

```python
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

```python
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:

```python
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](<https://en.wikipedia.org/wiki/Tree_(data_structure)>)
- [Recursion](<https://en.wikipedia.org/wiki/Recursion_(computer_science)>)
- [OSS Licenses](https://opensource.org/licenses)
- [Not Invented Here Syndrome](https://en.wikipedia.org/wiki/Not_invented_here)