## DEV Community is a community of 851,150 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

E. Choroba

Posted on • Updated on

# AoC Day 8: Memory Maneuver

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 (13)

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.n_metadata = data.popleft()
self.children = [Tree(data) for _ in range(self.n_children)]
self.metadata = [data.popleft() for _ in range(self.n_metadata)]

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):
if not self.children: return sum(self.metadata)
total = 0
for idx in self.metadata:
total += self.get_child_value(idx - 1) # Index starts at 1 not 0 :(
return total

tree = Tree(data)
print(tree.get_total())
print(tree.get_root_value())
``````
Mustafa Haddara

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 😅

Ryan Palo

`deque` FTW! Nice!

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),
integer.times(numMetadata),
::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[1]));
\$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[1]));
\$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[0]['children'] = get_children(\$children);
} else {
\$pos += 2;
}
if (\$metacount > 0) {
\$tree[0]['meta'] = array_slice(\$numbers, \$pos, \$metacount);
}
if (\$tree[0]['childcount'] == 0) {
\$tree[0]['value'] = array_sum(\$t['meta']);
} else {
foreach (\$tree[0]['meta'] as \$i=>\$m) {
if (array_key_exists(\$m-1, \$tree[0]['children'])) {
\$tree[0]['value'] += \$tree[0]['children'][\$m-1]['value'];
}
}
}
echo \$tree[0]['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
metaData []int
}

// readLines reads a whole file into memory
// 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)[0])
*parseNodes = (*parseNodes)[1:]
return i
}

// function to parse a node from the input string.
func readNode(parseNodes *[]string) node {
// Read header
numChildren := consume(parseNodes)
numMetaData := consume(parseNodes)
// Read children:
var children []node
for c := 0; c < numChildren; c++ {
children = append(children, readNode(parseNodes))
}
// Read meta data:
var metaData []int
for m := 0; m < numMetaData; m++ {
metaData = append(metaData, consume(parseNodes))
}
// Create and return node:
return node{children: children, metaData: metaData}
}

// function to get the sum of meta data from a given node.
func getMeta(node node) int {
// Read meta data of this node:
meta := node.metaData
// 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() {
data, err := readLines("input")
if err != nil {
panic(err)
}
nodeString := strings.Split(data[0], " ")

root := readNode(&nodeString)

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>)

fun Node.metadataTotal(): 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[0]
val numMetadata = input[1]

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

val metadata = remainder.take(numMetadata)
val node = Node(children, metadata)
return Pair(node, remainder.drop(numMetadata))
}

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

// Part 2

fun Node.metadataComplex(): Int =
if (children.isEmpty())
metadata.sum()
else
metadata.fold(0) { total, i ->
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>) {
val input = parse(File(args[0]).readText())
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):
def __init__(self, n_childs, n_metadata):
self.n_childs = n_childs
self.n_metadata = n_metadata
self.childs = []
self.metadata = []

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

stack = []
for _ in range(root.n_metadata):
stack.append(("metadata", root))
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_metadata):
stack.append(("metadata", new_node))
for _ in range(new_node.n_childs):
stack.append(("childs", new_node))
else:
current.metadata.append(next(it))
``````

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:
return sum(n.metadata)
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->[1];
\$pos = \$ch->[0];
}
\$sum += sum(0, @n[ \$pos .. \$pos + \$data_size - 1 ]);
\$pos += \$data_size;
return [ \$pos, \$sum ];
}

say process(0, 0)->[1];
``````

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->[1];
\$pos = \$ch->[0];
}

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)->[1];
``````
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
///
/// Build a license tree!

/// A node in a GPS Licensing tree structure
pub struct Node {
metadata: Vec<usize>,
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;
let metadata = data[ptr];
ptr += 1;

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

result.metadata.extend(&data[ptr..(ptr+metadata)]);
ptr += metadata;

(result, ptr)
}

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

## 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;
for pointer in self.metadata.iter() {
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 • Edited on

## JavaScript solution

#### reader.js

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

const readLines = (file, onLine) => {
const reader = readline.createInterface({
input: fs.createReadStream(file),
crlfDelay: Infinity
});

reader.on('line', onLine);

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

const readFile = async file => {
const lines = [];
await readLines(file, line => lines.push(line));
return lines;
}

module.exports = {
readLines,
readFile
};
``````

#### 08-common.js

``````class Node {
constructor(childNodesSize, metadataEntriesSize) {
this.childNodesSize = +childNodesSize;
this.metadataEntriesSize = +metadataEntriesSize;
this.childNodes = [];
this.metadataEntries = [];
}
}

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);
}

node.metadataEntries.push(...input.slice(i, i + node.metadataEntriesSize).map(entry => +entry));
i += node.metadataEntriesSize;
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);
}
return total;
};

(async () => {
const lines = await readFile('08-input.txt');

const tree = buildTree(lines[0].split(' '));

const sum = sumMetadata(tree);

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 lines = await readFile('08-input.txt');

const tree = buildTree(lines[0].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]
let metadata = data[index+1]
let totalMetadata = 0
while(children > 0) {
const childData = addNode(index+2)
index = childData.newIndex
totalMetadata += childData.totalMetadata
children--
}
for(let i = 0; i < metadata ; i++) {
totalMetadata += data[index + i + 2]
}
return {newIndex: index + metadata, totalMetadata}
}

console.log(addNode(0).totalMetadata)
``````

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]
let metadata = data[index+1]
let totalMetadata = 0
let childrenMetadata = []
if(children > 0) {
for(let i = 0; i < children; i++) {
const childData = addNode(index+2)
index = childData.newIndex
childrenMetadata[i] = childData.totalMetadata
}
for(let i = 0; i < metadata ; i++) {
const childMetadataToGet = data[index + i + 2] - 1
totalMetadata += (childrenMetadata[childMetadataToGet]||0)
}
} else {
for(let i = 0; i < metadata ; i++) {
totalMetadata += data[index + i + 2]
}
}
return {newIndex: index + metadata, totalMetadata, childrenMetadata}
}

console.log(addNode(0).totalMetadata)
``````

github.com/ngleich/adventofcode2018/

Mustafa Haddara

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))
num_metadata = parse(Int, popfirst!(nums))
total = 0
for i in 1:num_children
total += total_for_node(nums)
end
for i in 1:num_metadata
meta = parse(Int, popfirst!(nums))
total += meta
end
return total
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)[1]

return result
end

function total_for_node(nums)
num_children = parse(Int, popfirst!(nums))
num_metadata = 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
for i in 1:num_metadata
meta = parse(Int, popfirst!(nums))
total += meta
end
else
for i in 1:num_metadata
meta = parse(Int, popfirst!(nums))
if meta <= length(all_childs)
total += all_childs[meta]
end
end
end
return [total]
end
``````