Advent of Code 2018 Day 5
Try the simulator using your puzzle input!
Task: Solve for X where...
Part 1
X = the number of units remaining after fully reacting the polymer I scanned
Part 2
X = the length of the shortest polymer I can produce by removing all units of exactly one type and fully reacting the result
Example input
dabAcCaCBAcCcaDA
It represents:
- A polymer
- Comprised of units of different types and polarities
- Units' types are represented by letters
- Units' polarity is represented by capitalization
Part 1
- Many approaches. What's a smart one?
- Animating my first algorithmic idea
- Writing a working algorithm
- Building the simulator
Many approaches. What's a smart one?
- The examples allude to continually re-processing the input for polar-opposite-same-type letter pairs
- But my puzzle input is thousands of characters long
- I definitely don't want to be re-assigning smaller strings with each pass
- I suppose I could use an array
- And do a lot of splicing...maybe?
Animating my first algorithmic idea
Using this example input:
dabAcCaCBAcCcaDA
I want to:
- Walk the whole string, one character at a time
- Look ahead one character
- If both must be destroyed, step back one character and remove both characters one and two ahead
- If none should be destroyed, step forward one character
Writing a working algorithm
It's slightly different from what's depicted in the animation above.
Start at index -1 and go until the 3rd-to-last value
Check the values at the locations one and two ahead of index
If both values are different, but when uppercased are equal
Remove both from the list of characters
Decrement index by one to move back one character...in case the new character one ahead causes the character at index to become a matching pair
Else, increment index by 1 to move to the next character
Return the length of the list of characters
The results:
- It worked on every sample
- It worked on the example
- It worked on my puzzle input!
It took a few seconds, so I'm very glad I went with this approach instead of thousands of iterations, one for each subsequent removal.
Building the simulator
I was excited to watch the characters continually get removed.
After building it and watching it run, I'm very happy with my decision to make it.
It's like The Matrix, only horizontal!
Try the simulator for Part 1 using your puzzle input!
Part 2
- The same, but with fewer, and a lot more times!
- How my anticipated algorithm will work
- Testing my algorithm. Error!
- Testing my algorithm again. Success!
- Simulator: Update, or not?
The same, but with fewer, and a lot more times!
- I still need to count the characters remaining after reducing my polymer
- But before I do, I need to remove all instances of one unit (both polarities)
- And I need to do that for all unit types
How my anticipated algorithm will work
For each letter (case insensitive)
Replace all matches for that letter in the polymer with nothing (thereby removing all matches)
Reduce the polymer
Return the length of the reduced polymer
Return the smallest length of all the mutated and reduced polymers
Time to write it!
Done!
Time to test it!
Testing my algorithm. Error!
- It worked on the example input!
- It broke on my puzzle input!
- Hmm. Why?
More specifically:
- It broke when processing the letter
K
My puzzle input starts:
KWwBbJ
- My algorithm starts a location at
-1
so it can check the values at position0
and1
When I remove all K/k
s, I get:
WwBbJ
My algorithm does this:
index = -1
check 0 and 1
W w
Match! Remove! Decrement index by 1!
index = -2
check -1 and 0
ERROR!
That's it!
I fixed my algorithm with an added condition for whether index
is greater than -1...then decrement it.
Testing my algorithm again. Success!
Time to test it again!
- It worked on the example input!
- It worked on my puzzle input!
Simulator: Update, or not?
- It was fun to simulate one polymer reduction
- Funnily enough, it would take several minutes to finish
- So, the fun was in watching the characters whizz by, and not in seeing it finish
For Part 2, I could attempt to simultaneously simulate all of the separate polymer reductions.
But that doesn't feel worth the reward.
So, I vote 'Not'.
I did it!!
- I solved both parts!
- I made a simulator for Part 1!
- I made a GIF to think through my anticipated algorithm
- I learned new ways to use
RegExp()
andreplaceAll()
- I was able to quickly troubleshoot my algorithm's unexpected error
Top comments (0)