Advent Of Code - Day 14

Now we have to do some chemistry. Santa is pretty cool this way. They have a lot of skills mastered and read manuals like an expert. But this also means that manuals are always faulty. But Santa manages to work around these problems rather well.

Day 14 - Part 1

So, by reading the description and looking at the outcome, that a string only after 5 iterations will be this big, begs the question if we should build a primitive solution for this. Well, yes, I think we should. Part 2 will most likely be about something like, okay, now do this, but longer. I suspect this will be like the lanterfish thing. But let’s do it anyways.

A naive approach is to track the whole string and concatenate. This is done rather quickly, and earns us a good place if you managed to either wake up early, or not go to bed at all.

The concatenation is done quickly:

	steps := 10
	// insert then skip because pairs overlap.
	for step := 0; step < steps; step++ {
		newTemplate := " " // cheeky
		for i := 0; i < len(template)-1; i++ {
			pair := string(template[i]) + string(template[i+1])
			pair = string(pair[0]) + pairs[pair] + string(pair[1])
			newTemplate = newTemplate[:len(newTemplate)-1]
			newTemplate += pair
		}
		template = newTemplate
	}

And you can just see immediately how bad this would scale. But it works. And we have our star and the hull of the ship is now a bit stronger.

Day 14 - Part 2

Of course part 2 hits us in the face again, but instead of a fishy fist, we get a chemical fist. We know that this is similar to the lanterfish problem, right? So we got to look for some patterns again. We will have to most likely track something other than the string. Which means there is a solution to this which involves only counting. But what do we count and how? This is the question.

Let’s look at our string. Initial string is NNCB. We have a couple of pairs in this one as the example suggests. NN, NC, CB. That’s fine. Let’s look at the next iteration. NCNBCHB. Pairs?

NC, CN, NB, BC, CH, HB. We can see now a tiny bit of a pattern; namely that we’ll always end with B and that we’ll always start with N. Next.

NBCCNBBBCBHCB. Somewhat longer now, let’s list some pairs.

NB, BC, CC, CN, NB… hmmm. These are the same pairs. And if we go further and with a greater example, we’ll see that there are a finite number of pairs. So we track the pairs! But! Where do we get the pairs from? We can actually construct the pairs without having to concatenate all the strings.

Okay, okay, wait, what? Let’s initialize things so we can understand better.

	trackPairs := make(map[string]int)

	for i := 0; i < len(template)-1; i++ {
		trackPairs[string(template[i])+string(template[i+1])]++
	}

We have our initial pairs from the initial template. Now, what we have to do is use our rules for each pair in that map and construct new pairs with them. That part didn’t change. And add those pairs to a new map and update our tracking map.

	for i := 0; i < steps; i++ {
		update := make(map[string]int)
		for k, v := range trackPairs {
			update[string(k[0])+rules[k]] += v
			update[rules[k]+string(k[1])] += v
		}
		trackPairs = update
	}

We construct a new map and add the number of encountered pairs to this new pair. And if we already have it, it increases. Mind blown! This is all fine, but what do about counting the min and max characters? Well, all the characters are already there. Just construct a new map with a character count for each character.

	counts := map[string]int{}
	for k, v := range trackPairs {
		counts[string(k[0])] += v
	}

It’s enough to use the first one because they repeat.

We do some min, max on this map and tadaam. We have our value! We submit, and there is our second star. Fantastic!

Conclusion

Today, we learned again, that we should always look for patterns in the output. Sometimes they are well hidden. So we write out everything and try all combinations of things until something clicks.

The repository for all my solutions for AOC 2021 can be found here.

Thank you for reading!

Gergely.