Advent of Code F# – Day 9

Yan Cui

I help clients go faster for less using serverless technologies.

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.

Description for today’s challenge is here.


The input for Day 9 looks like this:

AlphaCentauri to Snowdin = 66

AlphaCentauri to Tambi = 28

AlphaCentauri to Faerun = 60

Snowdin to Tambi = 22

Snowdin to Faerun = 12

there are similarities between this challenge and Day 7 in that they’re essentially a graph problem. In that case, let’s model this problem as a graph:


in our model of this problem, we have a set of cities, and the connections between them (where the key is the city to travel from, and the value is a map of the cities that you can travel to and the distance between the pair).

Like we did in Day 7, let’s add a helper function to help connect two cities – a and b – together, along with the distance between them.


Armed with the above, we can now go back to our input, parse each line into two cities and their distance, and then fold over them to build up a graph:


notice that the information we get from the input list is actually bi-directional, which is why in the fold we have to add the direction from a to b, as well as from b to a.

Next, starting with each cities, we want to find the routes that’ll visit each city once and only once.


aside: in hindsight, both the model and the path finding algorithm here can be simplified, I simply didn’t realise the distance data is bi-directional (it was implied through the example which I skimmed over and got started writing code…). For instance, the data is set up such that every city is connected to every other city, so the steps I have taken above to determine ‘which cities can I travel from here’ is redundant.

That said, I decided to keep the solution as it is because:

a) it can solve a more general problem where cities do not form a mesh network

b) it works, and pretty easy to understand, so why change 

The last building block we need to compose our final solution is the ability to calculate the total distance we have to travel in a route:


and to answer the challenge:


in hindsight, it might be better to write the above as:

    graph |> findPaths |> calcDistance |> Seq.min


Part 2

To work out the longest distance one can travel, simply flap the last line to look for the max distance instead, simple:



Whenever you’re ready, here are 4 ways I can help you:

  1. If you want a one-stop shop to help you quickly level up your serverless skills, you should check out my Production-Ready Serverless workshop. Over 20 AWS Heroes & Community Builders have passed through this workshop, plus 1000+ students from the likes of AWS, LEGO, Booking, HBO and Siemens.
  2. If you want to learn how to test serverless applications without all the pain and hassle, you should check out my latest course, Testing Serverless Architectures.
  3. If you’re a manager or founder and want to help your team move faster and build better software, then check out my consulting services.
  4. If you just want to hang out, talk serverless, or ask for help, then you should join my FREE Community.


Leave a Comment

Your email address will not be published. Required fields are marked *