Advent of Code 2018: Day 7
data = input.split('\n').map(l => l.slice(1).match(/[A-Z]/g))
nodes = new Set(data.flat())
dependencies = { let dependencies = {}; for (let [before, then] of data) { if (dependencies[then]) { dependencies[then].add(before); } else { dependencies[then] = new Set(before); } } return dependencies; }
Part 1 In what order should the steps in your instructions be completed?
function isSubset (a, b) { if (!a && b) { return true; } return [...a].every(member => b.has(member)); }
instructionOrder = { let out = []; let unvisitedNodes = new Set(nodes); while (unvisitedNodes.size) { // Find nodes whose dependencies have all been visited // From those, pick the one whose value comes earliest in the alphabet const nextNode = [...unvisitedNodes].filter( n => isSubset(dependencies[n], new Set(out))).reduce((a, b) => a < b ? a : b); out.push(nextNode); unvisitedNodes.delete(nextNode); } return out.join(''); }
Part 2 With 5 workers and the 60+ second step durations described above, how long will it take to complete all of the steps?
numWorkers = 5
taskTimeFloor = 60
timeElapsed = { let completedTasks = []; let secondsElapsed = 0; let timers = new Array(numWorkers).fill(0); let tasks = new Array(numWorkers).fill(''); let remainingTasks = new Set(nodes); while (true) { // Decrement worker timers and unload completed tasks for (let w = 0; w < timers.length; w++) { timers[w] = Math.max(0, timers[w] - 1); if (timers[w] === 0 && tasks[w].length) { completedTasks.push(tasks[w]); tasks[w] = ''; } } // Find available tasks, as before // Sort them in order of increasing time burden let availableTasks = [...remainingTasks].filter( n => isSubset(dependencies[n], new Set(completedTasks))).sort(); // If there's no new work to do and all the workers are idle, return the time elapsed if (availableTasks.length === 0 && timers.every(t => t === 0)) { return secondsElapsed; } // Assign new tasks to idle workers and adjust their timers // Remove those tasks from the list of tasks available to claim for (let w = 0; w < timers.length; w++) { if (availableTasks.length) { if (timers[w] === 0) { tasks[w] = availableTasks.shift(); timers[w] = taskTimeFloor + tasks[w].charCodeAt(0) - 64; remainingTasks.delete(tasks[w]); } } } secondsElapsed++; } }
input = `Step T must be finished before step C can begin. Step V must be finished before step C can begin. Step Y must be finished before step H can begin. Step R must be finished before step U can begin. Step B must be finished before step J can begin. Step Q must be finished before step O can begin. Step W must be finished before step O can begin. Step S must be finished before step X can begin. Step I must be finished before step N can begin. Step X must be finished before step H can begin. Step M must be finished before step L can begin. Step A must be finished before step F can begin. Step G must be finished before step P can begin. Step U must be finished before step E can begin. Step Z must be finished before step E can begin. Step H must be finished before step L can begin. Step P must be finished before step C can begin. Step K must be finished before step F can begin. Step O must be finished before step C can begin. Step C must be finished before step F can begin. Step D must be finished before step L can begin. Step L must be finished before step F can begin. Step N must be finished before step E can begin. Step J must be finished before step F can begin. Step F must be finished before step E can begin. Step I must be finished before step A can begin. Step Z must be finished before step J can begin. Step I must be finished before step P can begin. Step T must be finished before step E can begin. Step R must be finished before step F can begin. Step U must be finished before step H can begin. Step K must be finished before step E can begin. Step D must be finished before step N can begin. Step U must be finished before step C can begin. Step D must be finished before step J can begin. Step N must be finished before step F can begin. Step C must be finished before step J can begin. Step U must be finished before step J can begin. Step A must be finished before step O can begin. Step H must be finished before step N can begin. Step P must be finished before step O can begin. Step I must be finished before step E can begin. Step G must be finished before step F can begin. Step O must be finished before step J can begin. Step Q must be finished before step F can begin. Step G must be finished before step J can begin. Step X must be finished before step E can begin. Step S must be finished before step D can begin. Step R must be finished before step P can begin. Step K must be finished before step L can begin. Step R must be finished before step Q can begin. Step L must be finished before step N can begin. Step Q must be finished before step C can begin. Step C must be finished before step D can begin. Step C must be finished before step N can begin. Step O must be finished before step E can begin. Step W must be finished before step F can begin. Step K must be finished before step D can begin. Step T must be finished before step H can begin. Step M must be finished before step D can begin. Step Y must be finished before step Z can begin. Step J must be finished before step E can begin. Step S must be finished before step F can begin. Step G must be finished before step U can begin. Step V must be finished before step S can begin. Step Y must be finished before step F can begin. Step G must be finished before step H can begin. Step T must be finished before step Q can begin. Step S must be finished before step U can begin. Step V must be finished before step D can begin. Step W must be finished before step M can begin. Step M must be finished before step E can begin. Step A must be finished before step H can begin. Step B must be finished before step F can begin. Step B must be finished before step N can begin. Step D must be finished before step F can begin. Step W must be finished before step K can begin. Step P must be finished before step E can begin. Step B must be finished before step X can begin. Step Q must be finished before step U can begin. Step Q must be finished before step X can begin. Step X must be finished before step N can begin. Step M must be finished before step Z can begin. Step G must be finished before step Z can begin. Step S must be finished before step G can begin. Step P must be finished before step F can begin. Step I must be finished before step O can begin. Step R must be finished before step A can begin. Step L must be finished before step J can begin. Step B must be finished before step I can begin. Step C must be finished before step E can begin. Step B must be finished before step W can begin. Step P must be finished before step N can begin. Step H must be finished before step C can begin. Step K must be finished before step J can begin. Step Y must be finished before step M can begin. Step Z must be finished before step P can begin. Step I must be finished before step K can begin. Step V must be finished before step E can begin. Step Y must be finished before step P can begin. Step T must be finished before step R can begin.`