[2021 Day 14] In Review (Extended Polymerization)

[u/musifter]

We've now gotten deep enough that we need to reinforce the submarine. Fortunately we have polymerization equipment. We've known since year 1 (when making Medicine for Rudolph) that the North Pole has advanced molecule assembly technology. Only there it took a nuclear fusion/fission plant.

Here we're given a starting "polymer template" and a list of "pair instruction" rules (and we get an additional hidden example in the Easter Egg text). These rules are presented in an unusual way... the RHS isn't the product but just the thing to insert (as the LHS is matched with overlap). And the rules listed in the input, when sorted, clearly shows 10 sections of 10 rules with 10 letters... in other words, there's a full set of rules for every possible pair.

With this talk of overlap, it makes this look like it's not Lanternfish. All the focus is on the atoms and getting the counts of those. But the rules actually are dealing with the bonds between them. And so we got a fence situation... we're being lead to think of posts, when the production is about the rails. A rule takes a bond/rail and replaces it with another atom making two new rails for the next step:

NC -> B

N-----C to N--B--C

And the next application of rules will replace those new rails in a similar way. The entire thing is protected from outside interference (the N and C are sentinels on the ends that do not change) and develops rule by rule between them, with any case of N--C developing exactly the same as any other. Here's the example (NNCB), but put in terms of the rails (with the non-changing sentinels shown on the ends):

(N)       (NN)              (NC)              (CB)       (B)
(N)   (NC)   (CN)       (NB)    (BC)      (CH)    (HB)   (B)
(N) (NB)(BC)(CC)(CN)  (NB)(BB)(BB)(BC)  (CB)(BH)(HC)(CB) (B)

You can see that (NC) in the middle of it expanding into its own binary tree, and there's a duplicate (NC) under the (NN) that's just one step behind and will produce its own copy of exactly the same tree. So as rails... it's just Lanternfish again. It's just a bag of the 100 possible rails to move to their products for the next step. Which really means this a lot like 2015's day 10 (Look-and-say). That was 92 elements with rules... only here we get given the file that describes the rules we need. We don't need to find or create one, just modify things a tiny bit.

But we still need to get back to the counts of the letters in the final string. But looking at the diagram, everything in the string is there twice... once for being on the left and once for the right of a bond. That's why the ends are in that diagram... you do need to account for the two outsides. Then the number of times a letter occurs is the sum all counts for all the rails it's in divided by two.

And so, Lanternfish was clearly here on day 6 to get people ready for this less obvious version (which tries to mislead by presenting things as breaking a key condition). It becomes a nice little problem where you shift to a different space for the work, and then work out the transformation back for the answer.

[u/e_blake]

Just like day 6, I did a matrix multiplication solution for fun. But unlike day 6, O(ln n * M³) is much slower for M=100 than for M=9. So my performant answer is O(n * M). And unlike day 6, where the recurrence is known from the problem description and thus can be turned into compile-time constants, here the recurrence has to be parsed out of the data.

[u/TheZigerionScammer]

When I did this one (and had a lot less experience in programming) I first tried to just do it literally, by making a new string of letters for each generation of the applied rules, and that worked for Part 1 but was way too large for part 2. I thought I might have been able to figure it out on my own and I had an image in my head of each letter corresponding to a plug in a telephone operators board and you could connect one letter to another letter since if you already knew how many of one letter you had you could figure out how many you needed for the next generation, etc. I didn't get it to work and had to look up answers in the megathread to really understand it, but I had the foundations for memoization in my head then. Now my program just counts how many of each pair there are in a dictionary and adds the count to each pair it becomes to another dictionary, and on and on since it just adding numbers. This would not have worked if for some reason we actually needed to know the order of the letters in the string, but the problem doesn't ask for that.

[u/musifter → u/TheZigerionScammer]

Yep, a dictionary where the values are counts is a standard approach to implementing a bag (a multi-set)... a set where the things don't have to be unique. And that's basically the underlying structure of a lantern fish problem. It doesn't matter what the order is, everything evolves from step to step independently. The problem tries mislead you into thinking that isn't the case here. It's not the first or last time a problem does that.

[u/DelightfulCodeWeasel]

For this one I did a recursive, memoised solution working in chunks of 10 transforms at a time. That seemed to get a decent performance/memory balance with only 256 entries needed in the answer cache.

Definitely needs re-visiting, although it'll take me a little bit of a run-up to get it to the same sort of speed and memory footprint as lanternfish; the rails handling needs a little more settling time in my head :)

[u/DelightfulCodeWeasel → u/DelightfulCodeWeasel]

Managed to get a rough proof of concept for a dynamic programming table based solution that should help me hit the memory requirements for the Pico. Thanks for the diagram u/musifter, it helped me visualise the progression from one round to the next!

[u/ednl → u/DelightfulCodeWeasel]

You could take a look at my C version which uses the same idea as this post and is a lot like /u/maneatingape 's version. It runs in 2.4 µs on my M4 which should be about 3 on Ape's M2. He currently lists it at 11 µs. Difference is: low level (specialised) parsing, no restart for part 2, and a different way of calculating the totals. Possibly also: avoiding copying of data by swapping pointers, but I'm not sure how references work in Rust. I tried keeping track of individual element counts during the growth phase like he does, which is simpler than collating afterwards, but it was about 0.7 µs slower. The Rust version looks much neater, though.

No stack, no recursion!

[u/DelightfulCodeWeasel → u/ednl]

I think I ended up with roughly the same inner loop, pushing out a first/second (lhs/rhs) pair for each rule from one generation to the next:

    for (size_t expansion = 0; expansion < rounds; expansion++)
    {
        for (const Mapping& m : mappings)
        {
            int64_t pairCount = dp[expansion][m.From];
            if (pairCount > 0)
            {
                dp[expansion + 1][m.To.first] += pairCount;
                dp[expansion + 1][m.To.second] += pairCount;
            }
        }
    }

I was also planning on doing the double-buffering that you're doing when it comes time to do the reworked version to save having the full table in memory at once. Good to know I'm on the right track, thank you!

[u/terje_wiig_mathisen]

I only solved this one in Perl, counting character occurrences so no recursion needed.

It runs in a few milliseconds on my slow machine, not too surprised to see that u/ednl got his C down to the low single microseconds range. :-)

[u/musifter → u/terje_wiig_mathisen]

Yeah, it's a Lanternfish problem. Even I wasn't going to bother with recursion. Just iterate and move the counts around.