Day fourteen of AoC 2021 (see https://adventofcode.com/2021/day/14) is what happens when chemistry class meets combinatorics and your RAM is the first casualty. The submarine’s polymerization equipment is supposed to reinforce the hull, but after reading the puzzle, I was more worried about reinforcing my patience.
The task: take a humble polymer template and, using a set of pair insertion rules, mutate it step by step. At first, it’s a simple string transformation. But after a few rounds, the polymer starts to grow like a chain reaction—doubling, tripling, and soon threatening to eat all available memory. (If you’ve ever tried to brute-force a problem and watched your computer beg for mercy, you know the feeling.)
Parsing the Input
The input is classic AoC: a starting string, a blank line, and then a list of rules like AB -> C. Each rule means: whenever you see the pair AB, insert C between them. I parsed the template as a string and the rules as a lookup object for fast access. (If you’re not using hash maps for AoC, are you even trying?)
const processInput = async (day: number) => {
const lines = await readInputLines(day);
const polymer = lines[0];
const rules = Object.fromEntries(
lines.slice(2).map(line => {
const [pair, insert] = line.split(' -> ');
return [pair, insert];
})
);
return { polymer, rules };
};
Part One: Naive Simulation (a.k.a. The Brute Force Blues)
My first instinct: just simulate the process. Loop through the string, apply the rules, build a new string, repeat. For 10 steps, this works fine. For 20 steps, you start to see the problem. For 40 steps, you start to see your life flash before your eyes. (Spoiler: the string length grows exponentially. By step 20, you’re looking at millions of characters. By step 40, you’re looking at a new computer.)
Still, for part one, brute force is enough. After 10 steps, count the frequency of each element, subtract the least from the most, and you’re golden. It’s a classic AoC move: get the star, then realize you need a new plan for part two.
Part Two: When Brute Force Breaks (a.k.a. Enter the Hash Map)
Part two asks for 40 steps. At this point, brute force is a chain around your neck. Time to get clever.
The key insight: you don’t need the whole string, just the counts of each pair. Instead of tracking the actual polymer, track how many times each pair appears. Each step, update the pair counts according to the rules. This keeps the data manageable, and suddenly, 40 steps is no big deal.
It’s a beautiful moment when you realize you can outsmart the exponential growth. The code goes from “please don’t crash” to “bring it on.”
Performance Notes
- Part one (10 steps): ~6ms, brute force, lots of string copying
- Part two (40 steps): ~50ms, pair counting, barely a blip on the CPU
- Memory usage: no longer measured in gigabytes of regret
Takeaways
- Exponential growth is a classic AoC gotcha—if your code feels slow, it probably is.
- Hash maps (objects) are the unsung heroes of Advent of Code.
- Sometimes you have to break the chains of brute force and riff on a smarter solution.
- If you’re seeing “out of memory” errors, you’re probably doing something interesting.