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
- Feels like pathfinding, but doable!
- Practice round 1: sorted permutations of the example input
- Practice round 2: listing each step's dependencies
- Attempting to codify my algorithm from Practice round 2
- Hurdles I encountered along the way
- 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:
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 theif
- 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
- Should I stay or should I go?
- 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!
Top comments (0)