/* 

  100 coins in Picat.

  From Daniel Litt https://x.com/littmath/status/1835669145943183416
  """
  Flip 100 coins, marked 1-100. Each second, Alice and Bob simultaneously 
  check one coin. Alice goes in order (1, 2, 3, ...; Bob checks the odd coins, 
  then the even (so 1, 3, 5, ..., 99, 2, 4, 6, .... 
  Who is more likely to see 26 total heads *first*?
  * Alice
  * Bob
  * Equally likely
  * Don't know
  """

  The correct answer is Alice:
  https://x.com/littmath/status/1836072843768901879
  """
  This time the answer was Alice! Congrats to the 17% who got it right.
  """

  Calculation:
  https://x.com/RadishHarmers/status/1835858798306635789
  """
  This can be answered in the same way as for the 2 heads case. Alice wins 
  with probability 600,324,422,051,451,511,106,864,339,192 / 2^100, while Bob 
  wins with lesser probability 592,412,163,120,813,120,181,761,789,204 / 2^100.
  """

  * Alice wins
    Picat> X=600324422051451511106864339192 / 2**100
    X = 0.473572467005789


  * Bob wins
    Picat> X=592412163120813120181761789204 / 2**100
    X = 0.467330795263422

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import ppl_distributions, ppl_utils, ppl_common_utils.
import util.
% import ordset.

main => go.

/*
  var : winner
  Probabilities:
  alice: 0.4734666666666666
  bob: 0.4690000000000000
  tie: 0.0575333333333333

*/
go ?=>
  reset_store,
  run_model(30_000,$model,[show_probs_trunc,mean]),
  nl,
  % show_store_lengths,nl,
  % fail,
  nl.
go => true.
  
  
model() =>
  N = 100,
  Target = 26,

  Coins = bern_n(1/2,N),

  % The order they check
  AliceOrder = 1..N,
  BobOrder = 2..2..N ++ 1..2..N,

  AliceCS  = [ Coins[I] : I in AliceOrder].cumsum,
  AlicePos = cond(AliceCS.last >= Target, [ I : I in 1..N, AliceCS[I] == Target],[0]).first,

  BobCS    = [ Coins[I] : I in BobOrder].cumsum,
  BobPos   = cond(BobCS.last >= Target, [ I : I in 1..N, BobCS[I] == Target],[0]).first,

  Winner = cond(AlicePos < BobPos,alice,
                cond(BobPos < AlicePos,
                     bob,
                     tie)),
  add("winner",Winner).