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

ORnPBP­M­gAr­Ca­Ca­C­a­SiTh­Ca­C­a­SiTh­Ca…

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:

day19_01

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

day19_02

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:

day19_03

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:

day19_04

 

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:

day19_05

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”)

day19_06

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


day19_07