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

Comments

[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]

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/