Advent of Code F# – Day 7

Of all the Advent of Code challenges so far, Day 7 has been my favourite as it allowed me to flex a number of F# muscles around domain modelling, DSL parsing, and writing algorithms (albeit a simple one at that).

The source code for this post (both Part 1 and Part 2) is available here and you can click here to see my solutions for the other Advent of Code challenges.

 

Domain Modelling

Reading through the description, we can capture some key pieces of information:

1) “Each wire has an identifier (some lowercase letters) and can carry a 16-bit signal (a number from 0 to 65535).”

2) “…Each wire can only get a signal from one source…”

3) “…A signal is provided to each wire by a gate, another wire, or some specific value…”

4) “…A gate provides no signal until all of its inputs have a signal…”

Based on the above, we can deduce that:

a) a wire can carry Some 16-bit signal, or None; the same goes to the output signal from gates; so to simplify things and unify our model, we might say that all the signals are options:

(and we threw in a helper function as bonus)

b) there are three sources of signals – a gate, another wire, some specific value, and as far as gates are concerned the spec only contains unary and binary gates:

and we can define the available gates – AND, OR, LSHIFT, RSHIFT and NOT – in a separate module:

c) each wire has a name, and each wire gets its signal from one source:

and now we need to parse the input into our domain model.

DSL Parsing

The input for the challenge is expressed in a rather simple 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 ourselves some help, let’s create a Regex active pattern:

Starting with a default circuit (from the model above), as we read each line from the input we will add to the circuit gradually. We can do this easily with a fold:

This list does not cover ALL possible inputs (e.g. “2345 OR dc -> ak”) but is sufficient for my input, and each case is simple enough that you can easily add support for other inputs as you see fit.

Before we drill down into each of these cases, let’s add a couple of helper members to Circuit:

These will make our lives so much easier when parsing the DSL.

Starting with a simple case of a NOT gate (e.g. “NOT dq -> dr” which takes the “dq” wire as input to a NOT gate, and outputs the negated signal to the “dr” wire):

here, we connect the output wire to a NOT Gate and another input wire as identified by its name.

We can repeat the same pattern for AND gates:

notice that in this case, it’s also possible to have one of the inputs be a specific Value. There are two other cases that can occur (but didn’t in my input, hence omitted here):

• specific value on the righthand side of AND, e.g. ke AND 234 -> mb
• specific values on both sides of AND, e.g. 123 AND 456 -> rm

Moving on, we can do the same for OR, LSHIFT and RSHIFT:

again, these cases are not exhaustive, but merely exhaustive enough for my input.

Finally, we have the two cases where a wire gets its signal from another wire, or a specific value:

this completes our parsing logic.

Once we have built a Circuit from the input, we still need to evaluate the wires to find out what signal (if any) they hold at the end of all these.

Evaluating the Circuit

To trigger the evaluation of a wire (and return an updated instance of Circuit that contains the final value of the wire) we can have the following:

To walk you through what’s happening here:

1. first we try to evaluate the wire itself, in the best case scenario it already has a signal so no change required;
2. otherwise, we check against the connections we have for this circuit to see where the wire gets its signal from (i.e. its source), we’ll evaluate the source to work out what signal the wire should carry and then return an updated instance of Circuit using the AddWireOrUpdate instance member we introduced earlier;
3. when we try to evaluate the source, depending on its type we might have to evaluate another wire or another source first – which is why evaluate and evaluateSource are mutually recursive;
4. at the end of it all, we’ll end up with a Circuit object where the initial wire has been evaluated, along with all other wires that it derives its signal from.

Finally, to evaluate all the wires we have in the circuit, we’ll need to get all the keys from Circuit.Wires, and amazingly there’s no built-in Map.keys! So let’s roll our own:

with that, we can now answer our challenge 

 

Part 2

For part 2, we have to reset almost all the wires and undo a lot of our hard work from Part 1. Fortunately we already have the means to do that easily with the Circuit.AddWireOrUpdate method we added earlier.

So, starting with where we left over in Part 1, our solution for Part 2 is: