Advent of Code F# – Day 1 to 6

Yan Cui

I help clients go faster for less using serverless technologies.

Table of Content

In case you missed it, a lot of the good folks in the F# community has been doing the Advent of Code the past 2 weeks. I’m a bit late to the game, but have done a lot of catching up this weekend, and here’s my solutions for the day 1-6.

p.s. you can find all my solution on github, but the input is different for everyone.

Day 1

Starting off nice and simple, we can solve this problem with a fold.

The only caveat I encountered with this problem was in fact, trying to capture the input into a string value:

which for some reason seems to upset F# interactive:

Which is why I defined the input in a source file (day01.fs) whilst keeping the actual solution in the script (day01.fsx).

After you solve the question, the second part of the challenge is revealed (the same theme runs throughout all the challenges).

Day 1 (Part 2)

This requires a slight twist to our approach to part 1 – we need the intermediate steps of the fold instead of the final value.

Fortunately Seq.scan does just that!

Another thing to note is that, since Seq.scan returns the initial value (0 in this case) as part of the returned sequence, it means we didn’t have to shift our index system from 0-based to 1-based.

Day 2

First, bear in mind that the input looks like this:

20x3x11
15x27x5
6x29x7
30x15x9
19x29x21
10x4x15

so let’s add a helper to make splitting strings easier (and prettier):

Day 2 (Part 2)

To find the shortest distance around the smallest side, we just have to sort the dimensions then pick the first 2. So our solution only needs a small tweak from part 1:

Day 3

Starting with an implied position of (0, 0), in order to find the number of houses that received at least one present we need to find the number of distinct positions that Santa has traversed.

Again, fold to the rescue!

Day 3 (Part 2)

First, let’s extract our fold logic out from part 1:

Now, we need to massage the input (e.g. ^v^v^v^v^v) into two sequences, i.e.:

input : seq { ‘^’; ‘v’; ‘^’; ‘v’; ‘^’; ‘v’; ‘^’; ‘v’; ‘^’; ‘v’ }

we want :

seq {

seq { ‘^’; ‘^’; ‘^’; ‘^’; ‘^’ }  // for Santa

seq { ‘v’; ‘v’; ‘v’; ‘v’; ‘v’ }   // for Robot-Santa

}

which is what the first 4 LOC does:

so, to explain, we start with “^v^v^v^v” which is really just a sequence of chars:

seq { ‘^’; ‘v’; ‘^’; ‘v’; ‘^’; ‘v’; ‘^’; ‘v’; ‘^’; ‘v’ }

=> seq { (0, ‘^’); (1, ‘v’); (0, ‘^’); (1, ‘v’); … }

=> seq {

(0, seq { (0, ‘^’); (0, ‘^’); (0, ‘^’); … })

(1, seq { (1, ‘v’); (1, ‘v’); (1, ‘v’); … }) }

=> seq {

seq { ‘^’; ‘^’; ‘^’; … }

seq { ‘v’; ‘v’; ‘v’; … } }

after we’ve done that, we

1. apply the same fold logic we did previously against each of the inner sequences;
2. collect the result (i.e. the positions traversed) into a unified sequence
3. count the distinct positions traversed by both Santa and Robot-Santa

and job done!

Day 4

In .Net you can use System.Security.Cryptography.MD5 to create a MD5 hash (as a byte[]) for some input byte[].

You can then use BitConverter.ToString to get back a string representation of the hex-decimal value for the hash.

Or, you can take a shortcut, and take advantage of binary-to-hex conversion where every 4 bits = 1 hex value:

Day 4 (Part 2)

Because of the approach we took for part 1, the change here becomes as trivial as checking if the 3rd byte is also 0uy!

Day 5

First, let’s capture the three requirements for a nice string.

At least 3 vowels, check.

At least 1 letter that appear twice in a row, check.

Does not contain certain strings, check (in a more generic way).

Then, let’s create a helper to make it easier for us to compose these three requirements later:

and finally let’s put everything together:

Voila!

aside : I think the <&&> operator makes the code easier to read here. I’m usually not a fan of special operators, I find they often gets in the way of discoverability and raises the barrier to entry for a library if there are too many special operators one has to remember. I think it’s ok in this case given that the scope is really small.

Day 5 (Part 2)

Again, let’s capture the 2 new requirements as functions.

At least one pair of letters that appear twice without overlap, check.

Here, I’m taking advantage of the fact that all the strings contains only alphabet characters and replacing the pair of characters currently being considered with ‘-’. However, it still feels as though I’m taking the scenic route to express the requirement here, if you have a better way, please let me know in the comments.

At least one letter that repeats with exactly one letter in between, check.

Like before, we just need to compose the two together to solve this challenge.

Day 6

First, let’s look at the input for this challenge.

turn on 489,959 through 759,964
turn off 820,516 through 871,914
turn off 427,423 through 929,502
toggle 756,965 through 812,992

