Advent of Code F# – Day 7

You can become a serverless blackbelt. Enrol to my 4-week online workshop Production-Ready Serverless and gain hands-on experience building something from scratch using serverless technologies. At the end of the workshop, you should have a broader view of the challenges you will face as your serverless architecture matures and expands. You should also have a firm grasp on when serverless is a good fit for your system as well as common pitfalls you need to avoid. Sign up now and get 15% discount with the code yanprs15!

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:


Liked this article? Support me on Patreon and get direct help from me via a private Slack channel or 1-2-1 mentoring.
Subscribe to my newsletter

Hi, I’m Yan. I’m an AWS Serverless Hero and I help companies go faster for less by adopting serverless technologies successfully.

Are you struggling with serverless or need guidance on best practices? Do you want someone to review your architecture and help you avoid costly mistakes down the line? Whatever the case, I’m here to help.

Hire me.

Skill up your serverless game with this hands-on workshop.

My 4-week Production-Ready Serverless online workshop is back!

This course takes you through building a production-ready serverless web application from testing, deployment, security, all the way through to observability. The motivation for this course is to give you hands-on experience building something with serverless technologies while giving you a broader view of the challenges you will face as the architecture matures and expands.

We will start at the basics and give you a firm introduction to Lambda and all the relevant concepts and service features (including the latest announcements in 2020). And then gradually ramping up and cover a wide array of topics such as API security, testing strategies, CI/CD, secret management, and operational best practices for monitoring and troubleshooting.

If you enrol now you can also get 15% OFF with the promo code “yanprs15”.

Enrol now and SAVE 15%.

Check out my new podcast Real-World Serverless where I talk with engineers who are building amazing things with serverless technologies and discuss the real-world use cases and challenges they face. If you’re interested in what people are actually doing with serverless and what it’s really like to be working with serverless day-to-day, then this is the podcast for you.

Check out my new course, Learn you some Lambda best practice for great good! In this course, you will learn best practices for working with AWS Lambda in terms of performance, cost, security, scalability, resilience and observability. We will also cover latest features from re:Invent 2019 such as Provisioned Concurrency and Lambda Destinations. Enrol now and start learning!

Check out my video course, Complete Guide to AWS Step Functions. In this course, we’ll cover everything you need to know to use AWS Step Functions service effectively. There is something for everyone from beginners to more advanced users looking for design patterns and best practices. Enrol now and start learning!