# AoC Day 8: Memory Maneuver E. Choroba Updated on ・1 min read

Day 8!
Today's tasks felt much easier than yesterday's, but maybe it was because they were closer to what I used to do at \$job - 2.

Let's recursively parse a tree from a sequence of integers! Meaning of each number depends on its position in the sequence and on the meaning of the other numbers...

### Discussion  Ali Spittel

Kinda happy with this one!

``````from collections import deque

with open('input.txt', 'r') as f:
data = deque()
for line in f:
for val in line.split(' '):
data.append(int(val))

class Tree:
def __init__(self, data):
self.n_children = data.popleft()
self.children = [Tree(data) for _ in range(self.n_children)]

def get_total(self):
return sum(self.metadata) + sum(child.get_total() for child in self.children)

def get_child_value(self, child):
if child < len(self.children):
return self.children[child].get_root_value()
return 0

def get_root_value(self):
total = 0
total += self.get_child_value(idx - 1) # Index starts at 1 not 0 :(

tree = Tree(data)
print(tree.get_total())
print(tree.get_root_value())
`````` Woah, that recursive constructor for `Tree` is really clever!

I considered building an object and then processing it after the fact, but decided to process it as I parsed it...I regretted that when I saw part 2 though 😅 Neil Gall

I was missing parser combinators so came back and did day 8 again.

``````data class Node(val children: List<Node>, val metadata: List<Int>)

fun parse(input: String): Node {
val integer = Terminals.IntegerLiteral.PARSER.map(String::toInt)

val treeRef = Parser.Reference<Node>()

fun nodeParser(numChildren: Int, numMetadata: Int): Parser<Node> =
sequence(
treeRef.lazy().times(numChildren),
::Node
)

val nodeInfo: Parser<Pair<Int, Int>> = sequence(integer, integer) { nc, nm -> Pair(nc, nm) }
val tree: Parser<Node> = nodeInfo.next { (nc, nm) -> nodeParser(nc, nm) }
treeRef.set(tree)

val parser = tree.from(Terminals.IntegerLiteral.TOKENIZER, Scanners.WHITESPACES)
return parser.parse(input.trim())
}
``````

It was initially much more dense but I tried to break it up to make it easier to follow. It's not the One True Way of parsing for nothing you know! Carly Ho 🌈

PHP

Recursion, or: finally a chance to use my degree. Did I need to actually build the tree in Part 2? Probably not, but it made it easier to organize the data and actually do the recursion, so ¯_(ツ)_/¯

Part 1:

``````<?php
\$input = trim(file_get_contents(\$argv));
\$numbers = array_map(function(\$x) {
return intval(\$x);
}, explode(" ", trim(\$input)));
\$pos = 0;
\$meta_entries = array();

function get_children(\$c) {
global \$numbers;
global \$pos;
global \$meta_entries;

\$count = 0;
\$pos += 2;
while (\$count < \$c && \$pos < count(\$numbers)) {
\$children = \$numbers[\$pos];
\$metacount = \$numbers[\$pos+1];

if (\$children > 0) {
get_children(\$children);
} else {
\$pos += 2;
}

if (\$metacount > 0) {
\$meta_entries = array_merge(\$meta_entries, array_slice(\$numbers, \$pos, \$metacount));
\$pos += \$metacount;
}
\$count++;
}
return;
}

while (\$pos < count(\$numbers)) {
\$children = \$numbers[\$pos];
\$metacount = \$numbers[\$pos+1];
if (\$children > 0) {
get_children(\$children);
} else {
\$pos += 2;
}
if (\$metacount > 0) {
\$meta_entries = array_merge(\$meta_entries, array_slice(\$numbers, \$pos, \$metacount));
\$pos += \$metacount;
}
}

echo array_sum(\$meta_entries);
die(1);
``````

Part 2:

``````<?php
\$input = trim(file_get_contents(\$argv));
\$numbers = array_map(function(\$x) {
return intval(\$x);
}, explode(" ", trim(\$input)));
\$pos = 0;
\$meta_entries = array();
\$tree = array();

