ribbons.ml
· 1.3 KiB · OCaml
原始文件
Playground
type open_ribbon = [`Open of int]
type looped_ribbon = [`Looped]
type ribbon =
[
| `Open of int
| `Looped
]
let tie a b : ribbon =
match a, b with
| (`Open x, `Open y) when x == y ->
`Looped
| (`Open x, `Open y) ->
`Open x
let ribbon_id =
let id = ref 0 in
fun () -> incr id; !id
let make_ribbon () =
`Open (ribbon_id ())
let drop f x = f ()
let swap_and_pop dynarray i =
dynarray |> Dynarray.get_last |> Dynarray.set dynarray i ;
dynarray |> Dynarray.remove_last
let loop_ribbons () =
let loops = ref 0 in
let ribbons = Dynarray.init 100 (drop make_ribbon) in
while Dynarray.is_empty ribbons |> not do
let i = ribbons |> Dynarray.length |> Random.int in
let j = ribbons |> Dynarray.length |> Random.int in
match tie (Dynarray.get ribbons i) (Dynarray.get ribbons j) with
| `Open id ->
Dynarray.set ribbons i (`Open id) ;
swap_and_pop ribbons j
| `Looped ->
incr loops ;
swap_and_pop ribbons i ;
done;
!loops
let run_simulations runs =
let acc = ref 0 in
for i = 1 to runs do
acc := !acc + loop_ribbons ()
done;
Float.of_int !acc /. Float.of_int runs
| 1 | type open_ribbon = [`Open of int] |
| 2 | type looped_ribbon = [`Looped] |
| 3 | type ribbon = |
| 4 | [ |
| 5 | | `Open of int |
| 6 | | `Looped |
| 7 | ] |
| 8 | |
| 9 | let tie a b : ribbon = |
| 10 | match a, b with |
| 11 | | (`Open x, `Open y) when x == y -> |
| 12 | `Looped |
| 13 | | (`Open x, `Open y) -> |
| 14 | `Open x |
| 15 | |
| 16 | let ribbon_id = |
| 17 | let id = ref 0 in |
| 18 | fun () -> incr id; !id |
| 19 | |
| 20 | let make_ribbon () = |
| 21 | `Open (ribbon_id ()) |
| 22 | |
| 23 | let drop f x = f () |
| 24 | |
| 25 | let swap_and_pop dynarray i = |
| 26 | dynarray |> Dynarray.get_last |> Dynarray.set dynarray i ; |
| 27 | dynarray |> Dynarray.remove_last |
| 28 | |
| 29 | let loop_ribbons () = |
| 30 | let loops = ref 0 in |
| 31 | let ribbons = Dynarray.init 100 (drop make_ribbon) in |
| 32 | while Dynarray.is_empty ribbons |> not do |
| 33 | let i = ribbons |> Dynarray.length |> Random.int in |
| 34 | let j = ribbons |> Dynarray.length |> Random.int in |
| 35 | match tie (Dynarray.get ribbons i) (Dynarray.get ribbons j) with |
| 36 | | `Open id -> |
| 37 | Dynarray.set ribbons i (`Open id) ; |
| 38 | swap_and_pop ribbons j |
| 39 | | `Looped -> |
| 40 | incr loops ; |
| 41 | swap_and_pop ribbons i ; |
| 42 | done; |
| 43 | !loops |
| 44 | |
| 45 | let run_simulations runs = |
| 46 | let acc = ref 0 in |
| 47 | for i = 1 to runs do |
| 48 | acc := !acc + loop_ribbons () |
| 49 | done; |
| 50 | Float.of_int !acc /. Float.of_int runs |
| 51 |