Advent of Code 2018 Day 7: The Sum of Its Parts
Tags: aoc2018, python, puzzle, challenge
Published: 2019-05-19 05:50:32

---
title: "Advent of Code 2018 Day 7: The Sum of Its Parts"
tags: ["aoc2018", "python", "puzzle", "challenge"]
published: true
categories: ["Advent of Code 2018"]
description: "At least Ikea instructions have diagrams."
---
> This post originally appeared on [steadbytes.com](https://steadbytes.com/blog/advent-of-code-2018/07/)
> Complete solution can be found on [GitHub](https://github.com/SteadBytes/advent-of-code-2018/blob/3ce928637a401a5180a5773c8087c1e884bb6fbf/07/solution.py)

## Part One

Given a [puzzle input](https://github.com/SteadBytes/advent-of-code-2018/blob/4f27d44f7003f04dcccd04b5471b96f19751b1f0/07/input.txt) 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:

```python
>>> 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`.

- [Demo of this regex](https://regex101.com/r/hNe6Qn/1/)

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:

```python
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:

```python
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:

```python
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:

```python
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](https://en.wikipedia.org/wiki/Time). Furthermore, elven [multi-processing](https://en.wikipedia.org/wiki/Multiprocessing) 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_:

1. Start with a set of 5 elf workers (not assigned to any tasks)
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](https://en.wikipedia.org/wiki/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:

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

The duration of a step can then be calculated:

```python
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:

```python
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:

```python
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**.

### Resources

- [Unicode](https://en.wikipedia.org/wiki/Unicode)
- [Python `ord` function](https://docs.python.org/3.6/library/functions.html#ord)