Ben Steadman
Posted on June 17, 2019
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):
- Retrieve the header of the first node
- 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
- 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
- Retrieve the header of the first node
- 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
- Else, find the value of each child node by recursing with the header from step 1 removed from the list of entries
- 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
Posted on June 17, 2019
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.