Advent of Code Day 14–Reindeer Races

December 16. 2015 14:25

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 Array.map (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 Array.map 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"
  |> Array.map (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 =
  reindeeers
  |> List.map (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.map 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.map List.head xss :: yss)) (List.map 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 () =
  distances
  |> transpose
  |> List.reduce (fun scores distances ->
    let maxi = List.max distances
    distances
    |> List.zip scores
    |> List.map (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).

Sehnsucht