function get_children(\$c) {
global \$numbers;
global \$pos;

\$childnodes = array();

\$count = 0;
\$pos += 2;

while (\$count < \$c && \$pos < count(\$numbers)) {
\$children = \$numbers[\$pos];
\$metacount = \$numbers[\$pos+1];

array_push(\$childnodes, array(
'childcount' => \$children,
'metacount' => \$metacount,
'children' => array(),
'meta' => array(),
'value' => 0
));

if (\$children > 0) {
\$childnodes[\$count]['children'] = get_children(\$children);
} else {
\$pos += 2;
}

if (\$metacount > 0) {
\$childnodes[\$count]['meta'] = array_slice(\$numbers, \$pos, \$metacount);
if (\$childnodes[\$count]['childcount'] == 0) {
\$childnodes[\$count]['value'] = array_sum(\$childnodes[\$count]['meta']);
} else {
foreach (\$childnodes[\$count]['meta'] as \$m) {
if (array_key_exists(\$m-1, \$childnodes[\$count]['children'])) {
\$childnodes[\$count]['value'] += \$childnodes[\$count]['children'][\$m-1]['value'];
}
}
}
\$pos += \$metacount;
}
\$count++;
}
return \$childnodes;
}

\$children = \$numbers[\$pos];
\$metacount = \$numbers[\$pos+1];
array_push(\$tree, array(
'childcount' => \$children,
'metacount' => \$metacount,
'children' => array(),
'meta' => array(),
'value' => 0
));
if (\$children > 0) {
\$tree['children'] = get_children(\$children);
} else {
\$pos += 2;
}
if (\$metacount > 0) {
\$tree['meta'] = array_slice(\$numbers, \$pos, \$metacount);
}
if (\$tree['childcount'] == 0) {
\$tree['value'] = array_sum(\$t['meta']);
} else {
foreach (\$tree['meta'] as \$i=>\$m) {
if (array_key_exists(\$m-1, \$tree['children'])) {
\$tree['value'] += \$tree['children'][\$m-1]['value'];
}
}
}
echo \$tree['value'];
die(1);
`````` Bjarne Magnussen

Here is my Golang solution for today's problem. It was more easy for me to solve today, but made me learn to use pointers in Golang to consume the input string. I don't think this is necessarily the best way to use pointers, but I liked the simplicity in this case.

``````package main

import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)

// A simple structure of a node.
type node struct {
children []node
}

// and returns a slice of its lines.
func readLines(path string) ([]string, error) {
file, err := os.Open(path)
if err != nil {
return nil, err
}
defer file.Close()

var lines []string
scanner := bufio.NewScanner(file)
for scanner.Scan() {
lines = append(lines, scanner.Text())
}
return lines, scanner.Err()
}

// function to consume elements from the input string.
func consume(parseNodes *[]string) int {
i, _ := strconv.Atoi((*parseNodes))
*parseNodes = (*parseNodes)[1:]
return i
}

// function to parse a node from the input string.
numChildren := consume(parseNodes)
var children []node
for c := 0; c < numChildren; c++ {
}
for m := 0; m < numMetaData; m++ {
}
// Create and return node:
}

// function to get the sum of meta data from a given node.
func getMeta(node node) int {
// Read meta data of this node:
// Run through each child and get meta data:
for _, c := range node.children {
meta = append(meta, getMeta(c))
}
var sum int
// Sum the meta data:
for _, m := range meta {
sum += m
}
return sum
}

// function to get the value of a given node.
func getValue(node node) int {
numChildren := len(node.children)
var value int
if numChildren == 0 {
// If the node has no children return just the sum of
// the meta data for thid node:
value = getMeta(node)
} else {
// If this node has children return the sum of the
// values for each child:
for _, m := range node.metaData {
m-- // for correct indexing
if m >= 0 && m < numChildren {
// Only get value if index is not out of bound
value += getValue(node.children[m])
}
}
}
return value
}

func main() {
if err != nil {
panic(err)
}
nodeString := strings.Split(data, " ")

fmt.Println("Part 1:")
fmt.Println(getMeta(root))

fmt.Println("Part 2:")
fmt.Println(getValue(root))

}
`````` Neil Gall

Agreed, today's was much simpler. My Kotlin:

``````package adventofcode2018.day8

import java.io.File

// Parsing

fun parse(input: String): List<Int> {
return input.trim().split(" ").map(String::toInt)
}

// Part 1

data class Node(val children: List<Node>, val metadata: List<Int>)

metadata.sum() + children.fold(0) { n: Int, c: Node -> n + c.metadataTotal() }

fun tree(input: List<Int>): Pair<Node, List<Int>> {
val numChildren = input

val (children, remainder) = (1..numChildren).fold(Pair(listOf<Node>(), input.drop(2))) { (cs, input), _ ->
val (child, input_) = tree(input)
Pair(cs + child, input_)
}

}

fun part1(input: List<Int>): Int = tree(input).first.metadataTotal()

// Part 2

if (children.isEmpty())
else
total + (if (children.indices.contains(i-1)) children[i-1].metadataComplex() else 0)
}

