Advent of Code F# – Day 19

The source code for this post (both Part 1 and Part 2) is avail­able here and you can click here to see my solu­tions for the oth­er Advent of Code chal­lenges.

Descrip­tion for today’s chal­lenge is here.


The input for Day 19 looks like the fol­low­ing:

Al => ThF

Al => ThRn­FAr

B => BCa

B => TiB


and it con­tains a series of replace­ment rules, as well as the mol­e­cule for a med­i­cine.

So we have two kinds of inputs in the same file:


and for each line in the file we will get one or the oth­er:


Since we know there’ll only be one mol­e­cule in the input file, we can again cheat a lit­tle and hard-wire a sin­gle ele­ment array pat­tern against the input:


Final­ly, to answer the chal­lenge, we’ll use each replace­ment rule to gen­er­ate a set of new mol­e­cules (one for each replace­able string in the cur­rent mol­e­cule) and count the unique strings that can be gen­er­at­ed:



Part 2

After get­ting stuck on this for the longest time and not able to come up with a solu­tion that solves a prob­lem with­in a rea­son­able amount of time (brute force approach just doesn’t work here), I even­tu­al­ly caved in and con­sult­ed the AoC sub­red­dit to see how oth­ers have solved this prob­lem, spoil­er alert and the solu­tion from askals­ki is soooo ele­gant.



(white­space intend­ed in case you don’t want to see the F# imple­men­ta­tion of askals­ki’s solu­tion)



OK, from here on, I assume you’ve read the sub­red­dit thread with the descrip­tion of the solu­tion.

So basi­cal­ly, the strings “Rn”, “Y”, “Ar” trans­lates to “(“, “,” and ”)”, and every­thing else are tokens (i.e. the left-hand sides of the replace­ment rules, e.g. “Ca => SiTh” means “Ca” is a token).

What’s more, we need to process the mol­e­cule from right-to-left, so we’ll reverse both the tokens as well as the mol­e­cule string itself:


Next, we’ll recur­sive­ly count the:

  • total num­ber of tokens (this includes “Rn”, “Y” and “Ar”)
  • num­ber of paren­the­ses (i.e. “Rn” and “Ar”)
  • num­ber of com­mas (i.e. “Y”)


and then final­ly apply askals­ki’s for­mu­la to arrive at the answer: