19 Day 19

The puzzle. Our input is list of “molecule” transformations that look like B => TiRnFAr, and then a longer test molecule.

19.1 How many distinct molecules can be created after one transformation?

Starting with our test molecule, we are asked to try every molecule transformation at every possible position, and count up the distinct molecules that are created.

Each molecule transformation defines a string replacement. We’ll parse our input into a test molecule, and a list of transformations (= each transformation is a list of a before and after string). Because we want to perform each transformation at every possible point in the test molecule, we can’t use regexp-replace (because it only replaces the first match) or regexp-replace* (because it replaces all matches). Instead we’ll use regexp-match-positions* to generate a list of match positions, and then perform the substitutions at each location to generate our list of molecules. After doing this for every transformation, we can remove-duplicates and see how many are left.

19.2 What’s the fewest number of transformations that will generate the test module?

Unlike some of the puzzles, this second part is a lot harder. The idea is that the test molecule was made from a series of transformations, starting with the single atom "e". So not only do we have to reverse-engineer this process, but we have to find the most efficient path.

There were three questions in Advent of Code that I couldn’t figure out. This was the first. The answer to the first question seems to provide a clue: we could reverse the transformations, perform the same replacement process, and we’d have a list of precursor molecules that could’ve existed one step before the test molecule. Then you repeat this process with all the possible precursors, until you get back to "e". This will work in theory, but not in practice, because it requires checking too many possibilities.

So I cheated. I adapted a Python algorithm for Racket. I can tell you how it works, though I’m still figuring out why it does. This function loops through the transformations and applies them everywhere they will fit. When it reaches a dead end — meaning, the molecule hasn’t changed during the loop — it randomly reorders the transformations with shuffle and tries again. It is strange to me that this process would converge to an answer at all, let alone the best answer, let alone so quickly.

19.3 Testing Day 19