Extended Polymerization

Advent of Code 2021 Day 14

Try the simulator with your input

Solve for X where

X = the difference between the most and least common letters after N pair insertion steps

1. N = 10
2. N = 40

What's our input?

• A multi-line string

It represents two things

1. Starting template
2. Pair insertion rules

My naive, literal, brute-force algorithm

Step 1 - Parse the input into the two separate parts
  1. A string representation of the starting template
  2. An object where keys are adjacent letters and values are the letter to be inserted

Step 2 - Perform in-place pair insertion into a growing string of letters, just as the instructional diagram depicts
  Do N times
    Split the template into a list of ordered letters
    For each letter in the list at its initial length, starting from the letter at the end of the list:
      Look-up the rule matching the concatenation of the letter to the left and the current letter
      If a pairing rule exists:
        Update the array by inserting the correct letter between the current letter and the one to its left
    Reassign to the variable storing the starting template the result of joining each letter in the updated array

Step 3 - Tally each letter
  Store an object to be filled with keys of each letter and values that increment with each occurrence of that letter
  For each letter in the most updated template string
    If the object has a key of the letter, increment its value by 1
    Else, create the key and set its value to 1

Lastly, return the difference of the letter with the largest tally and the letter with the smallest tally

This animation demonstrates how Step 2 of my algorithm works:

Why my algorithm performs so terribly

• By the time N equals 13, the template string has 25k characters in it, and it is at least doubling with each iteration
• That's 25k splits, rule checks and splices
• The algorithm slows to a crawl at 15, and would likely never make it to 40

I was at a loss for how to solve this challenge any other way.

A short search for an eloquent solution

It didn't take long to find a solution that seemed concise, understandable with focused study, and eventually re-producible:

• JavaScript solver NullDev's solution was the perfect candidate

Studying NullDev's algorithm

There seem to be six key steps:

1. Parse the input to extract the template and - separately but combined - the rules and the bookends of the template (e.g. the first and last characters of the starting template)
2. Define the algorithm central to solving this puzzle
3. Apply it first to the starting template
4. Apply it for each subsequent processing of accumulated pairs
5. Apply it for each letter of the resulting pairs, including the initial bookend letters
6. Perform some math, and return the difference in counts of max and min

The core algorithm

(o, k, v = 1) => (o[k] = (k in o) ? o[k] + v : v);

Translated into pseudocode:

Define a function that expects three parameters:
  1. An object
  2. A key to lookup in that object
  3. A value - 1 - to assign to new keys, or to add to values of existing keys...

Body of the function:
  Assign to the object's key the following, depending on whether that key exists on the object:
    If it exists, assign to it the sum of the current value stored in that key and the passed in value
    Else - if it doesn't exist:
      Assign to it the value passed in, or 1    

This animation describes step 3

This animation describes step 4

This animation describes step 5

Here is the full picture of the three above steps from NullDev's eloquent algorithm:

Admiring the performance and mechanics of this algorithm

• At its core, the program tracks only a handful of keys and the increasing numbers stored in them
• It repeatedly builds a new object to collect the new tallies of sums of pairs created during polymerization, then updates the global object with the most recently-created one's keys and values
• It brilliantly uses the same single-operation function to perform slightly different operations on similarly-structured objects

Building a simulator to solve for my input

• Much like with previous exercises, I felt encouraged to build a web app where I could paste my input, click some buttons, and generate the answer for my - or any - input
• I reproduced NullDev's code using my own labels
• I reorganized my code into functions that could be called at the press of a button, instead of immediately
• I did some unavoidable debugging
• Alas, I had a working simulator that would display the characters and answer at any step of the polymerization process for any input

Such a rewarding feeling

• Loading my simulator
• Pasting in my input
• Pressing Start
• Seeing it work for a few rounds
• And for 10 rounds
• And for 40
• Copy-pasting the answer into the Advent of Code submission box
• Seeing that I got the answer right and being awarded the second gold star

Time well spent on this puzzle.

On to the next one!