Skip to content

Instantly share code, notes, and snippets.

@davidgrenier
Last active August 29, 2015 14:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save davidgrenier/f1f2a5881b8cf4f338c5 to your computer and use it in GitHub Desktop.
Save davidgrenier/f1f2a5881b8cf4f338c5 to your computer and use it in GitHub Desktop.
#if INTERACTIVE
let (++) a b = System.IO.Path.Combine(a, b)
let source = __SOURCE_DIRECTORY__ ++ __SOURCE_FILE__
let args = sprintf "--platform:x86 %s -o:%s" source <| source.Replace("fs", "exe")
System.Diagnostics.Process.Start(System.AppDomain.CurrentDomain.BaseDirectory ++ "fsc", args)
#endif
let time f x =
let ts = System.Diagnostics.Stopwatch.StartNew()
let result = f x
printfn "Took %.3fs" ts.Elapsed.TotalSeconds
result
let inline ffoldi n f state =
let mutable state = state
for i = 0 to n - 1 do
state <- f state i
state
let product values n =
let p = Array.length values
Array.init (pown p n) (fun i ->
(Array.zeroCreate n, i)
|> ffoldi n (fun (result, i') j ->
result.[j] <- values.[i' % p]
result, i' / p
)
|> fst
)
let convolute signals filter =
let m = Array.length signals
let n = Array.length filter
let len = max m n - min m n + 1
Array.init len (fun offset ->
ffoldi n (fun acc i ->
acc + filter.[i] * signals.[m - 1 - offset - i]
) 0
)
let go () =
let n = 6
let iters = 1000
let next =
time (fun () ->
let arrays =
product [|-1; 0; 0; 1|] n
|> Array.filter (Array.forall ((=) 0) >> not)
let rnd = System.Random()
fun () -> arrays.[rnd.Next arrays.Length]
) ()
let signals = product [|-1; 1|] (n + 1)
let firstzero, bothzero =
ffoldi signals.Length (fun (firstzero, bothzero) i ->
let s = signals.[i]
ffoldi iters (fun (first, both) _ ->
let f = next()
match convolute s f with
| [|0; 0|] -> first + 1, both + 1
| [|0; _|] -> first + 1, both
| _ -> first, both
) (firstzero, bothzero)
) (0, 0)
printfn "firstzero %i" firstzero
printfn "bothzero %i" bothzero
[<EntryPoint>]
let main _ =
time go ()
0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment