Advent of Code F# – Day 1 to 6

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

image

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

image

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

image

which for some reason seems to upset F# interactive:

image

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)

image

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!

image

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

image

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):

image

image

 

Day 2 (Part 2)

image

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:

image

 

Day 3

image

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!

image

 

Day 3 (Part 2)

image

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

image

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:

image

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

image

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:

image

 

Day 4 (Part 2)

image

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

image

 

Day 5

image

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

At least 3 vowels, check.

image

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

image

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

image

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

image

and finally let’s put everything together:

image

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)

image

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

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

image

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.

image

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

image

 

Day 6

image

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:

image

For each line, the format is:

{action} {start_coordinate} through {end_coordinate}

so we can write a simple function to parse it:

image

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!

image

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

image

and then hook everything together:

image

 

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.

image

 

Day 6 (Part 2)

image

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:

image

and also how we calculate the final result:

image

and that’s it!

 

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

9 Comments

  1. Pingback: F# Weekly #51, 2015 | Sergey Tihon's Blog

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

  3. Pingback: Advent of Code F# – Day 18 | theburningmonk.com

  4. Stu Cavill   •  

    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!

  5. Bryan Slatner   •  

    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?

  6. Yan Cui   •  

    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.

  7. Bryan Slatner   •  

    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.

  8. Yan Cui   •  

    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

Leave a Reply

Your email address will not be published.