aoc-day07.swift

import Foundation

let input = """
Step X must be finished before step C can begin.
Step C must be finished before step G can begin.
Step F must be finished before step G can begin.
Step U must be finished before step Y can begin.
Step O must be finished before step S can begin.
Step D must be finished before step N can begin.
Step M must be finished before step H can begin.
Step J must be finished before step Q can begin.
Step G must be finished before step R can begin.
Step I must be finished before step N can begin.
Step R must be finished before step K can begin.
Step A must be finished before step Z can begin.
Step Y must be finished before step L can begin.
Step H must be finished before step P can begin.
Step K must be finished before step S can begin.
Step Z must be finished before step P can begin.
Step T must be finished before step S can begin.
Step N must be finished before step P can begin.
Step E must be finished before step S can begin.
Step S must be finished before step W can begin.
Step W must be finished before step V can begin.
Step L must be finished before step V can begin.
Step P must be finished before step B can begin.
Step Q must be finished before step V can begin.
Step B must be finished before step V can begin.
Step P must be finished before step Q can begin.
Step S must be finished before step V can begin.
Step C must be finished before step Q can begin.
Step I must be finished before step H can begin.
Step A must be finished before step E can begin.
Step H must be finished before step Q can begin.
Step G must be finished before step V can begin.
Step N must be finished before step L can begin.
Step R must be finished before step Q can begin.
Step W must be finished before step L can begin.
Step X must be finished before step L can begin.
Step X must be finished before step J can begin.
Step W must be finished before step P can begin.
Step U must be finished before step B can begin.
Step P must be finished before step V can begin.
Step O must be finished before step P can begin.
Step W must be finished before step Q can begin.
Step S must be finished before step Q can begin.
Step U must be finished before step Z can begin.
Step Z must be finished before step T can begin.
Step M must be finished before step T can begin.
Step A must be finished before step P can begin.
Step Z must be finished before step B can begin.
Step N must be finished before step S can begin.
Step H must be finished before step N can begin.
Step J must be finished before step E can begin.
Step M must be finished before step J can begin.
Step R must be finished before step A can begin.
Step A must be finished before step Y can begin.
Step F must be finished before step V can begin.
Step L must be finished before step P can begin.
Step K must be finished before step L can begin.
Step F must be finished before step P can begin.
Step G must be finished before step L can begin.
Step I must be finished before step Q can begin.
Step C must be finished before step L can begin.
Step I must be finished before step Y can begin.
Step G must be finished before step B can begin.
Step H must be finished before step L can begin.
Step X must be finished before step U can begin.
Step I must be finished before step K can begin.
Step R must be finished before step N can begin.
Step I must be finished before step L can begin.
Step M must be finished before step I can begin.
Step K must be finished before step V can begin.
Step G must be finished before step E can begin.
Step F must be finished before step B can begin.
Step O must be finished before step Y can begin.
Step Y must be finished before step Q can begin.
Step F must be finished before step K can begin.
Step N must be finished before step W can begin.
Step O must be finished before step R can begin.
Step N must be finished before step E can begin.
Step M must be finished before step V can begin.
Step H must be finished before step T can begin.
Step Y must be finished before step T can begin.
Step F must be finished before step J can begin.
Step F must be finished before step O can begin.
Step W must be finished before step B can begin.
Step T must be finished before step E can begin.
Step T must be finished before step P can begin.
Step F must be finished before step M can begin.
Step U must be finished before step I can begin.
Step H must be finished before step S can begin.
Step S must be finished before step P can begin.
Step T must be finished before step W can begin.
Step A must be finished before step N can begin.
Step O must be finished before step N can begin.
Step L must be finished before step B can begin.
Step U must be finished before step K can begin.
Step Z must be finished before step W can begin.
Step X must be finished before step D can begin.
Step Z must be finished before step L can begin.
Step I must be finished before step T can begin.
Step O must be finished before step W can begin.
Step I must be finished before step B can begin.
"""

struct Relation {
  let first: String
  let next: String

  init(_ string: String) {
    let components = string.components(separatedBy: .whitespaces)
    first = components[1]
    next = components[7]
  }
}

extension Sequence where Element == Relation {
  func relationMap(keyedBy: KeyPath<Relation, String>, values: KeyPath<Relation, String>) -> [String: Set<String>] {
    return reduce(into: Dictionary<String, Set<String>>()) { relations, relation in
      var next: Set<String> = relations[relation[keyPath: keyedBy], default: []]
      next.insert(relation[keyPath: values])
      relations[relation[keyPath: keyedBy]] = next
    }
  }
}

struct InstructionSet {
  enum Duration {
    case instant
    case variable(Int)

    private static let durationMap: Dictionary<String, Int> = {
      let pairs = Array("ABCDEFGHIJKLMNOPQRSTUVWXYZ").enumerated()
        .map { (String($0.element), $0.offset + 1) }
      return Dictionary(uniqueKeysWithValues: pairs)
    }()
    
    func duration(for instruction: String) -> Int {
      switch self {
        case .instant: 
          return 1
        case .variable(let prefix):
          return prefix + Duration.durationMap[instruction]!
      }
    }
  }
  
  private var ready: Set<String> = []
  private var completed: Set<String> = []
  private var pending: Set<String> = []
  private var inProgress: Dictionary<String, Int> = [:]
  private var instructonOrder: String = ""
  private var isFinished: Bool {
    return ready.count == 0 && pending.count == 0 && inProgress.count == 0
  }
      
  let parentToChild: [String: Set<String>]
  let childToParent: [String: Set<String>]
  
  init(relations: [Relation]) {
    parentToChild = relations.relationMap(keyedBy: \.first, values: \.next)
    childToParent = relations.relationMap(keyedBy: \.next, values: \.first)
    
    startOver()
  }
  
  mutating func startOver() {
    pending = Set(childToParent.keys)
    ready = Set(parentToChild.keys).subtracting(childToParent.keys)
    completed = []
    inProgress = [:]
    instructonOrder = ""
  }
  
  mutating func playToEnd(workerCount: Int, duration: Duration) -> (String, Int) {
    var t = 0
    repeat {
      startInstructions(at: t, workerCount: workerCount)
      t += 1
      finishInstructions(at: t, duration: duration)
    } while !isFinished
    
    return (instructonOrder, t)
  }
    
  private mutating func startInstructions(at time: Int, workerCount: Int) {
    next(workers: workerCount).forEach {
      instructonOrder.append($0)
      ready.remove($0)
      inProgress[$0] = time
    }
  }
  
  private func next(workers: Int) -> [String] {
    return Array(ready.sorted().prefix(workers - inProgress.count))
  }
  
  private mutating func finishInstructions(at time: Int, duration: Duration) {
    inProgress
      .filter { $0.value + duration.duration(for: $0.key) <= time }
      .forEach { complete($0.key, time: time)}
  }

  private mutating func complete(_ instruction: String, time: Int) {
    inProgress[instruction] = nil
    completed.insert(instruction)

    if let children = parentToChild[instruction] {
      children
        .filter { pending.contains($0)}
        .forEach { child in
          if let parents = childToParent[child], parents.allSatisfy({ completed.contains($0) }) {
            ready.insert(child)
            pending.remove(child)
          }
      }
    }
  }  
}

let relations = input.components(separatedBy: .newlines).map(Relation.init)
var instructionSet = InstructionSet(relations: relations)
print("part1: \(instructionSet.playToEnd(workerCount: 1, duration: .instant))")
instructionSet.startOver()
print("part2: \(instructionSet.playToEnd(workerCount: 5, duration: .variable(60)))")