Skip to content

Instantly share code, notes, and snippets.

@bslatner
Last active Jan 4, 2016
Embed
What would you like to do?
Project Euler 14
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment