Posted in:

Day 14 of the Advent of Code challenge saw us racing reindeer. Here’s my solution video as usual in C# and F#.

Here’s my C# code, after a bit of refactoring. I’m actually quite pleased with the way this came out in the end, and it was one of the more compact solutions for any of the languages on the advent of code subreddit, which is quite rare for C#. To help us solve part b, we need to track the progress of each reindeer in each second, and yet again MoreLINQ to the rescue with the Scan method which is ideal for calculating running totals.

var lookup = File.ReadAllLines("day14.txt").Select(s => s.Split(' '))
    .Select(g => new { Speed = int.Parse(g[3]), Duration = int.Parse(g[6]), Rest = int.Parse(g[13]) })
    .Select(r => 
        Enumerable.Range(0, 2503)
        .Select(t => t % (r.Duration + r.Rest) < r.Duration ? r.Speed : 0)
        .Scan(0, (a, b) => a + b).Skip(1).ToArray())

lookup.Max(v => v[v.Length-1]).Dump("a"); // 2640
lookup.Max(v => v.Select((n,t) => n == lookup.Max(q => q[t]) ? 1 : 0).Sum()).Dump("b"); // 1102

And in F# I take the same approach. One slight niggle I have with F# is that the Seq.max function doesn’t let you pass in a selector like LINQ’s equivalent, so I had to make my own (called smax). In this example, it seems C# may just beat F# for conciseness (although of course I may be missing a few tricks).

let dist (speed,dur,rest) t = if t % (dur + rest) < dur then speed else 0

let progress n x = [0..n-1] |> (dist x) |> Seq.scan (+) 0 |> Seq.skip 1 |> Seq.toArray

let lookup = "day14.txt" |> File.ReadAllLines |> (fun s -> s.Split(' '))
                |> (fun a -> (int a.[3], int a.[6], int a.[13]))
                |> (progress 2503) 
let smax f = f >> Seq.max
lookup |> smax (fun v -> v.[v.Length - 1]) |> printfn "a: %d" // 2640

let getPoints = Seq.mapi (fun t n -> if n = (lookup |> smax (fun f->f.[t])) then 1 else 0) >> Seq.sum
lookup |> smax getPoints |> printfn "b: %d" // 1102
Want to learn more about LINQ? Be sure to check out my Pluralsight course LINQ Best Practices.


Comment by Sehnsucht

That's an interesting one.
There is a Seq.maxBy which takes some "selector" but it's signature isn't exactly the same as your smax function. smax returns the maximum value according to the selector given ; Seq.maxBy returns the "object" for which the selector gave it's maximal result.
(ie (with some pseudo-code : for a person list, smax (age) will yield the max age [ex 42] and Seq.maxBy (age) will yield the older people [ex the object "John Doe" which age is 42])
That said ; there is (maybe, I didn't thought it thoroughly) some "new tool" (from F#4.0 ; the documentation don't mention them yet) which can be handy ; namely I'm thinking of Seq.mapFold which allow some mapping (like map) from an initial state (like fold) and returns the mapped sequence along with the final accumulated state ; that could be used to map the distance along with who is in lead. (but again that's a big maybe)
Another little side note ; regarding a performance point of view ; your lookup value is made from three successive call to (which implies the creation of a brand new array at each step). I don't know the specifics of implementation (although the source is available) and I doubt the various allocation are optimized away ; so it could be smarter to just use one with the differents step all at once using function composition. In the same vein "beware" (both in C# and F#) getting the max inside looping constructs ; you recalculate at each step the same max over and over)
Now I choose a totally different way to solve this one ; abstracting away "what is a reindeer" : a thing which state is either flying at some given speed or resting

type ReindeerState =
Flying of speed : int
| Resting

from that I made the reindeers from the input each one being an infinite sequence of state (reusing my regex stuff I don't put it again this time)

let reindeers =
System.IO.File.ReadAllLines "day14.txt"
|> (function
Matches "\d+" [[Int speed]; [Int flight]; [Int rest]] ->
let rec flying () = seq {
for i = 1 to flight do yield Flying speed
yield! resting ()
and resting () = seq {
for i = 1 to rest do yield Resting
yield! flying ()
flying ())
|> Array.toList

I could have made only one sequence instead of two mutual recursive ; using a while true but I think it's clearer that way. I could also made that sequence such that they yield the current distance (and the code would have been simpler but a loss in abstraction)

let flying dist = seq {
for i = 1 to flight do yield dist + i * speed
yield! resting (dist + flight * speed)
and resting dist = seq {
for i = 1 to rest do yield dist
yield! flying dist

With that in hand having distance is just taking the needed part of the sequence and folding data ; but to reuse that for the part2 I use scan too

let distances =
|> (Seq.take 2503 >> Seq.scan (fun acc -> function Flying speed -> acc + speed | Resting -> acc) 0 >> Seq.toList)

That gives us a list of lists with the same kind of structure as your lookup.
From that part1 is just getting the max value inside all lists ; that could be done in several ways :

let part1_v1 () = distances |> List.maxBy List.max |> List.max // showing what I talked about maxBy earlier ; maxBy returns the whole list
let part1_v1_5 () = distances |> List.max |> List.max
let part1_v2 () = distances |> List.fold (fun acc -> List.max >> max acc) 0
let part1_v3 () = distances |> List.collect id |> List.max // flatten then get max

Now for part2 ; if we take a look at the distances value ; from a "matrix" point of view each row is some reindeer distance at each step. Now we need to see them column by column to see who is leading at each step. for that I'll need a way to transpose my data structure :

let transpose xss =
let rec aux k = function
(_ :: _) :: _ as xss -> aux (fun yss -> k ( List.head xss :: yss)) ( List.tail xss)
| _ -> k []
aux id xss

Transposing distances will then gives a new list of lists ; the first one only with 0s the second with each reindeer distance after 1 second and so on.
There you skip that first "row" ; me instead, use it as the initial state for scores/points so I only need to reduce (fold with first item as initial state) it at each step getting the current max and mapping my "current step distance" list to add 1 to score if it's the same as max

let part2 () =
|> transpose
|> List.reduce (fun scores distances ->
let maxi = List.max distances
|> scores
|> (fun (score, distance) -> if distance = maxi then score + 1 else score))
|> List.max

Well that was longer than I initially thought ; that'll probably be my last one for a while (going in my family for xmas).

Comment by Mark Heath

yeah, I like that F# has a maxBy - I use MoreLinq to get one in C# - just seemed strange that there was no equivalent to map>>max in F#, as it's quite handy. I'll check out mapFold - haven't come across that yet.
On the perf issues, the Array.maps were me doing a little bit of "code golf" to make my code more compact. I like the three maps in one idea though. They were originally with a toArray at the end. And my initial solution did cache the max value for a second, but it made the whole thing horribly verbose compared to this solution.
And I like your solution for today. An elegant approach. Anyway, enjoy your holidays. Have appreciated having my own personal F# code reviewer / mentor :)

Mark Heath