so, we have coordinates – int, int – and three different actions – turn on, turn off, toggle – that we need to deal with:

For each line, the format is:

{action} {start_coordinate} through {end_coordinate}

so we can write a simple function to parse it:

After the first split, we’ll end up an array consisting of the two coordinates, e.g.

[| “ 489,959 ”; “ 759,964 ” |]

splitting each by ‘,’ again gives us an array of arrays, e.g.:

[|  [| “489”; “959” |];  [| “759”; “964” |]  |]

which is why we needed to further massage the inner arrays in to int tuples.

[| (489, 959); (759, 964) |]

Next, let’s have some lights!

And we also need a function to perform the parsed Action against the corresponding coordinate rages:

and then hook everything together:

Finally, let’s count how many of the lights are turned on after performing all the actions. Unfortunately, there’s no built-in sum, or sumBy functions in the Array2D module.. so for simplicity sake let’s just resort to using mutable state again.

Day 6 (Part 2)

We can reuse most of what we had done for part 1 of the challenge, the main thing that has to change is the perform function:

and also how we calculate the final result:

and that’s it!

From Day 7, the challenges start to get more challenging, so watch this space for more solutions to come.

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

1. Production-Ready Serverless: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for quickly levelling up your serverless skills.
2. Do you want to know how to test serverless architectures with a fast dev & test loop? Check out my latest course, Testing Serverless Architectures and learn the smart way to test serverless.
3. I help clients launch product ideas, improve their development processes and upskill their teams. If you’d like to work together, then let’s get in touch.
4. Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.

9 thoughts on “Advent of Code F# – Day 1 to 6”

1. Pingback: F# Weekly #51, 2015-IT??

2. Thanks for this. :) My Day 2 solution in F# was a right convoluted mess. Great to see it done in less than 20 lines of code compared to my 100!

3. I’m pretty new to F# and I must admit that I absolutely don’t understand your day 3 solution. That syntax is completely foreign to me, and I don’t even know what to Google to get an explanation :)

I solved Day 3 part 1 with Seq.scan to produce a Seq of position tuples. Then, like you, I piped that through distinct and length.

Can you explain your solution a little bit more, or point me to where I can read up on that technique you’re using?

4. Hi Bryan, I assume you mean the use of :: notation? That is known as the cons operator, and it’s how you attach a new head element to a list (F# lists are linked lists).

What I did in my solution was to apply it in a pattern matching against the current ‘state’ of the fold. If you break down that fold logic :
input
|> Seq.fold (fun …) [ (0,0) ]

you’ll see that I’m folding over the inputs with the starting state of [ (0, 0) ], i.e. a (int * int) list. For every input value the fold will append another tuple of (x,y) coordinates to the state, to do that I need to know the most recent (x,y) coordinate – i.e. I need to get the head element from the state.
One way to do this would be:
Seq.fold (fun acc nxt ->
let hd::tl = acc
match nxt with
| ‘^’ -> …) [ (0,0) ]
which is how you can pattern match against a F# list to get the head element (hd) and the rest of list, or commonly referred to as the ‘tail’ (tl).
But, since you can apply pattern matching in the function arguments too, so this is equivalent to:
Seq.fold (fun (hd::tl) nxt ->
match nxt with
| ‘^’ -> …) [ (0,0) ]
we can go a step further, because we’re dealing with a int*int list, so we can also pattern match against the head element itself! So to get the x and y coordinates of the head element, we can do this:
Seq.fold (fun ((x,y)::tl) nxt ->
…) [ (0,0) ]
We don’t actually care about the tail, in this case, so we can ignore it with the wildcard _ and our pattern can be simplified to ((x,y)::_)

However, we also need to capture the whole state, not just the x and y coordinates of the head element (our fold function needs to add a new element to it). And we can do that using the ‘as’ keyword here:
Seq.fold (fun ((x,y)::_ as acc) nxt ->
…) [ (0,0) ]
so in one single pattern, we managed to extract a) the last visited (x,y) coordinate, and b) all the visited coordinates as ‘acc’
Later on when we match against ‘nxt’, we return a new list by adding a new element to ‘acc’, again using the cons (::) operator:
match nxt with
| ‘^’ -> (x, y-1)::acc
| ‘>’ -> (x+1, y)::acc

Hope this is clear, let me know if you have any other questions. In truth, Seq.Scan is clearer and more succinct in this case.

5. Wow, thanks so much for that explanation. This finally “clicked” for me. I didn’t realize that you could use pattern matching syntax to decompose arguments passed to a function. Well, I suppose I did know that, but I didn’t realize it was quite this smart or powerful.

6. You’re welcome, it’s one of the things that most beginner books/articles don’t seem to mention. Plus, you can also use pattern matching on the left-hand side of an assignment too, e.g. we can apply the same pattern here too:

> let ((x,y)::_ as coordinate) = …

which would be the same as doing:

> let coordinates = …
> let (x,y) = coordinates.Head