2018-12-07 - The Sum of Its Parts
(original .ipynb)
test_input = [
"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."
]
real_input = [
"Step L must be finished before step A can begin.",
"Step P must be finished before step F can begin.",
"Step V must be finished before step U can begin.",
"Step F must be finished before step S can begin.",
"Step A must be finished before step J can begin.",
"Step R must be finished before step K can begin.",
"Step Z must be finished before step T can begin.",
"Step G must be finished before step W can begin.",
"Step H must be finished before step K can begin.",
"Step T must be finished before step U can begin.",
"Step K must be finished before step B can begin.",
"Step C must be finished before step Y can begin.",
"Step W must be finished before step N can begin.",
"Step E must be finished before step M can begin.",
"Step N must be finished before step J can begin.",
"Step B must be finished before step S can begin.",
"Step O must be finished before step D can begin.",
"Step X must be finished before step D can begin.",
"Step M must be finished before step Q can begin.",
"Step S must be finished before step J can begin.",
"Step U must be finished before step Y can begin.",
"Step I must be finished before step J can begin.",
"Step D must be finished before step J can begin.",
"Step Q must be finished before step Y can begin.",
"Step J must be finished before step Y can begin.",
"Step Z must be finished before step D can begin.",
"Step K must be finished before step E can begin.",
"Step U must be finished before step J can begin.",
"Step I must be finished before step Y can begin.",
"Step A must be finished before step B can begin.",
"Step B must be finished before step Q can begin.",
"Step Z must be finished before step S can begin.",
"Step F must be finished before step E can begin.",
"Step B must be finished before step I can begin.",
"Step C must be finished before step S can begin.",
"Step O must be finished before step S can begin.",
"Step V must be finished before step O can begin.",
"Step C must be finished before step B can begin.",
"Step G must be finished before step M can begin.",
"Step O must be finished before step Y can begin.",
"Step H must be finished before step N can begin.",
"Step D must be finished before step Y can begin.",
"Step Z must be finished before step O can begin.",
"Step K must be finished before step W can begin.",
"Step M must be finished before step Y can begin.",
"Step O must be finished before step J can begin.",
"Step P must be finished before step E can begin.",
"Step C must be finished before step Q can begin.",
"Step I must be finished before step D can begin.",
"Step F must be finished before step I can begin.",
"Step W must be finished before step B can begin.",
"Step W must be finished before step M can begin.",
"Step N must be finished before step D can begin.",
"Step Z must be finished before step M can begin.",
"Step M must be finished before step U can begin.",
"Step R must be finished before step I can begin.",
"Step S must be finished before step Y can begin.",
"Step L must be finished before step B can begin.",
"Step S must be finished before step D can begin.",
"Step R must be finished before step G can begin.",
"Step U must be finished before step D can begin.",
"Step C must be finished before step N can begin.",
"Step R must be finished before step T can begin.",
"Step K must be finished before step U can begin.",
"Step W must be finished before step E can begin.",
"Step H must be finished before step E can begin.",
"Step X must be finished before step M can begin.",
"Step G must be finished before step I can begin.",
"Step C must be finished before step U can begin.",
"Step N must be finished before step B can begin.",
"Step X must be finished before step S can begin.",
"Step G must be finished before step H can begin.",
"Step T must be finished before step X can begin.",
"Step P must be finished before step N can begin.",
"Step B must be finished before step Y can begin.",
"Step S must be finished before step Q can begin.",
"Step C must be finished before step E can begin.",
"Step F must be finished before step D can begin.",
"Step H must be finished before step J can begin.",
"Step B must be finished before step U can begin.",
"Step B must be finished before step J can begin.",
"Step P must be finished before step I can begin.",
"Step N must be finished before step X can begin.",
"Step M must be finished before step J can begin.",
"Step X must be finished before step I can begin.",
"Step L must be finished before step P can begin.",
"Step T must be finished before step B can begin.",
"Step T must be finished before step K can begin.",
"Step D must be finished before step Q can begin.",
"Step W must be finished before step X can begin.",
"Step A must be finished before step Y can begin.",
"Step G must be finished before step D can begin.",
"Step R must be finished before step Z can begin.",
"Step U must be finished before step Q can begin.",
"Step G must be finished before step O can begin.",
"Step G must be finished before step Q can begin.",
"Step G must be finished before step Y can begin.",
"Step P must be finished before step Y can begin.",
"Step I must be finished before step Q can begin.",
"Step F must be finished before step C can begin.",
"Step L must be finished before step K can begin."
]
# Part 1
import re
dependencies = {}
all_steps_list = []
solution = []
def parse_step(step_string):
global dependencies
global all_steps_list
parsed = re.search("^Step (\w+) .* step (\w+) .*$", step_string)
assert(len(parsed.groups()) == 2)
parent = parsed.group(1)
child = parsed.group(2)
all_steps_list.append(parent)
all_steps_list.append(child)
if child in dependencies:
dependencies[child].append(parent)
else:
dependencies[child] = [ parent ]
for step in real_input:
parse_step(step)
remaining_steps = set(all_steps_list)
while len(remaining_steps) > 0:
candidate_steps = sorted([ step for step in remaining_steps if (not step in dependencies) or (len(dependencies[step]) == 0)])
step = candidate_steps[0]
solution.append(step)
for child in dependencies:
if step in dependencies[child]:
dependencies[child].remove(step)
if step in dependencies:
del dependencies[step]
remaining_steps.discard(step)
print("".join(solution))
LAPFCRGHVZOTKWENBXIMSUDJQY
# Part 2
dependencies = {}
all_steps_list = []
solution = []
allocated = set()
work_per_step = 60
work_remaining = {}
workers = [ None, None, None, None, None ]
# process the input
for step in real_input:
parse_step(step)
# populate the amount of work remaining
for step in all_steps_list:
work = work_per_step + 1 + ord(step) - ord("A")
work_remaining[step] = work
# the list of steps
remaining_steps = set(all_steps_list)
seconds = 0
while len(remaining_steps) > 0:
# allocate
for worker_id, worker_step in enumerate(workers):
if worker_step is None:
candidate_steps = sorted([ step for step in remaining_steps if not (step in allocated) and ((not step in dependencies) or (len(dependencies[step]) == 0))])
if not candidate_steps:
continue
worker_step = candidate_steps.pop(0)
workers[worker_id] = worker_step
allocated.add(worker_step)
# perform work
for worker_id, worker_step in enumerate(workers):
if not worker_step:
continue
work_remaining[worker_step] -= 1
if work_remaining[worker_step] == 0:
solution.append(worker_step)
for child in dependencies:
if worker_step in dependencies[child]:
dependencies[child].remove(worker_step)
if worker_step in dependencies:
del dependencies[worker_step]
remaining_steps.discard(worker_step)
workers[worker_id] = None
worker_step = None
seconds += 1
print("".join(solution))
print(seconds)
LRVAGPZHFOTCKWENBXIMSUDJQY
936