https://adventofcode.com/2018/day/7

Advent7-dependencies.js

var parseLine = /Step (\w) must be finished before step (\w) can begin./;

function groupBy(col, key, data) {
  if (!col[key]) col[key] = [];
  col[key].push(data);
}

function noKeyForVal(byAfter) {
  const afterKeys = Object.keys(byAfter).sort();
  const afterVals = afterKeys.reduce((col, k) => {
    return col.concat(byAfter[k]);
  }, []);
  const afterValsUnique = [...new Set(afterVals)].sort();
  afterKeys;
  afterValsUnique;
  const result = afterValsUnique.filter(u => afterKeys.indexOf(u) === -1);
  return result.sort();
}

function removeDep(byAfter, step) {
  Object.keys(byAfter).forEach(k => {
    const vals = byAfter[k];
    const i = vals.indexOf(step);
    if (i > -1) {
      vals.splice(i, 1);
    }
    if (!vals.length) {
      delete byAfter[k];
    }
  });
}

function main(input) {
  const lines = input.split("\n").sort();
  const steps = [];
  const aBeforeB = lines.map(l => parseLine.exec(l).slice(1, 3));
  const byAfter = {};
  aBeforeB.forEach(([a, b]) => groupBy(byAfter, b, a));
  const allDepSteps = Object.keys(byAfter).sort();
  let nextSteps = noKeyForVal(byAfter);
  while (nextSteps.length) {
    const nextStep = nextSteps.shift();
    if (steps.indexOf(nextStep) > -1) continue;
    steps.push(nextStep);
    removeDep(byAfter, nextStep);
    nextSteps = noKeyForVal(byAfter).concat(nextSteps); // this is depth-first, swap for breadth first
  }
  allDepSteps.reduce((col, step) => {
    if (steps.indexOf(step) === -1) col.push(step);
    return col;
  }, steps);
  console.log('steps:', steps.join('')); // <<<<<<<<<<<<<<<<<
}

main(`Step O must be finished before step C can begin.
Step Y must be finished before step D can begin.
Step N must be finished before step D can begin.
Step G must be finished before step F can begin.
Step C must be finished before step Z can begin.
Step H must be finished before step K can begin.
Step W must be finished before step T can begin.
Step T must be finished before step F can begin.
Step S must be finished before step I can begin.
Step X must be finished before step B can begin.
Step J must be finished before step A can begin.
Step K must be finished before step D can begin.
Step Z must be finished before step A can begin.
Step A must be finished before step B can begin.
Step L must be finished before step V can begin.
Step F must be finished before step M can begin.
Step B must be finished before step V can begin.
Step M must be finished before step Q can begin.
Step D must be finished before step E can begin.
Step I must be finished before step U can begin.
Step R must be finished before step V can begin.
Step E must be finished before step U can begin.
Step P must be finished before step V can begin.
Step V must be finished before step Q can begin.
Step U must be finished before step Q can begin.
Step P must be finished before step U can begin.
Step O must be finished before step F can begin.
Step T must be finished before step M can begin.
Step I must be finished before step Q can begin.
Step M must be finished before step U can begin.
Step R must be finished before step E can begin.
Step T must be finished before step R can begin.
Step H must be finished before step S can begin.
Step L must be finished before step B can begin.
Step S must be finished before step Q can begin.
Step E must be finished before step Q can begin.
Step B must be finished before step Q can begin.
Step S must be finished before step M can begin.
Step C must be finished before step D can begin.
Step S must be finished before step R can begin.
Step G must be finished before step D can begin.
Step T must be finished before step E can begin.
Step T must be finished before step Q can begin.
Step N must be finished before step I can begin.
Step S must be finished before step P can begin.
Step N must be finished before step J can begin.
Step X must be finished before step L can begin.
Step G must be finished before step K can begin.
Step N must be finished before step E can begin.
Step H must be finished before step D can begin.
Step H must be finished before step P can begin.
Step O must be finished before step A can begin.
Step V must be finished before step U can begin.
Step F must be finished before step D can begin.
Step B must be finished before step P can begin.
Step T must be finished before step L can begin.
Step I must be finished before step P can begin.
Step K must be finished before step Z can begin.
Step G must be finished before step M can begin.
Step F must be finished before step Q can begin.
Step J must be finished before step L can begin.
Step H must be finished before step Q can begin.
Step W must be finished before step R can begin.
Step R must be finished before step U can begin.
Step P must be finished before step Q can begin.
Step D must be finished before step V can begin.
Step G must be finished before step C can begin.
Step Z must be finished before step B can begin.
Step O must be finished before step H can begin.
Step S must be finished before step A can begin.
Step J must be finished before step Q can begin.
Step N must be finished before step F can begin.
Step L must be finished before step R can begin.
Step O must be finished before step R can begin.
Step W must be finished before step M can begin.
Step J must be finished before step F can begin.
Step G must be finished before step W can begin.
Step K must be finished before step U can begin.
Step D must be finished before step U can begin.
Step W must be finished before step I can begin.
Step E must be finished before step V can begin.
Step Y must be finished before step Q can begin.
Step L must be finished before step E can begin.
Step S must be finished before step B can begin.
Step T must be finished before step V can begin.
Step C must be finished before step U can begin.
Step M must be finished before step P can begin.
Step G must be finished before step S can begin.
Step B must be finished before step R can begin.
Step K must be finished before step M can begin.
Step X must be finished before step A can begin.
Step R must be finished before step P can begin.
Step B must be finished before step I can begin.
Step C must be finished before step X can begin.
Step O must be finished before step P can begin.
Step D must be finished before step Q can begin.
Step F must be finished before step B can begin.
Step I must be finished before step R can begin.
Step Y must be finished before step I can begin.
Step M must be finished before step D can begin.
Step F must be finished before step U can begin.`);