fun part2(input: List<Int>): Int = tree(input).first.metadataComplex()

fun main(args: Array<String>) {
println("Part 1: \${part1(input)}")
println("Part 2: \${part2(input)}")
}
`````` Florian Rohrer

Here is my Python Solution:

Both parts

``````with open("input.txt") as f:
numbers = [int(x) for x in next(f).split()]

class Node(object):
self.n_childs = n_childs
self.childs = []

it = iter(numbers)
root = Node(next(it), next(it))

stack = []
for _ in range(root.n_childs):
stack.append(("childs", root))

while stack:
inst, current = stack.pop()
if inst == "childs":
new_node = Node(next(it), next(it))
current.childs.append(new_node)
for _ in range(new_node.n_childs):
stack.append(("childs", new_node))
else:
``````

Part 1

``````def tree_sum(n):
return sum(n.metadata)+sum(tree_sum(c) for c in n.childs)

print(tree_sum(root))
``````

Part 2

``````def tree_sum2(n):
if len(n.childs) == 0:
else:
d = dict((i+1, c) for i, c in enumerate(n.childs))
return sum(tree_sum2(d.get(m, Node(0,0))) for m in n.metadata)

print(tree_sum2(root))
`````` E. Choroba

And here are my Perl solutions:

Part 1

``````#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use List::Util qw{ sum };

my @n = split ' ', <>;

sub process {
my (\$pos, \$sum) = @_;
my \$child_tally = \$n[\$pos++];
my \$data_size   = \$n[\$pos++];
for (1 .. \$child_tally) {
my \$ch = process(\$pos, \$sum);
\$sum = \$ch->;
\$pos = \$ch->;
}
\$sum += sum(0, @n[ \$pos .. \$pos + \$data_size - 1 ]);
\$pos += \$data_size;
return [ \$pos, \$sum ];
}

say process(0, 0)->;
``````

Part 2

``````#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use List::Util qw{ sum };

my @n = split ' ', <>;

sub process {
my (\$pos, \$sum) = @_;
my \$child_tally = \$n[\$pos++];
my \$data_size   = \$n[\$pos++];
my @ch;
for (1 .. \$child_tally) {
my \$ch = process(\$pos, \$sum);
push @ch, \$ch->;
\$pos = \$ch->;
}

if (\$child_tally) {
\$sum += sum(map {
\$ch[\$_ - 1] // 0
} @n[ \$pos .. \$pos + \$data_size - 1 ]);

} else {
my \$v = sum(@n[ \$pos .. \$pos + \$data_size - 1 ]);
\$sum += \$v;
}

\$pos += \$data_size;
return [ \$pos, \$sum ];
}

say process(0, 0)->;
`````` Ryan Palo

@choroba , thanks again for putting this post up! Sorry for not getting it out on time yesterday.

I liked this challenge! Something about this one just worked out for me and I didn't have to wrestle with it very much. Also, this was my first time defining a recursive data structure in Rust, and I didn't have any issues -- hopefully I did it the right way!

## Part 1

``````/// Day 8: Memory Maneuver
///

/// A node in a GPS Licensing tree structure
pub struct Node {
children: Vec<Box<Node>>,
}

impl Node {
pub fn new() -> Self {
Self { metadata: vec![], children: vec![] }
}

/// Generates a node from a string of space-separated integers
pub fn from_text(text: &str) -> Self {
let data: Vec<usize> = text.split(' ').map(|num|{
num.parse().unwrap()
}).collect();
let (node, _ptr) = Node::build_child(&data, 0);
node
}

/// Builds a child based on a strand of data and a pointer to start at.
///
/// These nodes are recursive in their layout.  So, for example,
/// the root node has a header at the start of the string, and its
/// metadata comes after all of the rest of the nodes in the tree
fn build_child(data: &Vec<usize>, start: usize) -> (Node, usize) {
let mut result = Node::new();
let mut ptr = start;
let children = data[ptr];
ptr += 1;
ptr += 1;

for _i in 0..children {
let (node, new_ptr) = Node::build_child(&data,ptr);
result.children.push(Box::new(node));
ptr = new_ptr;
}

(result, ptr)
}

/// Calculate the recurive total of all the metadata here and below
pub fn metadata_total(&self) -> usize {
let children_total: usize = self.children.iter()
}
}
``````

## Part 2

For part 2, I didn't have to change the data structure at all, I just created the `value` function to describe how the new thing was calculated.

