Advent of Code 2018 Day 7: The Sum of Its Parts

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.

• Demo of this regex

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:

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

Resources

• Unicode
• Python ord function