Day 6 of AOC 2018

day6aoc2018.js

var run = src => {

    const input = src.split(/\n/).map(m => m.split(/\)/));

    const node = (id) =>  {
        const o = {
            id,
            parent: null,
            children: []
        }
        return o;
    }

    const nodeLookup = input.reduce((lookup, [par, chi]) => {
        if (!lookup[par]) {
            lookup[par] = node(par);
        }
        if (!lookup[chi]) {
            lookup[chi] = node(chi);
        }
        let parNode = lookup[par];
        let chiNode = lookup[chi];

        if (parNode.children.indexOf(chiNode) === -1) {
            parNode.children.push(chiNode);
        }
        chiNode.parent = parNode;
        if (parNode.parent === null) {
            Object.values(lookup).forEach(node => {
                if (node.children.indexOf(parNode) !== -1) {
                    parNode.parent = node;
                }
            });
        }
        return lookup;
    }, {});


    // start 1 - just count orbits...
    //const count = Object.values(nodeLookup).reduce((sum, node) => {
    //  let count = 0;
    //  while(node.parent){
    //    node = node.parent;
    //    count++;
    //  }
    //  return sum + count;
    //}, 0)

    //return count;

    // starting with the start node,
    // do a bfs
    const findPath = () => {
      const q = [nodeLookup['YOU']];
      nodeLookup['YOU'].c = 0;
      let i = 0;
      let start = null;
      let dest = null;
      while (q[i] && !window.done && !dest) {
        let {c, children, parent } = q[i];
        c++;
        if (parent) {
            if (!parent.c && parent.c !== 0) {
                parent.c = c;
            }

            if (parent.id === 'SAN') {
                dest = parent;
                dest.c = c;
            }
            if (q.indexOf(parent) === -1){
                q.push(parent);
            }
        }
        for (let j = 0; j < children.length; j++) {
            if (!children[j].c && children[j].c !== 0) {
               children[j].c = c; 
            }
            if (children[j].id === 'SAN') {
                dest = children[j];
                break;
            }
            if (q.indexOf(children[j]) === -1) {
                q.push(children[j]);
            }
        }
        i++;
      }
      return dest;
    }

    // with the graph annotated with scores
    // follow the cheapest path until we find 
    // the target..
    const start = findPath();
    let path = [start];
    let current = start;
    let next;
    while(!window.done && current.c !== 0){
      const c = current.c;
      if (current.parent){
        next = current.parent;
      } else {
        next = current.children[0];
      }
      // find a better match if there is one...
      for (let i = 0; i < current.children.length; i++) {
          if (current.children[i].c < next.c) {
              next = current.children[i];
          }
      }
      current = next;
      path.push(current);
    }

    return path.length - 3;

}