Alchemical Reduction

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

1. Many approaches. What's a smart one?
2. Animating my first algorithmic idea
3. Writing a working algorithm
4. 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

1. The same, but with fewer, and a lot more times!
2. How my anticipated algorithm will work
3. Testing my algorithm. Error!
4. Testing my algorithm again. Success!
5. 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 position 0 and 1

When I remove all K/ks, 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!

This was a beautiful sight:

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() and replaceAll()
• I was able to quickly troubleshoot my algorithm's unexpected error