include "Tlbx GameplayKit.incl"

_prisoners = 100
_instances = 10000

local fn DrawersArray as CFArrayRef
  long index
  CFMutableArrayRef temp = fn MutableArrayWithCapacity(100)
  for index = 0 to 99
    MutableArrayAddObject( temp, @(index) )
  next
end fn = fn ArrayShuffledArray( temp )


local fn RandomResult( drawers as CFArrayRef ) as BOOL
  long prisoner, i, drawer, total = 0
  MutableIndexSetRef set

  for prisoner = 0 to _prisoners - 1
    set = fn MutableIndexSetInit
    for i = 1 to _prisoners/2
      drawer = rnd(_prisoners)-1
      while ( fn IndexSetContainsIndex( set, intVal( drawers[drawer] ) ) )
        drawer = rnd(_prisoners)-1
      wend
      MutableIndexSetAddIndex( set, intVal( drawers[drawer] ) )
      if ( fn IndexSetContainsIndex( set, prisoner ) )
        total++
        break
      end if
    next
  next
end fn = ( total == _prisoners )


local fn OptimalResult( drawers as CFArrayRef ) as BOOL
  long prisoner, drawer, i, card, total = 0

  for prisoner = 0 to _prisoners - 1
    drawer = prisoner
    for i = 1 to _prisoners/2
      card = intVal( drawers[drawer] )
      if ( card == prisoner )
        total++
        break
      end if
      drawer = card
    next
  next
end fn = ( total == _prisoners )


void local fn DoIt
  static double sTime = 0.0

  block TimerRef timer = timerbegin , 0.001, YES
    sTime += 0.001
    cls
    printf @"Compute time: %.3f\n",sTime
  timerend

  dispatchglobal
    long instance, randomTotal = 0, optimalTotal = 0
    CFArrayRef drawers

    for instance = 1 to _instances
      drawers = fn DrawersArray
      if ( fn RandomResult( drawers ) ) then randomTotal++
      if ( fn OptimalResult( drawers ) ) then optimalTotal++
    next

    dispatchmain
      TimerInvalidate( timer )

      cls
      print @"Prisoners: "_prisoners
      print @"Instances: "_instances
      printf @"Random - fail: %ld, success: %ld (%.2f%%)",_instances-randomTotal,randomTotal,(double)randomTotal/(double)_instances*100.0
      printf @"Optimal - fail: %ld, success: %ld (%.2f%%)\n",_instances-optimalTotal,optimalTotal,(double)optimalTotal/(double)_instances*100.0

      printf @"Compute time: %.3f\n",sTime
    dispatchend

  dispatchend
end fn

random

window 1, @"100 Prisoners"

fn DoIt

HandleEvents