Advent of Code Day 07

AoC2018Day07.swift

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()