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