Advent of Code F# – Day 7

Of all the Advent of Code chal­lenges so far, Day 7 has been my favourite as it allowed me to flex a num­ber of F# mus­cles around domain mod­el­ling, DSL pars­ing, and writ­ing algo­rithms (albeit a sim­ple one at that).

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.

 

Domain Modelling

Read­ing through the descrip­tion, we can cap­ture some key pieces of infor­ma­tion:

1) “Each wire has an iden­ti­fi­er (some low­er­case let­ters) and can car­ry a 16-bit sig­nal (a num­ber from 0 to 65535).”

2) “…Each wire can only get a sig­nal from one source…”

3) “…A sig­nal is pro­vid­ed to each wire by a gate, anoth­er wire, or some spe­cif­ic val­ue…”

4) “…A gate pro­vides no sig­nal until all of its inputs have a sig­nal…”

Based on the above, we can deduce that:

a) a wire can car­ry Some 16-bit sig­nal, or None; the same goes to the out­put sig­nal from gates; so to sim­pli­fy things and uni­fy our mod­el, we might say that all the sig­nals are options:

day07_01

(and we threw in a helper func­tion as bonus)

b) there are three sources of sig­nals — a gate, anoth­er wire, some spe­cif­ic val­ue, and as far as gates are con­cerned the spec only con­tains unary and bina­ry gates:

day07_02

and we can define the avail­able gates — AND, OR, LSHIFT, RSHIFT and NOT — in a sep­a­rate mod­ule:

day07_03v2

c) each wire has a name, and each wire gets its sig­nal from one source:

day07_04

and now we need to parse the input into our domain mod­el.

DSL Parsing

The input for the chal­lenge is expressed in a rather sim­ple DSL, e.g.:

NOT dq -> dr
kg OR kf -> kh
44430 -> b
eg AND ei -> ej
y AND ae -> ag
lf RSHIFT 2 -> lg
z AND aa -> ac
kk RSHIFT 3 -> km
...

so to give our­selves some help, let’s cre­ate a Regex active pat­tern:

day07_05

Start­ing with a default cir­cuit (from the mod­el above), as we read each line from the input we will add to the cir­cuit grad­u­al­ly. We can do this eas­i­ly with a fold:

day07_06

This list does not cov­er ALL pos­si­ble inputs (e.g. “2345 OR dc -> ak”) but is suf­fi­cient for my input, and each case is sim­ple enough that you can eas­i­ly add sup­port for oth­er inputs as you see fit.

Before we drill down into each of these cas­es, let’s add a cou­ple of helper mem­bers to Cir­cuit:

day07_07

These will make our lives so much eas­i­er when pars­ing the DSL.

Start­ing with a sim­ple case of a NOT gate (e.g. “NOT dq -> dr” which takes the “dq” wire as input to a NOT gate, and out­puts the negat­ed sig­nal to the “dr” wire):

day07_08

here, we con­nect the out­put wire to a NOT Gate and anoth­er input wire as iden­ti­fied by its name.

We can repeat the same pat­tern for AND gates:

day07_09

notice that in this case, it’s also pos­si­ble to have one of the inputs be a spe­cif­ic Val­ue. There are two oth­er cas­es that can occur (but didn’t in my input, hence omit­ted here):

  • spe­cif­ic val­ue on the right­hand side of AND, e.g. ke AND 234 -> mb
  • spe­cif­ic val­ues on both sides of AND, e.g. 123 AND 456 -> rm

Mov­ing on, we can do the same for OR, LSHIFT and RSHIFT:

day07_10

again, these cas­es are not exhaus­tive, but mere­ly exhaus­tive enough for my input.

Final­ly, we have the two cas­es where a wire gets its sig­nal from anoth­er wire, or a spe­cif­ic val­ue:

day07_11

this com­pletes our pars­ing log­ic.

Once we have built a Cir­cuit from the input, we still need to eval­u­ate the wires to find out what sig­nal (if any) they hold at the end of all these.

Evaluating the Circuit

To trig­ger the eval­u­a­tion of a wire (and return an updat­ed instance of Cir­cuit that con­tains the final val­ue of the wire) we can have the fol­low­ing:

day07_12

To walk you through what’s hap­pen­ing here:

  1. first we try to eval­u­ate the wire itself, in the best case sce­nario it already has a sig­nal so no change required;
  2. oth­er­wise, we check against the con­nec­tions we have for this cir­cuit to see where the wire gets its sig­nal from (i.e. its source), we’ll eval­u­ate the source to work out what sig­nal the wire should car­ry and then return an updat­ed instance of Cir­cuit using the AddWire­OrUp­date instance mem­ber we intro­duced ear­li­er;
  3. when we try to eval­u­ate the source, depend­ing on its type we might have to eval­u­ate anoth­er wire or anoth­er source first — which is why eval­u­ate and eval­u­ate­Source are mutu­al­ly recur­sive;
  4. at the end of it all, we’ll end up with a Cir­cuit object where the ini­tial wire has been eval­u­at­ed, along with all oth­er wires that it derives its sig­nal from.

Final­ly, to eval­u­ate all the wires we have in the cir­cuit, we’ll need to get all the keys from Circuit.Wires, and amaz­ing­ly there’s no built-in Map.keys! So let’s roll our own:

day07_13

with that, we can now answer our chal­lenge 

day07_14

 

Part 2

For part 2, we have to reset almost all the wires and undo a lot of our hard work from Part 1. For­tu­nate­ly we already have the means to do that eas­i­ly with the Circuit.AddWireOrUpdate method we added ear­li­er.

So, start­ing with where we left over in Part 1, our solu­tion for Part 2 is:

day07_15