Advent of Code F# – Day 1 to 6

In case you missed it, a lot of the good folks in the F# com­mu­ni­ty 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 catch­ing up this week­end, and here’s my solu­tions for the day 1–6.

p.s. you can find all my solu­tion on github, but the input is dif­fer­ent for every­one.

 

Day 1

image

Start­ing off nice and sim­ple, we can solve this prob­lem with a fold.

image

The only caveat I encoun­tered with this prob­lem was in fact, try­ing to cap­ture the input into a string val­ue:

image

which for some rea­son seems to upset F# inter­ac­tive:

image

Which is why I defined the input in a source file (day01.fs) whilst keep­ing the actu­al solu­tion in the script (day01.fsx).

After you solve the ques­tion, the sec­ond part of the chal­lenge is revealed (the same theme runs through­out all the chal­lenges).

 

Day 1 (Part 2)

image

This requires a slight twist to our approach to part 1 – we need the inter­me­di­ate steps of the fold instead of the final val­ue.

For­tu­nate­ly Seq.scan does just that!

image

Anoth­er thing to note is that, since Seq.scan returns the ini­tial val­ue (0 in this case) as part of the returned sequence, it means we didn’t have to shift our index sys­tem 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 split­ting strings eas­i­er (and pret­ti­er):

image

image

 

Day 2 (Part 2)

image

To find the short­est dis­tance around the small­est side, we just have to sort the dimen­sions then pick the first 2. So our solu­tion only needs a small tweak from part 1:

image

 

Day 3

image

Start­ing with an implied posi­tion of (0, 0), in order to find the num­ber of hous­es that received at least one present we need to find the num­ber of dis­tinct posi­tions that San­ta has tra­versed.

Again, fold to the res­cue!

image

 

Day 3 (Part 2)

image

First, let’s extract our fold log­ic out from part 1:

image

Now, we need to mas­sage 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 San­ta

seq { ‘v’; ‘v’; ‘v’; ‘v’; ‘v’ }   // for Robot-San­ta

}

which is what the first 4 LOC does:

image

so, to explain, we start with “^v^v^v^v” which is real­ly 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 log­ic we did pre­vi­ous­ly against each of the inner sequences;
  2. col­lect the result (i.e. the posi­tions tra­versed) into a uni­fied sequence
  3. count the dis­tinct posi­tions tra­versed by both San­ta and Robot-San­ta

and job done!

 

Day 4

image

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

You can then use BitConverter.ToString to get back a string rep­re­sen­ta­tion of the hex-dec­i­mal val­ue for the hash.

Or, you can take a short­cut, and take advan­tage of bina­ry-to-hex con­ver­sion where every 4 bits = 1 hex val­ue:

image

 

Day 4 (Part 2)

image

Because of the approach we took for part 1, the change here becomes as triv­ial as check­ing if the 3rd byte is also 0uy!

image

 

Day 5

image

First, let’s cap­ture the three require­ments for a nice string.

At least 3 vow­els, check.

image

At least 1 let­ter that appear twice in a row, check.

image

Does not con­tain cer­tain strings, check (in a more gener­ic way).

image

Then, let’s cre­ate a helper to make it eas­i­er for us to com­pose these three require­ments lat­er:

image

and final­ly let’s put every­thing togeth­er:

image

Voila!

aside : I think the <&&> oper­a­tor makes the code eas­i­er to read here. I’m usu­al­ly not a fan of spe­cial oper­a­tors, I find they often gets in the way of dis­cov­er­abil­i­ty and rais­es the bar­ri­er to entry for a library if there are too many spe­cial oper­a­tors one has to remem­ber. I think it’s ok in this case giv­en that the scope is real­ly small.

 

Day 5 (Part 2)

image

Again, let’s cap­ture the 2 new require­ments as func­tions.

At least one pair of let­ters that appear twice with­out over­lap, check.

image

Here, I’m tak­ing advan­tage of the fact that all the strings con­tains only alpha­bet char­ac­ters and replac­ing the pair of char­ac­ters cur­rent­ly being con­sid­ered with ‘-’. How­ev­er, it still feels as though I’m tak­ing the scenic route to express the require­ment here, if you have a bet­ter way, please let me know in the com­ments.

At least one let­ter that repeats with exact­ly one let­ter in between, check.

image

Like before, we just need to com­pose the two togeth­er to solve this chal­lenge.

image

 

Day 6

image

First, let’s look at the input for this chal­lenge.

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

so, we have coor­di­nates – int, int – and three dif­fer­ent actions – turn on, turn off, tog­gle – that we need to deal with:

image

For each line, the for­mat is:

{action} {start_coordinate} through {end_coordinate}

so we can write a sim­ple func­tion to parse it:

image

After the first split, we’ll end up an array con­sist­ing of the two coor­di­nates, e.g.

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

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

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

which is why we need­ed to fur­ther mas­sage the inner arrays in to int tuples.

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

 

Next, let’s have some lights!

image

And we also need a func­tion to per­form the parsed Action against the cor­re­spond­ing coor­di­nate rages:

image

and then hook every­thing togeth­er:

image

 

Final­ly, let’s count how many of the lights are turned on after per­form­ing all the actions. Unfor­tu­nate­ly, there’s no built-in sum, or sum­By func­tions in the Array2D mod­ule.. so for sim­plic­i­ty sake let’s just resort to using muta­ble state again.

image

 

Day 6 (Part 2)

image

We can reuse most of what we had done for part 1 of the chal­lenge, the main thing that has to change is the per­form func­tion:

image

and also how we cal­cu­late the final result:

image

and that’s it!

 

From Day 7, the chal­lenges start to get more chal­leng­ing, so watch this space for more solu­tions to come.