3 choices

evaluation.fsx

let rng = System.Random()

// first interpretation: flip coins,
// and keep only the ones where heads (=0)
// until there is only 1 left.
let rec Strategy1 (rolls:int, choices:int list) =
    match choices with
    | [] -> failwith "unexpected"
    | [x] -> rolls, x // only one result left: done
    | _ -> 
        let count = List.length choices
        let flips = choices |> List.map (fun _ -> rng.Next(0,2) = 0)
        let remaining = 
            choices 
            |> List.zip flips
            |> List.filter fst
            |> List.map snd
        let remaining =
            if remaining = List.empty 
            then choices // nothing left: try again
            else remaining     
        Strategy1 (rolls + count, remaining)            

// second interpretation: flip 3 coins,
// if there is 1 head, that's the choice,
// if there is 1 tail, that's the choice,
// otherwise try again.
let rec Strategy2 (rolls:int) =
    let rolls = rolls + 3
    // 3 coin tosses
    let tosses = Array.init 3 (fun _ -> rng.Next(0,2) = 0)
    let heads = tosses |> Seq.filter id |> Seq.length
    let tails = 3 - heads
    if heads = 1
    then (tosses |> Array.findIndex id, rolls)
    elif tails = 1
    then (tosses |> Array.findIndex (not), rolls)
    else Strategy2 rolls    
    
// my approach: flip 2 coins, encode the 4
// possible results. The 4th possibility indicates
// 'try again'
let rec Strategy3 (rolls:int) =
    
    let first = rng.Next(0,2)
    let second = rng.Next(0,2)
    let rolls = rolls + 2
    match (first,second) with
    | 0,0 -> (1,rolls)
    | 1,0 -> (2,rolls)
    | 0,1 -> (3,rolls)
    | 1,1 -> Strategy3 (rolls)
        
#time "on"
       
// comparison on 10,000 'games'

let games = 10000
let s1Count = [ for _ in 1 .. 10000 -> Strategy1 (0, [1..3]) |> fst |> float ] |> List.average
let s2Count = [ for _ in 1 .. 10000 -> Strategy2 0 |> snd |> float ] |> List.average
let s3Count = [ for _ in 1 .. 10000 -> Strategy3 0 |> snd |> float ] |> List.average

// check results distribution

let s1Dist = [ for _ in 1 .. 10000 -> Strategy1 (0, [1..3]) |> snd ] |> Seq.countBy id |> Seq.toList
let s2Dist = [ for _ in 1 .. 10000 -> Strategy2 0 |> fst ] |> Seq.countBy id |> Seq.toList
let s3Dist = [ for _ in 1 .. 10000 -> Strategy3 0 |> fst ] |> Seq.countBy id |> Seq.toList