2018 Advent of Code, Day 7

day07.js

const smallInput = ["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."]
const input = ['Step F must be finished before step Q can begin.', 'Step A must be finished before step K can begin.', 'Step K must be finished before step R can begin.', 'Step D must be finished before step X can begin.', 'Step L must be finished before step T can begin.', 'Step V must be finished before step W can begin.', 'Step J must be finished before step N can begin.', 'Step B must be finished before step W can begin.', 'Step X must be finished before step C can begin.', 'Step W must be finished before step I can begin.', 'Step Q must be finished before step P can begin.', 'Step E must be finished before step M can begin.', 'Step C must be finished before step N can begin.', 'Step U must be finished before step O can begin.', 'Step O must be finished before step R can begin.', 'Step N must be finished before step Z can begin.', 'Step R must be finished before step I can begin.', 'Step G must be finished before step H can begin.', 'Step T must be finished before step H can begin.', 'Step M must be finished before step P can begin.', 'Step Y must be finished before step I can begin.', 'Step S must be finished before step Z can begin.', 'Step I must be finished before step H can begin.', 'Step H must be finished before step P can begin.', 'Step P must be finished before step Z can begin.', 'Step Y must be finished before step P can begin.', 'Step A must be finished before step O can begin.', 'Step V must be finished before step O can begin.', 'Step G must be finished before step Y can begin.', 'Step K must be finished before step B can begin.', 'Step I must be finished before step P can begin.', 'Step D must be finished before step L can begin.', 'Step A must be finished before step P can begin.', 'Step O must be finished before step T can begin.', 'Step F must be finished before step C can begin.', 'Step M must be finished before step S can begin.', 'Step V must be finished before step Q can begin.', 'Step G must be finished before step I can begin.', 'Step O must be finished before step I can begin.', 'Step N must be finished before step I can begin.', 'Step E must be finished before step O can begin.', 'Step N must be finished before step S can begin.', 'Step J must be finished before step H can begin.', 'Step C must be finished before step P can begin.', 'Step E must be finished before step N can begin.', 'Step T must be finished before step P can begin.', 'Step A must be finished before step G can begin.', 'Step A must be finished before step V can begin.', 'Step C must be finished before step H can begin.', 'Step A must be finished before step Y can begin.', 'Step E must be finished before step U can begin.', 'Step T must be finished before step Y can begin.', 'Step Q must be finished before step S can begin.', 'Step Y must be finished before step S can begin.', 'Step E must be finished before step P can begin.', 'Step N must be finished before step T can begin.', 'Step T must be finished before step M can begin.', 'Step Q must be finished before step M can begin.', 'Step H must be finished before step Z can begin.', 'Step D must be finished before step Y can begin.', 'Step J must be finished before step R can begin.', 'Step U must be finished before step R can begin.', 'Step K must be finished before step N can begin.', 'Step A must be finished before step W can begin.', 'Step A must be finished before step H can begin.', 'Step X must be finished before step G can begin.', 'Step V must be finished before step J can begin.', 'Step W must be finished before step C can begin.', 'Step I must be finished before step Z can begin.', 'Step V must be finished before step H can begin.', 'Step R must be finished before step H can begin.', 'Step U must be finished before step N can begin.', 'Step O must be finished before step Z can begin.', 'Step X must be finished before step S can begin.', 'Step E must be finished before step G can begin.', 'Step W must be finished before step U can begin.', 'Step U must be finished before step G can begin.', 'Step D must be finished before step Z can begin.', 'Step E must be finished before step R can begin.', 'Step L must be finished before step B can begin.', 'Step B must be finished before step R can begin.', 'Step G must be finished before step T can begin.', 'Step F must be finished before step K can begin.', 'Step R must be finished before step S can begin.', 'Step J must be finished before step Z can begin.', 'Step Q must be finished before step U can begin.', 'Step X must be finished before step O can begin.', 'Step F must be finished before step I can begin.', 'Step W must be finished before step R can begin.', 'Step W must be finished before step Y can begin.', 'Step M must be finished before step Y can begin.', 'Step S must be finished before step I can begin.', 'Step F must be finished before step O can begin.', 'Step C must be finished before step Y can begin.', 'Step N must be finished before step G can begin.', 'Step O must be finished before step S can begin.', 'Step Q must be finished before step O can begin.', 'Step K must be finished before step T can begin.', 'Step X must be finished before step Z can begin.', 'Step L must be finished before step N can begin.', 'Step S must be finished before step P can begin.']

const parseStep = step => 
  step .match (/Step (.) must be finished before step (.) can begin./) .slice (1)

const firstFreeNode = (edges, nodes) => 
  head (reject
    ( flip (contains) (map (last, edges))
    , nodes
    ))  // note: nodes remain sorted, so `head` is fine here.

const removeEdgesFrom = (node, edges) => reject(([from]) => from === node, edges)

const partialOrder = (edges, nodes, order = [], node = firstFreeNode (edges, nodes)) => 
  edges .length == 0 
    ? order .concat (nodes)
    : partialOrder
      ( removeEdgesFrom (node, edges)
      , without (node, nodes)
      , append (node, order)
      )

const puzzle7a = (input, edges = map (parseStep, input)) => 
  join
    ( '' 
    , partialOrder
      ( edges
      , sortBy (identity, uniq (flatten (edges)))
      )
    )

puzzle7a(smallInput) //=> "CABDFE"
puzzle7a(input) //=> "ADEFKLBVJQWUXCNGORTMYSIHPZ"