AoC Day 8: Memory Maneuver

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

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

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

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

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

}

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

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

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

print(tree_sum(root))

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

#!/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];

#!/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];

/// 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
    }
}

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

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

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

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

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

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)

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)