Advent of Code 2021 - Day 14

The problem

Given a polymer template and a list of pair insertion rules. Repeat the pair insertion process a few times and find out quantity of the most common element and subtract the quantity of the least common element

Your can read more about the puzzle here

Day 14 - Advent of Code 2021

Advent of Code 2021

Finding the pattern

NNCB

CH -> B
HH -> N
CB -> H
NH -> C
HB -> C
HC -> B
HN -> C
NN -> C
BH -> H
NC -> B
NB -> B
BN -> B
BB -> N
BC -> B
CC -> N
CN -> C

The pattern is pretty straight foward, for each pair of letter in the current polymer string, we are going to check if there is any insertion rules for that pair, for example, first pair is "NN" insertion rule is NN -> C , our current polymer string will transform into "NCNCB" , our current index is 0, beacause insertions all happen simultaneously which mean that we wont process the newly insterted pair NC right now, we will need to increase the index 2 times, so the new index would be 2, our next pair is NC. Reapeat until we reach the end of polymer, and we will have our answers.

const execStep = (polymer, template) => {
  let i = 0;
  while (i < polymer.length - 1) {
    const pair = polymer[i] + polymer[i + 1];
    const matchTemplate = template.find((item) => item[0] === pair);
    if (matchTemplate) {
      polymer =
        polymer.slice(0, i + 1) + matchTemplate[1] + polymer.slice(i + 1);
      i++;
    }
    i++;
  }

  return polymer;
};

Our simple solution works for now in the first part with the requirement of 10 steps ✨

Let the fun begin

I should've known better, the second part is the same but with a requirement of 40 steps calculation. Our polymer increase exponentially with our current implementation, my PC begin to sweat, fan start to spin louder ?we need another solution, quick !

So i remembered the Lattern Fish problem in Day6, we don't need to store the actual generated polymer, we only need to know the number of each character ?

So with that in mind, begin with the number occurences of each pair, we can calculate the new number of pair after each insertion ! ?

From NNCB we have NN: 1, NC:1, CB: 1, after 1 step we will have NCNBCHB, NC:1, CN:1, NB:1, BC:1 , CH:1, HB: 1

With the first pair NN, we are already known its insertion rule is NN -> C, which mean, no more NN => NN: 0, new 2 pair NC:1 and CN:1. Next pair is NC, with an insertion rule NC => B , so same thing no more NC: 0, for each NC we going to have another NB and BC, we are currently at 2 NC, so it would be NB: 2, CB: 2, right ?  

Remember insertions all happen simultaneously, yeah thats mean we dont update our counter directly ! We need to duplicate the counter and update it with the original values so we don't take account of the news pair.

const execStep2 = (pairCount, template) => {
  const result = { ...pairCount };
  console.log(pairCount);
  Object.keys(pairCount).forEach((pair) => {
    const matchTemplate = template.find((item) => item[0] === pair);
    if (matchTemplate) {
      // slit the pair
      const firstPair = pair[0] + matchTemplate[1];
      const secondPair = matchTemplate[1] + pair[1];
    
      result[firstPair] = (result[firstPair] ?? 0) + pairCount[pair];
      result[secondPair] = (result[secondPair] ?? 0) + pairCount[pair];
      result[pair] -= pairCount[pair];
    }
  });

  return result;
};

So now we got our counters of every pair, we are going to need to count the single letters. To do it, i count of the first letter of each pair and add them together PLUS the very last letter of the template needs to be added separately. So we have our answer !

PSA: Always remember to think ahead the size of generated results so we directly implement an optimized solution.

That's it for today, thank you for reading ! 🎉