The Sum of Its Parts

Advent of Code 2018 Day 7

Task: Solve for X where...

Part 1

X = the order the steps in my instructions should be completed

Part 2

X = the number of seconds it takes to complete all of the steps using the rules provided

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

It represents:

• Instructions for assembling a Sleigh kit
• A series of steps labeled A-Z
• Requirements about which steps must be finished before others can begin

Part 1

1. Feels like pathfinding, but doable!
2. Practice round 1: sorted permutations of the example input
3. Practice round 2: listing each step's dependencies
4. Attempting to codify my algorithm from Practice round 2
5. Hurdles I encountered along the way
6. Testing the results

Feels like pathfinding, but doable!

• Since it is instructions, it is an ordered list
• I must determine the order
• Thankfully, the use of only alphabetical characters means the list is 26 items long
• Also thankfully, my puzzle input is 100 steps long

In other words:

• I shall first attempt this puzzle manually
• Hopefully I'll find the correct answer
• If I do, maybe I'll identify a way to do it algorithmically, too

This won't be the first time I attempt to solve a puzzle manually:

• 2021 Day 23: Amphipod
• 2020 Day 17: Set and Forget
• 2020 Day 15: Oxygen System

Practice round 1: sorted permutations of the example 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.

The steps referenced in order of appearance are:

CAFBDE

That tells me:

• There are six steps
• Steps are labeled A-F
• No letters are skipped

And the rule I must keep in mind:

If more than one step is ready, choose the step which is first alphabetically

What if I treated this like an unsorted array?

That was a fun exercise.

But would make for a terrible, unreliable algorithm.

Practice round 2: listing each step's dependencies

Well, that process definitely feels more easily codified.

Attempting to codify my algorithm from Practice round 2

From my puzzle input
  Generate a Dictionary that stores 
    Keys for all characters referenced among the steps
    Values storing arrays filled with any dependencies referenced among the steps
Create an array to store the ordered list of steps
Create a unique set of values, nextSteps, to store the list of potential next steps at any given moment
Do until the number of items in steps equals the number of keys in the dictionary
  For each key in the dictionary
    Add the key to nextSteps - unless it would be a duplicate - only if both of the following are true:
      1. Every element in this rule's list of dependencies matches some element in steps
      2. This rule is not yet in steps
  Generate an array from nextSteps
    Sort the array alphabetically
      Add the first element to steps
  Delete the element just added to steps from nextSteps
Return the string concatenation of the ordered values now in steps

Hurdles I encountered along the way

Add them all, or one at a time?

• My puzzle input had three letters with no dependencies
• I thought I could just add those letters as the first three steps
• But I noticed that some letters had only the first of those three letters as a dependency
• This meant I could only add one of the three to the list, then I had to run the check again

What condition correctly catches the next possible steps?

• Initially I had an if...else to account for the empty arrays of the dependency-less letters and the rest
• Thankfully, the condition inside the else was written well enough to work in the if
• So, my code is now simplified: it catches rules that are not already in the ordered list and whose arrays are either identical to, or contain a subset of the values in steps (including empty arrays)

Set or Array?

• Initially I had nextSteps as an array
• But I quickly realized I was re-adding rules
• And those rules were being re-added to steps
• Instead, I made nextSteps a Set and made sure to account for it when sorting in each step, and again when removing the newly-added rule

Testing the results

• It worked on the example input
• It worked on my puzzle input!

I'm shocked!

• I didn't have to attempt solving this puzzle manually!
• My algorithm generated the correct answer!
• My algorithm is under 30 lines of code!

Part 2

1. Should I stay or should I go?
2. Manually attempting to solve, slide by slide

Should I stay or should I go?

• Solving this part seems doable, too
• Like earlier - probably not with a codified algorithm
• Rather, manually. Probably by creating a GIF that shows most of the steps
• That's going to be a big ordeal, since there will likely be well over 60 * 26 frames!

I am interested in drawing the first few steps to confirm my understanding.

Then, if I feel like it, I'll make the rest of the frames.

Manually attempting to solve, slide by slide

• I decided not to draw each second
• Just the seconds where one step finished and one or more others started

The full walkthrough is depicted in this animation:

The big question is: is 1164 my correct answer (Y/N)?

No. Too high.

Bummer!

But...1160 is too low.

So, the answer must be one of:

• 1161
• 1162
• 1163

Was I off by one?

Trying again after one minute...

Yup! 1163 was my correct answer!

I did it!!

• I solved Part 1 algorithmically!
• I solved Part 2 manually!
• I made several GIFs that described my approaches to solving this puzzle
• I seriously impressed myself!

Wow! What a delightfully rewarding sense of accomplishment!