part2-very-broken.js

var parseLine = /Step (\w) must be finished before step (\w) can begin./;

function groupBy(col, key, data) {
  if (!col[key]) col[key] = [];
  col[key].push(data);
}

function noKeyForVal(byAfter) {
  const afterKeys = Object.keys(byAfter).sort();
  const afterVals = afterKeys.reduce((col, k) => {
    return col.concat(byAfter[k]);
  }, []);
  const afterValsUnique = [...new Set(afterVals)].sort();
  afterKeys;
  afterValsUnique;
  const result = afterValsUnique.filter(u => afterKeys.indexOf(u) === -1);
  return result.sort();
}

function removeDep(byAfter, step) {
  Object.keys(byAfter).forEach(k => {
    const vals = byAfter[k];
    const i = vals.indexOf(step);
    if (i > -1) {
      vals.splice(i, 1);
    }
    if (!vals.length) {
      delete byAfter[k];
    }
  });
}

const byAfter = {};
var workers = [
  { id: 0, step: "", timeLeft: 0 },
  { id: 1, step: "", timeLeft: 0 },
  { id: 2, step: "", timeLeft: 0 },
  { id: 3, step: "", timeLeft: 0 },
  { id: 4, step: "", timeLeft: 0 }
];
var stepsWaiting = [];
var stepsFinished = [];
function getTimeForStep(step) {
  return "ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("").indexOf(step) + 61;
}
function assignNewStepToWorker(wId, step) {
  const time = getTimeForStep(step);
  workers[wId].step = step;
  workers[wId].timeLeft = time;
}
function tickDownTimeLeftGetFinsihedSteps() {
  const finishedSteps = workers.reduce((col, w) => {
    if (w.timeLeft === 1) {
      col.push(w.step);
      w.step = "";
    }
    w.timeLeft = Math.max(w.timeLeft - 1, 0);
    return col;
  }, []);
  finishSteps(finishedSteps);
  scheduleWorkerForSteps();
}
function findIdleWorkerIds() {
  return workers.filter(w => w.timeLeft === 0).map(w => w.id);
}
function finishSteps(finishedSteps) { // RangeError: Maximum call stack size exceeded
  finishedSteps.forEach(fstep => {
    stepsFinished.push(fstep);
    removeDep(byAfter, fstep);
    addSteps(byAfter);
  });
}
function scheduleWorkerForSteps() {
  stepsWaiting.every(step => {
    while (!findIdleWorkerIds().length) {
      tickDownTimeLeftGetFinsihedSteps();
    }
    const wId = findIdleWorkerIds()[0];
    assignNewStepToWorker(wId, step);
  });
}
function addSteps() {
  const steps = noKeyForVal(byAfter);
  stepsWaiting = stepsWaiting.concat(steps);
  scheduleWorkerForSteps(byAfter);
}

function main2(input) {
  const lines = input.split("\n").sort();
  const steps = [];
  const aBeforeB = lines.map(l => parseLine.exec(l).slice(1, 3));
  aBeforeB.forEach(([a, b]) => groupBy(byAfter, b, a));
  const allDepSteps = Object.keys(byAfter).sort();
  addSteps();

  while (findIdleWorkerIds().length < 5) {
    addSteps(); // ???????
  }
  stepsFinished.join(""); // <<<<<<<<<<<<<<<<<
}

main2(`Step C must be finished before step A can begin.
Step C must be finished before step F can begin.
Step A must be finished before step B can begin.
Step A must be finished before step D can begin.
Step B must be finished before step E can begin.
Step D must be finished before step E can begin.
Step F must be finished before step E can begin.`);