Skip to content

Instantly share code, notes, and snippets.

@aglee
Created December 7, 2018 21:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aglee/94ca6395c531077988523be94dba1c69 to your computer and use it in GitHub Desktop.
Save aglee/94ca6395c531077988523be94dba1c69 to your computer and use it in GitHub Desktop.
Advent of Code Day 07
import Foundation
let USING_TEST_INPUT = false
let commandURL = URL(fileURLWithPath: CommandLine.arguments[0])
let inputFileName = USING_TEST_INPUT ? "test.txt" : "input.txt"
let inputFileURL = commandURL.deletingLastPathComponent().appendingPathComponent(inputFileName)
let inputText = try! String(contentsOf: inputFileURL, encoding: .utf8).trimmingCharacters(in: .whitespacesAndNewlines)
let inputLines = inputText.split(separator: "\n")
// MARK: - Data structures for the directed graph of steps.
// Node in the graph. I'm using parent/child terminology to indicate the
// direction of arcs in the graph.
class Step {
let name: String
var childStepNames = Set<String>()
var parentStepNames = Set<String>()
// Only used by solve2(). Is ignored by solve1().
var duration: Int {
let baseTime = USING_TEST_INPUT ? 0 : 60
return Int(UnicodeScalar(name)!.value) - Int(UnicodeScalar("A")!.value) + 1 + baseTime
}
// Only used by solve2(). Is always false for solve1().
var isInProgress = false
init(_ name: String) {
self.name = name
}
}
// Each parent-child arc in the graph corresponds to a rule that we got in the
// input stating that the parent must finish before the child can begin.
class StepGraph {
var stepsByName = Dictionary<String, Step>()
init() {
// Populate the graph using the input data.
for line in inputLines {
let line = line as NSString
let parts = line.components(separatedBy: " ")
let (stepName, childStepName) = (parts[1], parts[7])
self.addGraphEdge(parentStepName: stepName, childStepName: childStepName)
}
}
private func getStepByName(_ stepName: String) -> Step {
if let step = stepsByName[stepName] {
return step
} else {
let step = Step(stepName)
stepsByName[stepName] = step
return step
}
}
func addGraphEdge(parentStepName: String, childStepName: String) {
let step = getStepByName(parentStepName)
let childStep = getStepByName(childStepName)
step.childStepNames.insert(childStepName)
childStep.parentStepNames.insert(parentStepName)
}
// Find the step with the alphabetically lowest name that has no parent steps
// and is not already in progress.
func nextRootStep() -> Step? {
for stepName in stepsByName.keys.sorted() {
if let step = stepsByName[stepName] {
if step.parentStepNames.count == 0 && !step.isInProgress {
return step
}
}
}
return nil
}
// Remove the given step from the graph. It must be a root step.
func popRootStep(_ rootStep: Step) {
if rootStep.parentStepNames.count > 0 {
fatalError("Trying to pop step \(rootStep.name) which is not a root step")
}
for childStepName in rootStep.childStepNames {
getStepByName(childStepName).parentStepNames.remove(rootStep.name)
}
stepsByName[rootStep.name] = nil
}
}
// MARK: - Part 1 stuff
func solve1() {
let stepGraph = StepGraph()
// Keep popping root steps from the graph until the graph is empty.
var answer = ""
while let rootStep = stepGraph.nextRootStep() {
stepGraph.popRootStep(rootStep)
answer += rootStep.name
}
print(answer)
}
solve1()
// MARK: - Part 2 stuff
class Worker {
var stepInProgress: Step?
var secondsRemaining = 0
}
class Part2 {
let stepGraph = StepGraph()
var workers: [Worker]
var allWorkersAreIdle: Bool {
for w in workers {
if w.stepInProgress != nil {
return false
}
}
return true
}
init() {
let numWorkers = USING_TEST_INPUT ? 2 : 5
self.workers = (0..<numWorkers).map { _ in Worker() }
}
func assignWorkToWorkers() {
for w in workers {
if w.stepInProgress == nil {
if let step = stepGraph.nextRootStep() {
w.stepInProgress = step
w.secondsRemaining = step.duration
step.isInProgress = true
}
}
}
}
func solve() {
// Initialize workers with work.
assignWorkToWorkers()
// Iterate through as many 1-second ticks of the clock as necessary
// until all workers have become idle because there is no work left
// AND they have all completed the work assigned to them.
var tickCount = 0
while !allWorkersAreIdle {
tickCount += 1
// Decrement secondsRemaining for all active workers.
for w in workers {
if let workerStep = w.stepInProgress {
w.secondsRemaining -= 1
if w.secondsRemaining == 0 {
// This worker has completed the step, so the step can
// now be popped from the graph.
//print(workerStep.name)
stepGraph.popRootStep(workerStep)
w.stepInProgress = nil
}
}
}
// Assign work (if possible) to newly idle workers.
assignWorkToWorkers()
}
print(tickCount)
}
}
func solve2() {
let part2 = Part2()
part2.solve()
}
solve2()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment