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
- N = 10
- N = 40
What's our input?
- A multi-line string
It represents two things
- Starting template
- 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:
- 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)
- Define the algorithm central to solving this puzzle
- Apply it first to the starting template
- Apply it for each subsequent processing of accumulated pairs
- Apply it for each letter of the resulting pairs, including the initial bookend letters
- 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!
Top comments (0)