## DEV Community is a community of 553,512 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Advent of Code 2018 Day 7: The Sum of Its Parts Ben Steadman Updated on ・4 min read

This post originally appeared on steadbytes.com
Complete solution can be found on GitHub

## Part One

Given a puzzle input containing a set of instructions for building Santa's sleigh, we are asked to determine the order in which the steps in the instructions should be completed.

Each instruction defines an order dependency between a pair of steps:

``````Step C must be finished before step A can begin.
``````

Important rules:

• A step is available if all it's pre-requisite steps have been completed
• If there are multiple available steps, they are completed in alphabetical order

Overall algorithm:

1. Extract pairs of steps from puzzle input to obtain a list of step dependencies
2. While there are uncompleted steps:
• Find the next available step from the list of step dependencies
• Remove step from uncompleted set
• Append step to a list of completed steps
• Remove all step dependencies which require the completed step
3. Return list of completed steps

### Parsing Input

To extract pairs of steps from a line of puzzle input I will use a trusty regular expression:

``````>>> import re
>>> line = "Step C must be finished before step A can begin."
>>> re.findall(r"step (\w)", line, re.IGNORECASE)
['C', 'A']
``````

The `re.IGNORECASE` flag is important in order to match `Step X` and `step Y`.

Parsing the entire puzzle input into a list of step dependencies, where the first step in each pair is a pre-requisite of the second:

``````import re

with open("input.txt") as f:
prereq_step_pairs = [re.findall(r"step (\w) ", l, re.IGNORECASE) for l in f]
``````

This can then be used to obtain the set of all steps:

``````steps = {s for steps in prereq_step_pairs for s in steps}
``````

### Finding the Next Available Step

A step is available if all of its pre-requisite steps have been completed. Given a set (`steps`) and a list of remaining step dependencies (`prereq_step_pairs`), available steps can be found by filtering the set of steps to those which do not have any pre-requisites in `prereq_step_pairs`. These must then be completed in alphabetical order, so the next available step is the first element in the returned list:

``````def find_next_steps(steps, prereq_step_pairs):
next_steps = sorted(
[step for step in steps if all(s != step for prereq, s in prereq_step_pairs)]
)
return next_steps
``````

### Main Algorithm

The rest of the algorithm can now be implemented:

``````step_order = []
while steps:
next_step = find_next_steps(steps, prereq_step_pairs)
step_order.append(next_step)
steps.remove(next_step)
# remove dependencies fulfilled by completing the step
prereq_step_pairs = [
(prereq, s) for (prereq, s) in prereq_step_pairs if prereq != next_step
]

``````

For my puzzle input, the answer is GRTAHKLQVYWXMUBCZPIJFEDNSO.

## Part Two

As is so often the case, we must contend with the reality that is time. Furthermore, elven multi-processing is thrown into the mix! We are asked to find how long it will take to complete all the steps, given 5 elves working simultaneously and a duration for each step.

In typical Advent of Code fashion, this problem presents itself well to a simulation:

2. While uncompleted steps remain and some elves are still working:
• For each worker:
• Decrement the remaining time of their current task
• If the task is now complete:
• Remove all step dependencies which require the completed step
• Set the worker to idle
• Find the next available step
• Calculate the duration of the next available step
• Assign the step to the worker
• Remove step from set of steps to be completed
• Increment time step

### Calculating Step Duration

The puzzle states that each step takes 60 seconds plus an amount corresponding to its letter (position in the alphabet). To determine the zero-indexed position of a letter in the alphabet, the value of it's unicode code point is subtracted from that of the letter "A". This works because the code points increase by 1 for each letter of the alphabet:

``````>>> ord("A")
65
>>> ord("B")
66
...
>>> ord("B") - ord("A")
1
``````

The duration of a step can then be calculated:

``````def calculate_step_time(s):
return (ord(s) - ord("A") + 1) + 60
``````
• Note the `+ 1` as the letter values in the question are 1-indexed

### Workers

Each worker is a dictionary of their current step and the time remaining for the step to be completed:

``````workers = [{"step": None, "time": 0} for _ in range(5)]
``````

### Main Algorithm

Obtaining the step dependencies and set of all steps is the same as part 1. Then, the simulation begins at time `-1` and the answer is the value of time after the simulation (`while` loop) is complete:

``````time = -1
workers = [{"step": None, "time": 0} for _ in range(5)]
while steps or any(w["time"] > 0 for w in workers):
for w in workers:
# decrement remaining time of current task
w["time"] = max(w["time"] - 1, 0)

if w["time"] == 0:
if w["step"] is not None:
# remove all step dependencies which require the completed step
prereq_step_pairs = [
(prereq, s)
for (prereq, s) in prereq_step_pairs
if prereq != w["step"]
]
# set worker to idle
w["step"] = None
next_steps = find_next_steps(steps, prereq_step_pairs)
if next_steps:
# get next step and assign to worker
step = next_steps.pop()
w["time"] = calculate_step_time(step)
w["step"] = step
steps.remove(step)
# move along the wheel of time
time += 1
``````

For my puzzle input, the result is 1115.

## Discussion 