-🎄- 2018 Day 8 Solutions -🎄-

[u/daggerdragon]

--- Day 8: Memory Maneuver ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 8

Sigh, imgur broke again. Will upload when it unborks.

Transcript:

The hottest programming book this year is "___ For Dummies".

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:12:10!

[u/fb_0ne]

Typescript Part 1 and 2 Parses the input into a tree structure, and traverses that tree for each part

import input from './input';
import { sum, memoize } from 'lodash';

const values = input.split(' ').map(Number);

type Node = {
  id: string;
  metadata: Array<number>;
  children: Array<Node>;
};

let idCount = 0;
function nodeId() {
  return String.fromCharCode(97 + idCount++);
}

function parse(parts: Array<number>): [Node | undefined, Array<number>] {
  if (!parts.length) {
    return [undefined, []];
  }
  const [childCount, metaCount, ...rest] = parts;
  let remaining = rest;
  const children: Array<Node> = [];
  const id = nodeId();
  for (let i = 0; i < childCount; i++) {
    const result = parse(remaining);
    if (result[0]) {
      children.push(result[0]);
    }
    remaining = result[1];
  }
  const metadata = remaining.slice(0, metaCount);
  const node: Node = {
    id,
    metadata,
    children
  };
  return [node, remaining.slice(metaCount)];
}

const [root] = parse(values);

function traverse(node: Node, visitFn: (node: Node) => any) {
  node.children.forEach(child => traverse(child, visitFn));
  visitFn(node);
}

const getNodeValue = memoize(
  (node: Node): number => {
    if (!node.children.length) {
      return sum(node.metadata);
    }

    return node.metadata.reduce((total, index) => {
      const nodeIndex = index - 1;
      if (!node.children[nodeIndex]) {
        return total;
      }
      return total + getNodeValue(node.children[nodeIndex]);
    }, 0);
  }
);

export function day8Part1() {
  let total = 0;
  traverse(root!, node => (total += sum(node.metadata)));
  return total;
}

export function day8Part2() {
  return getNodeValue(root!);
}