Skip to content

Instantly share code, notes, and snippets.

@edvakf edvakf/euler78-2.fsx
Last active Aug 29, 2015

Embed
What would you like to do?
open System.Collections.Generic
let limit = 100000
let divisor = 1000000
let memo = new Dictionary<int,int> ()
let rec partitions = fun (n, m) ->
if (n >= limit || m >= limit) then 0
elif (n = 0) then 1
elif (n = 1 || m = 1) then 1
elif (n < m) then partitions(n, n)
elif (memo.ContainsKey(n * limit + m)) then memo.[n * limit + m]
else
let result = List.reduce (fun sum x -> (sum + x) % divisor ) [ for i in 1 .. m -> partitions(n - i, i) ]
memo.Add(n * limit + m, result)
result
let rec f = fun n -> if (partitions(n, n) = 0) then n else f(n+1)
let start = fun _ -> printfn "%d" (f 1)
start()
open System.Collections.Generic
let limit = 100000
let divisor = 1000000
let memo = new Dictionary<int,int> ()
let rec partitions n m =
if (n >= limit || m >= limit) then 0
elif (n = 0) then 1
elif (n = 1 || m = 1) then 1
elif (n < m) then partitions n n
elif (memo.ContainsKey(n * limit + m)) then memo.[n * limit + m]
else
let result = List.reduce (fun sum x -> (sum + x) % divisor ) [ for i in 1 .. m -> partitions (n - i) i ]
memo.Add(n * limit + m, result)
result
let rec f n = if ((partitions n n) = 0) then n else f(n+1)
let start = printfn "%d" (f 1)
start
let memo = [| for i in 1 .. 10 -> [| for i in 1 .. 10 -> -1 |] |]
let rec partitions = fun (n, m) ->
printfn "partitions %d, %d" n m
if (n >= 10 || m >= 10) then 0
elif (n = 0) then 1
elif (n = 1 || m = 1) then 1
elif (n < m) then partitions(n, n)
elif (memo.[n].[m] <> -1) then memo.[n].[m]
else
let result = ([ for i in 1 .. m -> partitions(n - i, i) ] |> List.sum)
printfn "result = %d" result
Array.set memo.[n] m result
result % 7
let rec f = fun n -> if (partitions(n, n) = 0) then n else f(n+1)
let start = fun _ -> printfn "%d" (f 1)
start()
printfn "%A" memo
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.