# 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:

- Extract pairs of steps from puzzle input to obtain a list of step dependencies
- 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

- 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)[0]
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
]
answer = "".join(step_order)
```

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*:

- Start with a set of 5 elf workers (not assigned to any tasks)
- 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

- For each worker:

### 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)
# current task complete
if w["time"] == 0:
# task is assigned
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**.