Project Euler 14

Problem14.fsx

#load "Helpers.fs"

open Helpers

let next n =
    match n with
    | Even64 -> n/2L
    | Odd64 -> 3L*n+1L

let collatzLength start = 
    let mutable count = 1L
    let mutable current = start
 
    while current > 1L do
        current <- next current
        count <- count + 1L
    count

let cache = System.Collections.Generic.Dictionary<int64,int64>()

let collatzLengthCached start =
    let mutable count = 1L
    let mutable current = start

    while current > 1L do
        match cache.TryGetValue current with
        | true,cachedCount ->
            count <- count + cachedCount
            current <- 1L
        | _ ->
            current <- next current
            count <- count + 1L

    cache.Add(start,count)
    count

let findLengthsAsync startNum endNum = async {
    return 
        seq { startNum..endNum }
        |> Seq.map (fun i -> i,collatzLength i)
        |> Seq.maxBy snd
}

#time
let sanswer = seq { 1L..999999L } |> Seq.maxBy collatzLength
#time

#time
let canswer = seq { 1L..999999L} |> Seq.maxBy collatzLengthCached
#time

let ranges = [ 1L,125000L; 125001L,250000L; 250001L,375000L; 375001L,500000L; 500001L,625000L; 625001L,750000L; 750001L,875000L; 875001L,999999L ]

#time
let aanswer =
    ranges
    |> Seq.map (fun (s,e) -> findLengthsAsync s e)
    |> Async.Parallel
    |> Async.RunSynchronously
    |> Seq.maxBy snd
    |> fst
#time

printfn "Answer sync : %i" sanswer
printfn "Answer cache: %i" canswer
printfn "Answer async: %i" aanswer