``````impl Node {

/// Calculates a node's value.
///
/// Value is defined like this:
///  - if a node has no children, it's the sum of the metadata
///  - if a node *does* have children, value is defined recursively,
///    and each metadata is a pointer at a particular child.
///    This node's value is the sum of *those* nodes' values.
///    If a pointer is invalid, skip it.
pub fn value(&self) -> usize {
if self.children.is_empty() { return self.metadata.iter().sum(); }

let mut total: usize = 0;
if *pointer < 1 || *pointer > self.children.len() { continue; }

total += self.children.get(*pointer - 1)
.expect("Couldn't get child value")
.value();
}
total
}
}
`````` Tiago Romero Garcia

## JavaScript solution

``````const fs = require('fs');

const readLines = (file, onLine) => {
crlfDelay: Infinity
});

return new Promise(resolve => reader.on('close', resolve));
};

const readFile = async file => {
const lines = [];
return lines;
}

module.exports = {
};
``````

#### 08-common.js

``````class Node {
this.childNodesSize = +childNodesSize;
this.childNodes = [];
}
}

const buildNode = (input, i = 0) => {
const node = new Node(input[i], input[i + 1]);
i += 2;

for (let j = 0; j < node.childNodesSize; j++) {
let [children, newI] = buildNode(input, i);
i = newI;
node.childNodes.push(children);
}

return [node, i];
};

const buildTree = input => {
const [root, i] = buildNode(input);
return root;
};

module.exports = {
Node,
buildNode,
buildTree
};
``````

#### 08a.js

``````const { readFile } = require('./reader');
const { buildTree } = require('./08-common');

const sumMetadata = root => {
let total = 0;
let queue = [root];
while (queue.length > 0) {
const node = queue.shift();
total += node.metadataEntries.reduce((sum, entry) => sum + entry, 0);
queue.push(...node.childNodes);
}
};

(async () => {

const tree = buildTree(lines.split(' '));

console.log(`The sum of all metadata entries is \${sum}`);
})();
``````

#### 08b.js

``````const { readFile } = require('./reader');
const { buildTree } = require('./08-common');

const getNodeValue = node => {
let value = 0;
if (node.childNodesSize === 0) {
value += node.metadataEntries.reduce((sum, entry) => sum + entry, 0);
}
else {
for (let entry of node.metadataEntries) {
const child = node.childNodes[entry-1];
if (child) {
value += getNodeValue(child);
}
}
}
return value;
}

const getRootNodeValue = root => {
return getNodeValue(root);
};

(async () => {

const tree = buildTree(lines.split(' '));

const rootNodeValue = getRootNodeValue(tree);

console.log(`The value of the root node is is \${rootNodeValue}`);
})();
`````` Nicolas Gleichgerrcht

This is my js solution using recursive functions

Part1

``````import { readFileSync } from 'fs'
// data as array
const data = readFileSync('./data', {encoding: 'utf8'}).trim().split(" ").map(Number)
// recursive fn
// return the index that the current child ends and the children metadata
const addNode = (index) => {
let children = data[index]
while(children > 0) {
index = childData.newIndex
children--
}
for(let i = 0; i < metadata ; i++) {
totalMetadata += data[index + i + 2]
}
}

``````

Part 2

``````
import { readFileSync } from 'fs'

const data = readFileSync('./data', {encoding: 'utf8'}).trim().split(" ").map(Number)
// recursive fn
// return the child index, metadata qty, and the metadata for the childs
const addNode = (index) => {
const realIndex = index
let children = data[index]
if(children > 0) {
for(let i = 0; i < children; i++) {
index = childData.newIndex
}
for(let i = 0; i < metadata ; i++) {
const childMetadataToGet = data[index + i + 2] - 1
}
} else {
for(let i = 0; i < metadata ; i++) {
totalMetadata += data[index + i + 2]
}
}
}

`````` I liked this challenge a lot! It felt a lot more straightforward than the other problems.

The code came out extremely succinct, too, which is always nice. IMO it's quite readable:

Part 1:

``````function sum_metadata(input)
nums = split(input, " ")
result = total_for_node(nums)

return result
end

function total_for_node(nums)
num_children = parse(Int, popfirst!(nums))
total = 0
for i in 1:num_children
total += total_for_node(nums)
end
meta = parse(Int, popfirst!(nums))
total += meta
end
end
``````

Part 2 looks almost identical to part 1, but with an extra branch in the middle.

``````function sum_child(input)
nums = split(input, " ")
result = total_for_node(nums)

return result
end

function total_for_node(nums)
num_children = parse(Int, popfirst!(nums))
all_childs = []
for i in 1:num_children
append!(all_childs, total_for_node(nums))
end
total = 0
if length(all_childs) == 0
meta = parse(Int, popfirst!(nums))
total += meta
end
else  