100 prisoners

From Rosetta Code
Task
100 prisoners
You are encouraged to solve this task according to the task description, using any language you may know.


The Problem
  • 100 prisoners are individually numbered 1 to 100
  • A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
  • Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
  • Prisoners start outside the room
  • They can decide some strategy before any enter the room.
  • Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
  • A prisoner can open no more than 50 drawers.
  • A prisoner tries to find his own number.
  • A prisoner finding his own number is then held apart from the others.
  • If all 100 prisoners find their own numbers then they will all be pardoned. If any don't then all sentences stand.


The task
  1. Simulate several thousand instances of the game where the prisoners randomly open drawers
  2. Simulate several thousand instances of the game where the prisoners use the optimal strategy mentioned in the Wikipedia article, of:
  • First opening the drawer whose outside number is his prisoner number.
  • If the card within has his number then he succeeds otherwise he opens the drawer with the same number as that of the revealed card. (until he opens his maximum).


Show and compare the computed probabilities of success for the two strategies, here, on this page.


References
  1. The unbelievable solution to the 100 prisoner puzzle standupmaths (Video).
  2. wp:100 prisoners problem
  3. 100 Prisoners Escape Puzzle DataGenetics.
  4. Random permutation statistics#One hundred prisoners on Wikipedia.



11l[edit]

Translation of: Python
F play_random(n)
   V pardoned = 0
   V in_drawer = Array(0.<100)
   V sampler = Array(0.<100)
   L 0 .< n
      random:shuffle(&in_drawer)
      V found = 0B
      L(prisoner) 100
         found = 0B
         L(reveal) random:sample(sampler, 50)
            V card = in_drawer[reveal]
            I card == prisoner
               found = 1B
               L.break
         I !found
            L.break
      I found
         pardoned++
   R Float(pardoned) / n * 100

F play_optimal(n)
   V pardoned = 0
   V in_drawer = Array(0.<100)
   L 0 .< n
      random:shuffle(&in_drawer)
      V found = 0B
      L(prisoner) 100
         V reveal = prisoner
         found = 0B
         L 50
            V card = in_drawer[reveal]
            I card == prisoner
               found = 1B
               L.break
            reveal = card
         I !found
            L.break
      I found
         pardoned++
   R Float(pardoned) / n * 100

V n = 100'000
print(‘ Simulation count: ’n)
print(‘ Random play wins: #2.1% of simulations’.format(play_random(n)))
print(‘Optimal play wins: #2.1% of simulations’.format(play_optimal(n)))
Output:
 Simulation count: 100000
 Random play wins:  0.0% of simulations
Optimal play wins: 31.1% of simulations

AArch64 Assembly[edit]

Works with: as version Raspberry Pi 3B version Buster 64 bits
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program prisonniex64.s   */ 

/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"

.equ NBDOORS,   100
.equ NBLOOP, 1000

/*********************************/
/* Initialized data              */
/*********************************/
.data
sMessResult:        .asciz "Random strategie  : @ sur 1000 \n"
sMessResultOPT:     .asciz "Optimal strategie : @ sur 1000 \n"
szCarriageReturn:   .asciz "\n"
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:        .skip 24
tbDoors:          .skip 8 * NBDOORS 
tbTest:           .skip 8 * NBDOORS
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                 // entry of program 
    
    ldr x1,qAdrtbDoors
    mov x2,#0
1:                                    // loop init doors table
    add x3,x2,#1
    str x3,[x1,x2,lsl #3]
    add x2,x2,#1
    cmp x2,#NBDOORS
    blt 1b
 
    mov x9,#0                         // loop counter
    mov x10,#0                        // counter successes random strategie
    mov x11,#0                        // counter successes optimal strategie
2:
    ldr x0,qAdrtbDoors
    mov x1,#NBDOORS
    bl knuthShuffle
    
    ldr x0,qAdrtbDoors
    bl aleaStrategie
    cmp x0,#NBDOORS
    cinc x10,x10,eq
    
    ldr x0,qAdrtbDoors
    bl optimaStrategie
    cmp x0,#NBDOORS
    cinc x11,x11,eq
   
    add x9,x9,#1
    cmp x9,#NBLOOP
    blt 2b
    
    mov x0,x10                        // result display
    ldr x1,qAdrsZoneConv
    bl conversion10                   // call decimal conversion
    ldr x0,qAdrsMessResult
    ldr x1,qAdrsZoneConv              // insert conversion in message
    bl strInsertAtCharInc
    bl affichageMess
    
    mov x0,x11                        // result display
    ldr x1,qAdrsZoneConv
    bl conversion10                   // call decimal conversion
    ldr x0,qAdrsMessResultOPT
    ldr x1,qAdrsZoneConv              // insert conversion in message
    bl strInsertAtCharInc
    bl affichageMess
    
100:                                  // standard end of the program 
    mov x0,0                          // return code
    mov x8,EXIT                       // request to exit program
    svc 0                             // perform the system call
 
qAdrszCarriageReturn:     .quad szCarriageReturn
qAdrsMessResult:          .quad sMessResult
qAdrsMessResultOPT:       .quad sMessResultOPT
qAdrtbDoors:              .quad tbDoors
qAdrtbTest:               .quad tbTest
qAdrsZoneConv:            .quad sZoneConv
/******************************************************************/
/*            random door test strategy                           */ 
/******************************************************************/
/* x0 contains the address of table */
aleaStrategie:
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!          // save  registres
    stp x8,x9,[sp,-16]!          // save  registres
    ldr x6,qAdrtbTest            // table doors tests address
    mov x8,x0                    // save table doors address
    mov x4,#0                    // counter number of successes
    mov x2,#0                    // prisonners indice
1:
    bl razTable                  // zero to table doors tests
    mov x5,#0                    // counter of door tests 
    add x7,x2,#1
2:
    mov x0,#1
    mov x1,#NBDOORS
    bl extRandom                 // random test
    ldr x3,[x6,x0,lsl #3]        // doors also tested ?
    cmp x3,#0 
    bne 2b                       // yes
    ldr x3,[x8,x0,lsl #3]        // load N° door
    cmp x3,x7                    // compar N° door N° prisonner
    cinc x4,x4,eq
    beq 3f
    mov x3,#1                    // top test table item 
    str x3,[x6,x0,lsl #3]
    add x5,x5,#1
    cmp x5,#NBDOORS / 2          // number tests maxi ?
    blt 2b                       // no -> loop
3:
    add x2,x2,#1                 // other prisonner
    cmp x2,#NBDOORS
    blt 1b
    
    mov x0,x4                    // return number of successes 
100:
    ldp x8,x9,[sp],16           // restaur des  2 registres
    ldp x6,x7,[sp],16           // restaur des  2 registres
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
/******************************************************************/
/*     raz test table                                             */ 
/******************************************************************/
razTable:
    stp x0,lr,[sp,-16]!        // save  registres
    stp x1,x2,[sp,-16]!        // save  registres
    ldr x0,qAdrtbTest
    mov x1,#0                  // item indice
    mov x2,#0
1:
    str x2,[x0,x1,lsl #3]      // store zero à item
    add x1,x1,#1
    cmp x1,#NBDOORS
    blt 1b
100:
    ldp x1,x2,[sp],16          // restaur des  2 registres
    ldp x0,lr,[sp],16          // restaur des  2 registres
    ret
/******************************************************************/
/*            random door test strategy                           */ 
/******************************************************************/
/* x0 contains the address of table */
optimaStrategie:
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    mov x4,#0                    // counter number of successes
    mov x2,#0                    // counter prisonner
1:
    mov x5,#0                    // counter test
    mov x1,x2                    // first test = N° prisonner
2:
    ldr x3,[x0,x1,lsl #3]        // load N° door
    cmp x3,x2
    cinc x4,x4,eq                // equal -> succes
    beq 3f
    mov x1,x3                    // new test with N° door
    add x5,x5,#1                 
    cmp x5,#NBDOORS / 2          // test number maxi ?
    blt 2b
3:
    add x2,x2,#1                 // other prisonner
    cmp x2,#NBDOORS
    blt 1b
    
    mov x0,x4
100:
    ldp x4,x5,[sp],16          // restaur des  2 registres
    ldp x2,x3,[sp],16          // restaur des  2 registres
    ldp x1,lr,[sp],16          // restaur des  2 registres
    ret
/******************************************************************/
/*     knuth Shuffle                                  */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements */
knuthShuffle:
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!         // save  registers
    mov x5,x0                   // save table address
    mov x6,x1                   // save number of elements
    mov x2,0                    // start index
1:
    mov x0,0
    mov x1,x2                   // generate aleas
    bl extRandom
    ldr x3,[x5,x2,lsl #3]        // swap number on the table
    ldr x4,[x5,x0,lsl #3]
    str x4,[x5,x2,lsl #3]
    str x3,[x5,x0,lsl #3]
    add x2,x2,#1                 // next number
    cmp x2,x6                    // end ?
    blt 1b                       // no -> loop
100:
    ldp x6,x7,[sp],16           // restaur des  2 registres
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret

/******************************************************************/
/*     random number                                          */ 
/******************************************************************/
/*  x0 contains inferior value */
/*  x1 contains maxi value */
/*  x0 return random number */
extRandom:
    stp x1,lr,[sp,-16]!        // save  registers
    stp x2,x8,[sp,-16]!        // save  registers
    stp x3,x4,[sp,-16]!        // save  registers
    stp x19,x20,[sp,-16]!      // save  registers
    sub sp,sp,16               // reserve 16 octets on stack
    mov x19,x0
    add x20,x1,1
    mov x0,sp                  // store result on stack
    mov x1,8                   // length 8 bytes
    mov x2,0
    mov x8,278                 //  call system Linux 64 bits Urandom
    svc 0
    mov x0,sp                  // load résult on stack
    ldr x0,[x0]
    sub x2,x20,x19             // calculation of the range of values 
    udiv x1,x0,x2              // calculation range modulo
    msub x0,x1,x2,x0
    add  x0,x0,x19             // and add inferior value
100:
    add sp,sp,16               // alignement stack 
    ldp x19,x20,[sp],16        // restaur  2 registers
    ldp x3,x4,[sp],16          // restaur  2 registers
    ldp x2,x8,[sp],16          // restaur  2 registers
    ldp x1,lr,[sp],16          // restaur  2 registers
    ret                        // return to address lr x30
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
Random strategie  : 0 sur 1000
Optimal strategie : 305 sur 1000

Ada[edit]

package Prisoners is

   type Win_Percentage is digits 2 range 0.0 .. 100.0;
   type Drawers is array (1 .. 100) of Positive;

   function Play_Game
     (Repetitions : in Positive;
      Strategy    :    not null access function
        (Cupboard     : in Drawers; Max_Prisoners : Integer;
         Max_Attempts :    Integer; Prisoner_Number : Integer) return Boolean)
      return Win_Percentage;
   -- Play the game with a specified number of repetitions, the chosen strategy
   -- is passed to this function

   function Optimal_Strategy
     (Cupboard : in Drawers; Max_Prisoners : Integer; Max_Attempts : Integer;
      Prisoner_Number :    Integer) return Boolean;

   function Random_Strategy
     (Cupboard : in Drawers; Max_Prisoners : Integer; Max_Attempts : Integer;
      Prisoner_Number :    Integer) return Boolean;

end Prisoners;
pragma Ada_2012;
with Ada.Numerics.Discrete_Random;
with Ada.Text_IO; use Ada.Text_IO;

package body Prisoners is

   subtype Drawer_Range is Positive range 1 .. 100;
   package Random_Drawer is new Ada.Numerics.Discrete_Random (Drawer_Range);
   use Random_Drawer;
   
   -- Helper procedures to initialise and shuffle the drawers
   
   procedure Swap (A, B : Positive; Cupboard : in out Drawers) is
      Temp : Positive;
   begin
      Temp         := Cupboard (B);
      Cupboard (B) := Cupboard (A);
      Cupboard (A) := Temp;
   end Swap;

   procedure Shuffle (Cupboard : in out Drawers) is
      G : Generator;
   begin
      Reset (G);
      for I in Cupboard'Range loop
         Swap (I, Random (G), Cupboard);
      end loop;
   end Shuffle;

   procedure Initialise_Drawers (Cupboard : in out Drawers) is
   begin
      for I in Cupboard'Range loop
         Cupboard (I) := I;
      end loop;
      Shuffle (Cupboard);
   end Initialise_Drawers;
   
   -- The two strategies for playing the game

   function Optimal_Strategy
     (Cupboard : in Drawers; Max_Prisoners : Integer; Max_Attempts : Integer;
      Prisoner_Number :    Integer) return Boolean
   is
      Current_Card : Positive;
   begin
      Current_Card := Cupboard (Prisoner_Number);
      if Current_Card = Prisoner_Number then
         return True;
      else
         for I in Integer range 1 .. Max_Attempts loop
            Current_Card := Cupboard (Current_Card);
            if Current_Card = Prisoner_Number then
               return True;
            end if;
         end loop;
      end if;
      return False;
   end Optimal_Strategy;

   function Random_Strategy
     (Cupboard : in Drawers; Max_Prisoners : Integer; Max_Attempts : Integer;
      Prisoner_Number :    Integer) return Boolean
   is
      Current_Card : Positive;
      G            : Generator;
   begin
      Reset (G);
      Current_Card := Cupboard (Prisoner_Number);
      if Current_Card = Prisoner_Number then
         return True;
      else
         for I in Integer range 1 .. Max_Attempts loop
            Current_Card := Cupboard (Random (G));
            if Current_Card = Prisoner_Number then
               return True;
            end if;
         end loop;
      end if;
      return False;
   end Random_Strategy;

   function Prisoners_Attempts
     (Cupboard : in Drawers; Max_Prisoners : Integer; Max_Attempts : Integer;
      Strategy :    not null access function
        (Cupboard     : in Drawers; Max_Prisoners : Integer;
         Max_Attempts :    Integer; Prisoner_Number : Integer) return Boolean)
      return Boolean
   is
   begin
      for Prisoner_Number in Integer range 1 .. Max_Prisoners loop
         if not Strategy
             (Cupboard, Max_Prisoners, Max_Attempts, Prisoner_Number)
         then
            return False;
         end if;
      end loop;
      return True;
   end Prisoners_Attempts;
   
   -- The function to play the game itself

   function Play_Game
     (Repetitions : in Positive;
      Strategy    :    not null access function
        (Cupboard     : in Drawers; Max_Prisoners : Integer;
         Max_Attempts :    Integer; Prisoner_Number : Integer) return Boolean)
      return Win_Percentage
   is
      Cupboard            : Drawers;
      Win, Game_Count     : Natural          := 0;
      Number_Of_Prisoners : constant Integer := 100;
      Max_Attempts        : constant Integer := 50;
   begin
      loop
         Initialise_Drawers (Cupboard);
         if Prisoners_Attempts
             (Cupboard     => Cupboard, Max_Prisoners => Number_Of_Prisoners,
              Max_Attempts => Max_Attempts, Strategy => Strategy)
         then
            Win := Win + 1;
         end if;
         Game_Count := Game_Count + 1;
         exit when Game_Count = Repetitions;
      end loop;
      return Win_Percentage ((Float (Win) / Float (Repetitions)) * 100.0);
   end Play_Game;

end Prisoners;
with Prisoners;   use Prisoners;
with Ada.Text_IO; use Ada.Text_IO;

procedure Main is
   Wins : Win_Percentage;
   package Win_Percentage_IO is new Float_IO (Win_Percentage);
begin
   Wins := Play_Game (100_000, Optimal_Strategy'Access);
   Put ("Optimal Strategy = ");
   Win_Percentage_IO.Put (Wins, 2, 2, 0);
   Put ("%");
   New_Line;
   Wins := Play_Game (100_000, Random_Strategy'Access);
   Put ("Random Strategy = ");
   Win_Percentage_IO.Put (Wins, 2, 2, 0);
   Put ("%");
end Main;
Output:
Optimal Strategy = 31.80%
Random Strategy =  0.00%

APL[edit]

Works with: GNU APL version 1.8
 R  random Nnc; N; n; c
  (N n c)  Nnc
  R  /{∨/=c[n?N]}¨⍳N


 R  follow Nnc; N; n; c; b
  (N n c)  Nnc
  b  n N⍴⍳N
  R  /∨⌿b={⍺⊢c[⍵]}⍀n Nc


 R  M timesSimPrisoners Nn; N; n; m; c; r; s
  (N n)  Nn
  R  0 0
  m  M
  LOOP: cN?N       
  r  random N n c
  s  follow N n c
  R  R + r,s      
  ((mm-1)>0)/LOOP
  R  R ÷ M


5000 timesSimPrisoners 100 50

Applesoft BASIC[edit]

This is modified from the 100_prisoners#Commodore_BASIC listing. Here are some noted differences between the BASICs and platforms:

  • UPPER CASE, for the 1970's Apple II and Apple II+
  • GET in Applesoft waits for a keypress, so : IF K$ = "" THEN 1110 is not needed
  • CLear Screen: PRINT CHR$ (147); on Commodore BASIC, HOME in Applesoft
  • "{LEFT-CRSR}" is CHR$(8) on Apple II, but numbers printed in Applesoft don't have spaces appended to them
  • but spaces need to be added in front and after numbers in Applesoft
  • ; is optional for string concatenation
  • Replace bare PRINT statement with M$ embedded in PRINT statements to visually compact the listing


And, minor speed tweaks:

  • Remove REMs, adjust line numbers, move the two compacted methods to the beginning of the program
  • Rename some two character variable names to single character names: 's/DR(/D(/' 's/IG(/J(/'
  • Start at 0 and go up to 99, but don't regress into off by one bugs
  • Inline the shuffle subroutine and hoist it out of the methods
  • Embed the results in the loop because feedback can be helpful, otherwise it looks like the program froze


Actual test of 4000 trials for each method were run on the KEGSMAC emulator with MHz set to No Limit.

0 GOTO 9

1 FOR X = 0 TO N:J(X) = X: NEXT: FOR I = 0 TO N:FOR X = 0 TO N:T = J(X):NP =  INT ( RND (1) * H):J(X) = J(NP):J(NP) = T: NEXT :FOR G = 1 TO W:IF D(J(G)) = I THEN IP = IP + 1: NEXT I: RETURN 
2 NEXT G:RETURN 

3 FOR I = 0 TO N:NG = I: FOR G = 0 TO W:CD = D(NG):IF CD = I THEN IP = IP + 1: NEXT I: RETURN 
4 NG = CD:IF CD = I THEN STOP
5 NEXT G: RETURN 

9 H=100:N=H-1:DIM D(99),J(99):FOR I = 0 TO N:D(I) = I: NEXT:W=INT(H/2)-1:M$=CHR$(13):M$(1)="RANDOM GUESSING":M$(2)="CHAINED NUMBER PICKING"

1000 FOR Q = 0 TO 1 STEP 0 : HOME : PRINT "100 PRISONERS"M$: INPUT "HOW MANY TRIALS FOR EACH METHOD? ";  TT
1010     VTAB 2:CALL-958:PRINT M$"RESULTS:"M$
1020     FOR M = 1 TO 2: SU(M) = 0:FA(M) = 0
1030         FOR TN = 1 TO TT
1040             VTAB 4:PRINT M$ "   OUT OF " TT " TRIALS, THE RESULTS ARE"M$"   AS FOLLOWS...";
1050             IP = 0: X =  RND ( - TI): FOR I = 0 TO N:R =  INT ( RND (1) * N):T = D(I):D(I) = D(R):D(R) = T: NEXT
1060             ON M GOSUB 1,3 : SU(M) = SU(M) + (IP = H):FA(M) = FA(M) + (IP < H)
1070             FOR Z = 1 TO 2
1071                 PRINT M$M$Z". "M$(Z)":"M$
1073                 PRINT "   "SU(Z)" SUCCESSES"TAB(21)
1074                 PRINT "   "FA(Z)" FAILURES"M$
1075                 PRINT "   "(SU(Z) / TT) * 100"% SUCCESS RATE.";:CALL-868
1090     NEXT Z,TN,M

1100     PRINT M$M$"AGAIN?"
1110     GET K$
1120     Q = K$ <> "Y" AND K$ <> CHR$(ASC("Y") + 32) : NEXT Q
Output:
100 PRISONERS

RESULTS:

   OUT OF 4000 TRIALS, THE RESULTS ARE
   AS FOLLOWS...

1. RANDOM GUESSING:

   0 SUCCESSES         4000 FAILURES

   0% SUCCESS RATE.

2. CHAINED NUMBER PICKING:

   1278 SUCCESSES      2722 FAILURES

   31.95% SUCCESS RATE.

ARM Assembly[edit]

Works with: as version Raspberry Pi
/* ARM assembly Raspberry PI  */
/*  program prisonniers.s   */ 

/* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.inc"

.equ NBDOORS,   100
.equ NBLOOP, 1000

/*********************************/
/* Initialized data              */
/*********************************/
.data
sMessResult:        .asciz "Random strategie  : @ sur 1000 \n"
sMessResultOPT:     .asciz "Optimal strategie : @ sur 1000 \n"
szCarriageReturn:   .asciz "\n"
.align 4
iGraine:  .int 123456
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:        .skip 24
tbDoors:          .skip 4 * NBDOORS 
tbTest:           .skip 4 * NBDOORS
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                 @ entry of program 
    
    ldr r1,iAdrtbDoors
    mov r2,#0
1:                                    @ loop init doors table
    add r3,r2,#1
    str r3,[r1,r2,lsl #2]
    add r2,r2,#1
    cmp r2,#NBDOORS
    blt 1b
 
    mov r9,#0                         @ loop counter
    mov r10,#0                        @ counter successes random strategie
    mov r11,#0                        @ counter successes optimal strategie
2:
    ldr r0,iAdrtbDoors
    mov r1,#NBDOORS
    bl knuthShuffle
    
    ldr r0,iAdrtbDoors
    bl aleaStrategie
    cmp r0,#NBDOORS
    addeq r10,r10,#1
    
    ldr r0,iAdrtbDoors
    bl optimaStrategie
    cmp r0,#NBDOORS
    addeq r11,r11,#1
    
    add r9,r9,#1
    cmp r9,#NBLOOP
    blt 2b
    
    mov r0,r10                        @ result display
    ldr r1,iAdrsZoneConv
    bl conversion10                   @ call decimal conversion
    ldr r0,iAdrsMessResult
    ldr r1,iAdrsZoneConv              @ insert conversion in message
    bl strInsertAtCharInc
    bl affichageMess
    
    mov r0,r11                        @ result display
    ldr r1,iAdrsZoneConv
    bl conversion10                   @ call decimal conversion
    ldr r0,iAdrsMessResultOPT
    ldr r1,iAdrsZoneConv              @ insert conversion in message
    bl strInsertAtCharInc
    bl affichageMess
    
100:                                  @ standard end of the program 
    mov r0, #0                        @ return code
    mov r7, #EXIT                     @ request to exit program
    svc #0                            @ perform the system call
 
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdrsMessResultOPT:        .int sMessResultOPT
iAdrtbDoors:              .int tbDoors
iAdrtbTest:               .int tbTest
iAdrsZoneConv:            .int sZoneConv
/******************************************************************/
/*            random door test strategy                           */ 
/******************************************************************/
/* r0 contains the address of table */
aleaStrategie:
    push {r1-r7,lr}              @ save registers
    ldr r6,iAdrtbTest            @ table doors tests address
    mov r1,r0                    @ save table doors address
    mov r4,#0                    @ counter number of successes
    mov r2,#0                    @ prisonners indice
1:
    bl razTable                  @ zero to table doors tests
    mov r5,#0                    @ counter of door tests 
    add r7,r2,#1
2:
    mov r0,#NBDOORS - 1
    bl genereraleas              @ random test
    add r0,r0,#1
    ldr r3,[r6,r0,lsl #2]        @ doors also tested ?
    cmp r3,#0 
    bne 2b                       @ yes
    ldr r3,[r1,r0,lsl #2]        @ load N° door
    cmp r3,r7                    @ compar N° door N° prisonner
    addeq r4,r4,#1               @ succes
    beq 3f
    mov r3,#1                    @ top test table item 
    str r3,[r6,r0,lsl #2]
    add r5,r5,#1
    cmp r5,#NBDOORS / 2          @ number tests maxi ?
    blt 2b                       @ no -> loop
3:
    add r2,r2,#1                 @ other prisonner
    cmp r2,#NBDOORS
    blt 1b
    
    mov r0,r4                    @ return number of successes 
100:
    pop {r1-r7,lr}
    bx lr                        @ return 
/******************************************************************/
/*     raz test table                                             */ 
/******************************************************************/
razTable:
    push {r0-r2,lr}              @ save registers
    ldr r0,iAdrtbTest
    mov r1,#0                    @ item indice
    mov r2,#0
1:
    str r2,[r0,r1,lsl #2]        @ store zero à item
    add r1,r1,#1
    cmp r1,#NBDOORS
    blt 1b
100:
    pop {r0-r2,lr}
    bx lr                        @ return 
/******************************************************************/
/*            random door test strategy                           */ 
/******************************************************************/
/* r0 contains the address of table */
optimaStrategie:
    push {r1-r7,lr}              @ save registers
    mov r4,#0                    @ counter number of successes
    mov r2,#0                    @ counter prisonner
1:
    mov r5,#0                    @ counter test
    mov r1,r2                    @ first test = N° prisonner
2:
    ldr r3,[r0,r1,lsl #2]        @ load N° door
    cmp r3,r2
    addeq r4,r4,#1               @ equal -> succes
    beq 3f
    mov r1,r3                    @ new test with N° door
    add r5,r5,#1                 
    cmp r5,#NBDOORS / 2          @ test number maxi ?
    blt 2b
3:
    add r2,r2,#1                 @ other prisonner
    cmp r2,#NBDOORS
    blt 1b
    
    mov r0,r4
100:
    pop {r1-r7,lr}
    bx lr                        @ return 
/******************************************************************/
/*     knuth Shuffle                                  */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements */
knuthShuffle:
    push {r2-r5,lr}                   @ save registers
    mov r5,r0                         @ save table address
    mov r2,#0                         @ start index
1:
    mov r0,r2                         @ generate aleas
    bl genereraleas
    ldr r3,[r5,r2,lsl #2]             @ swap number on the table
    ldr r4,[r5,r0,lsl #2]
    str r4,[r5,r2,lsl #2]
    str r3,[r5,r0,lsl #2]
    add r2,#1                         @ next number
    cmp r2,r1                         @ end ?
    blt 1b                            @ no -> loop
100:
    pop {r2-r5,lr}
    bx lr                             @ return 
/***************************************************/
/*   Generation random number                  */
/***************************************************/
/* r0 contains limit  */
genereraleas:
    push {r1-r4,lr}                   @ save registers 
    ldr r4,iAdriGraine
    ldr r2,[r4]
    ldr r3,iNbDep1
    mul r2,r3,r2
    ldr r3,iNbDep1
    add r2,r2,r3
    str r2,[r4]                       @ maj de la graine pour l appel suivant 
    cmp r0,#0
    beq 100f
    mov r1,r0                         @ divisor
    mov r0,r2                         @ dividende
    bl division
    mov r0,r3                         @ résult = remainder
  
100:                                  @ end function
    pop {r1-r4,lr}                    @ restaur registers
    bx lr                             @ return
/*****************************************************/
iAdriGraine: .int iGraine
iNbDep1:     .int 0x343FD
iNbDep2:     .int 0x269EC3 
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
Random strategie  : 0           sur 1000
Optimal strategie : 303         sur 1000

AutoHotkey[edit]

NumOfTrials := 20000
randomFailTotal := 0, strategyFailTotal := 0
prisoners := [], drawers := [], Cards := []
loop, 100
	prisoners[A_Index] := A_Index				; create prisoners
	, drawers[A_Index] := true				; create drawers

loop, % NumOfTrials
{
	loop, 100
		Cards[A_Index] := A_Index			; create cards for this iteration
	loop, 100
	{
		Random, rnd, 1, Cards.count()
		drawers[A_Index] := Cards.RemoveAt(rnd)		; randomly place cards in drawers
	}
	;-------------------------------------------
	; randomly open drawers
	RandomList := []
	loop, 100
		RandomList[A_Index] := A_Index
	Fail := false
	while (A_Index <=100) && !Fail
	{
		thisPrisoner := A_Index
		res := ""
		while (thisCard <> thisPrisoner) && !Fail
		{
			Random, rnd, 1, % RandomList.Count()	; choose random number
			NextDrawer := RandomList.RemoveAt(rnd)	; remove drawer from random list (don't choose more than once)
			thisCard := drawers[NextDrawer]		; get card from this drawer
			if (A_Index > 50)
				Fail := true
		}
		if Fail
			randomFailTotal++
	}
	;-------------------------------------------
	; use optimal strategy
	Fail := false
	while (A_Index <=100) && !Fail
	{
		counter := 1, thisPrisoner := A_Index
		NextDrawer := drawers[thisPrisoner]		; 1st trial, drawer whose outside number is prisoner number
		while (drawers[NextDrawer] <> thisPrisoner) && !Fail
		{	
			NextDrawer := drawers[NextDrawer]	; drawer with the same number as that of the revealed card
			if ++counter > 50
				Fail := true
		}
		if Fail
			strategyFailTotal++
	}
}
MsgBox %  "Number Of Trials = " NumOfTrials
		. "`nOptimal Strategy:`t" (1 - strategyFailTotal/NumOfTrials) *100 " % success rate" 
		. "`nRandom Trials:`t" (1 - randomFailTotal/NumOfTrials) *100 " % success rate"
Outputs:
Number Of Trials = 20000
Optimal Strategy:	33.275000 % success rate
Random Trials   :	0.000000 % success rate

BASIC256[edit]

Works with: BASIC256 version 2.0.0.11
O = 50
N = 2*O
iterations = 10000

REM From the numbers 0 to N-1 inclusive, pick O of them.
function shuffle(N, O)
 dim array(N)
 for i = 0 to N-1
  array[i] = i
 next i
 for i = 0 to O-1
  swapindex = i + rand*(N-i)
  swapvalue = array[swapindex]
  array[swapindex] = array[i]
  array[i] = swapvalue
 next i
 return array
end function

REM given N drawers with O to open, prisoner P chooses randomly: does he choose well?
function chooserandom(drawers, N, O, p)
  choices = shuffle(N, O)
  for i = 0 to O-1
   if drawers[choices[i]] = p then return true
  next i
  return false
end function

REM N prisoners randomly choose O drawers to open: do they all choose well?
function allchooserandom(N, O)
 drawers = shuffle(N, N)
 for p = 0 to N-1
  goodchoice = chooserandom(drawers, N, O, p)
  if not goodchoice then return false
 next p
 return true
end function

REM given N drawers with O to open, prisoner P chooses smartly: does he choose well?
function choosesmart(drawers, N, O, p)
 numopened = 0
 i = p
 while numopened < O
  numopened += 1
  if drawers[i] = p then return true
  i = drawers[i]
 end while
 return false
end function

REM N prisoners smartly choose O drawers to open: do they all choose well?
function allchoosesmart(N, O)
 drawers = shuffle(N, N)
 for p = 0 to N-1
  goodchoice = choosesmart(drawers, N, O, p)
  if not goodchoice then return false
 next p
 return true
end function

cls
print N; " prisoners choosing ";O;" drawers, ";iterations;" iterations:"

total = 0
for iteration = 1 to iterations
 if allchooserandom(N, O) then total += 1
next iteration

print "Random choices: "; total;" out of ";iterations
print "Observed ratio: "; total/iterations; ", expected ratio: "; (O/N)^N

total = 0
for iteration = 1 to iterations
 if allchoosesmart(N, O) then total += 1
next iteration

print "Smart choices: "; total;" out of ";iterations
print "Observed ratio: "; total/iterations; ", expected ratio with N=2*O: greater than about 0.30685": REM for N=100, O=50 particularly, about 0.3118
Output:
100 prisoners choosing 50 drawers, 10000 iterations:
Random choices: 0 out of 10000
Observed ratio: 0.0, expected ratio: 0.0
Smart choices: 3052 out of 10000
Observed ratio: 0.3052, expected ratio with N=2*O: greater than about 0.30685

BCPL[edit]

get "libhdr"

manifest $( 
    seed = 12345   // for pseudorandom number generator
    size = 100     // amount of drawers and prisoners
    tries = 50     // amount of tries each prisoner may make
    simul = 2000   // amount of simulations to run
$)

let randto(n) = valof
$(  static $( state = seed $)
    let mask = 1
    mask := (mask<<1)|1 repeatuntil mask > n
    state := random(state) repeatuntil ((state >> 8) & mask) < n 
    resultis (state >> 8) & mask
$)

// initialize drawers
let placeCards(d, n) be
$(  for i=0 to n-1 do d!i := i;
    for i=0 to n-2 do
    $(  let j = i+randto(n-i)
        let k = d!i
        d!i := d!j
        d!j := k
    $)
$)

// random strategy (prisoner 'p' tries to find his own number)
let randoms(d, p, t) = valof
$(  for n = 1 to t do
        if d!randto(size) = p then resultis true
    resultis false 
$)

// optimal strategy
let optimal(d, p, t) = valof
$(  let last = p
    for n = 1 to t do
        test d!last = p 
            then resultis true
            else last := d!last
    resultis false
$)

// run a simulation given a strategy
let simulate(d, strat, n, t) = valof
$(  placeCards(d, n)
    for p = 0 to n-1 do
        if not strat(d, p, t) then resultis false
    resultis true
$)

// run many simulations and count the successes
let runSimulations(d, strat, n, amt, t) = valof
$(  let succ = 0
    for i = 1 to amt do
        if simulate(d, strat, n, t) do
            succ := succ + 1
    resultis succ
$)

let run(d, name, strat, n, amt, t) be
$(  let s = runSimulations(d, strat, n, amt, t);
    writef("%S: %I5 of %I5, %N percent.*N", name, s, amt, s*10/(amt/10))
$)

let start() be
$(  let d = vec size-1
    run(d, " Random", randoms, size, simul, tries)
    run(d, "Optimal", optimal, size, simul, tries)
$)
Output:
 Random:     0 of  2000, 0 percent.
Optimal:   698 of  2000, 34 percent.

C[edit]

#include<stdbool.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>

#define LIBERTY false
#define DEATH true

typedef struct{
	int cardNum;
	bool hasBeenOpened;
}drawer;

drawer *drawerSet;

void initialize(int prisoners){
	int i,j,card;
	bool unique;

	drawerSet = ((drawer*)malloc(prisoners * sizeof(drawer))) -1;

	card = rand()%prisoners + 1;
	drawerSet[1] = (drawer){.cardNum = card, .hasBeenOpened = false};

	for(i=1 + 1;i<prisoners + 1;i++){
		unique = false;
		while(unique==false){
			for(j=0;j<i;j++){
				if(drawerSet[j].cardNum == card){
					card = rand()%prisoners + 1;
					break;
				}
			}
			if(j==i){
				unique = true;
			}
		}
		drawerSet[i] = (drawer){.cardNum = card, .hasBeenOpened = false};
	}

}

void closeAllDrawers(int prisoners){
	int i;
	for(i=1;i<prisoners + 1;i++)
		drawerSet[i].hasBeenOpened = false;
}

bool libertyOrDeathAtRandom(int prisoners,int chances){
	int i,j,chosenDrawer;

	for(i= 1;i<prisoners + 1;i++){
		bool foundCard = false;
		for(j=0;j<chances;j++){
			do{
				chosenDrawer = rand()%prisoners + 1;
			}while(drawerSet[chosenDrawer].hasBeenOpened==true);
			if(drawerSet[chosenDrawer].cardNum == i){
				foundCard = true;
				break;
			}
			drawerSet[chosenDrawer].hasBeenOpened = true;
		}
		closeAllDrawers(prisoners);
		if(foundCard == false)
			return DEATH;
	}

	return LIBERTY;
}

bool libertyOrDeathPlanned(int prisoners,int chances){
	int i,j,chosenDrawer;
	for(i=1;i<prisoners + 1;i++){
		chosenDrawer = i;
		bool foundCard = false;
		for(j=0;j<chances;j++){
			drawerSet[chosenDrawer].hasBeenOpened = true;

			if(drawerSet[chosenDrawer].cardNum == i){
				foundCard = true;
				break;
			}
			if(chosenDrawer == drawerSet[chosenDrawer].cardNum){
				do{
                    chosenDrawer = rand()%prisoners + 1;
				}while(drawerSet[chosenDrawer].hasBeenOpened==true);
			}
			else{
				chosenDrawer = drawerSet[chosenDrawer].cardNum;
			}

		}

		closeAllDrawers(prisoners);
		if(foundCard == false)
			return DEATH;
	}

	return LIBERTY;
}

int main(int argc,char** argv)
{
	int prisoners, chances;
	unsigned long long int trials,i,count = 0;
        char* end;

	if(argc!=4)
		return printf("Usage : %s <Number of prisoners> <Number of chances> <Number of trials>",argv[0]);

	prisoners = atoi(argv[1]);
	chances = atoi(argv[2]);
	trials = strtoull(argv[3],&end,10);

	srand(time(NULL));

	printf("Running random trials...");
	for(i=0;i<trials;i+=1L){
		initialize(prisoners);

		count += libertyOrDeathAtRandom(prisoners,chances)==DEATH?0:1;
	}

	printf("\n\nGames Played : %llu\nGames Won : %llu\nChances : %lf %% \n\n",trials,count,(100.0*count)/trials);

        count = 0;

	printf("Running strategic trials...");
	for(i=0;i<trials;i+=1L){
		initialize(prisoners);

		count += libertyOrDeathPlanned(prisoners,chances)==DEATH?0:1;
	}

	printf("\n\nGames Played : %llu\nGames Won : %llu\nChances : %lf %% \n\n",trials,count,(100.0*count)/trials);
	return 0;
}
$ gcc 100prisoners.c && ./a.out 100 50 10000
Running random trials...

Games Played : 10000
Games Won : 0
Chances : 0.000000 % 

Running strategic trials...

Games Played : 10000
Games Won : 3051
Chances : 30.510000 % 

C#[edit]

Translation of: D
using System;
using System.Linq;

namespace Prisoners {
    class Program {
        static bool PlayOptimal() {
            var secrets = Enumerable.Range(0, 100).OrderBy(a => Guid.NewGuid()).ToList();

            for (int p = 0; p < 100; p++) {
                bool success = false;

                var choice = p;
                for (int i = 0; i < 50; i++) {
                    if (secrets[choice] == p) {
                        success = true;
                        break;
                    }
                    choice = secrets[choice];
                }

                if (!success) {
                    return false;
                }
            }

            return true;
        }

        static bool PlayRandom() {
            var secrets = Enumerable.Range(0, 100).OrderBy(a => Guid.NewGuid()).ToList();

            for (int p = 0; p < 100; p++) {
                var choices = Enumerable.Range(0, 100).OrderBy(a => Guid.NewGuid()).ToList();

                bool success = false;
                for (int i = 0; i < 50; i++) {
                    if (choices[i] == p) {
                        success = true;
                        break;
                    }
                }

                if (!success) {
                    return false;
                }
            }

            return true;
        }

        static double Exec(uint n, Func<bool> play) {
            uint success = 0;
            for (uint i = 0; i < n; i++) {
                if (play()) {
                    success++;
                }
            }
            return 100.0 * success / n;
        }

        static void Main() {
            const uint N = 1_000_000;
            Console.WriteLine("# of executions: {0}", N);
            Console.WriteLine("Optimal play success rate: {0:0.00000000000}%", Exec(N, PlayOptimal));
            Console.WriteLine(" Random play success rate: {0:0.00000000000}%", Exec(N, PlayRandom));
        }
    }
}
Output:
# of executions: 1000000
Optimal play success rate: 31.21310000000%
 Random play success rate: 0.00000000000%

C++[edit]

#include <cstdlib>   // for rand
#include <algorithm> // for random_shuffle
#include <iostream>  // for output

using namespace std;

class cupboard {
public:
    cupboard() {
        for (int i = 0; i < 100; i++)
            drawers[i] = i;
        random_shuffle(drawers, drawers + 100);
    }

    bool playRandom();
    bool playOptimal();

private:
    int drawers[100];
};

bool cupboard::playRandom() {
    bool openedDrawers[100] = { 0 };
    for (int prisonerNum = 0; prisonerNum < 100; prisonerNum++) { // loops through prisoners numbered 0 through 99
        bool prisonerSuccess = false;
        for (int i = 0; i < 100 / 2; i++) {  // loops through 50 draws for each prisoner
            int drawerNum = rand() % 100;
            if (!openedDrawers[drawerNum]) {
                openedDrawers[drawerNum] = true;
                break;
            }
            if (drawers[drawerNum] == prisonerNum) {
                prisonerSuccess = true;
                break;
            }
        }
        if (!prisonerSuccess)
            return false;
    }
    return true;
}

bool cupboard::playOptimal() {
    for (int prisonerNum = 0; prisonerNum < 100; prisonerNum++) {
        bool prisonerSuccess = false;
        int checkDrawerNum = prisonerNum;
        for (int i = 0; i < 100 / 2; i++) {
            if (drawers[checkDrawerNum] == prisonerNum) {
                prisonerSuccess = true;
                break;
            } else
                checkDrawerNum = drawers[checkDrawerNum];
        }
        if (!prisonerSuccess)
            return false;
    }
    return true;
}

double simulate(char strategy) {
    int numberOfSuccesses = 0;
    for (int i = 0; i < 10000; i++) {
        cupboard d;
        if ((strategy == 'R' && d.playRandom()) || (strategy == 'O' && d.playOptimal())) // will run playRandom or playOptimal but not both because of short-circuit evaluation
            numberOfSuccesses++;
    }

    return numberOfSuccesses * 100.0 / 10000;
}

int main() {
    cout << "Random strategy:  " << simulate('R') << " %" << endl;
    cout << "Optimal strategy: " << simulate('O') << " %" << endl;
    system("PAUSE"); // for Windows
    return 0;
}
Output:
Random strategy:  0 %
Optimal strategy: 31.54 %

Clojure[edit]

(ns clojure-sandbox.prisoners)

(defn random-drawers []
  "Returns a list of shuffled numbers"
  (-> 100
      range
      shuffle))

(defn search-50-random-drawers [prisoner-number drawers]
  "Select 50 random drawers and return true if the prisoner's number was found"
  (->> drawers
      shuffle ;; Put drawer contents in random order
      (take 50) ;; Select first 50, equivalent to selecting 50 random drawers
      (filter (fn [x] (= x prisoner-number))) ;; Filter to include only those that match prisoner number
      count
      (= 1))) ;; Returns true if the number of matching numbers is 1

(defn search-50-optimal-drawers [prisoner-number drawers]
  "Open 50 drawers according to the agreed strategy, returning true if prisoner's number was found"
  (loop [next-drawer prisoner-number ;; The drawer index to start on is the prisoner's number
         drawers-opened 0] ;; To keep track of how many have been opened as 50 is the maximum
    (if (= drawers-opened 50)
      false ;; If 50 drawers have been opened, the prisoner's number has not been found
      (let [result (nth drawers next-drawer)] ;; Open the drawer given by next number
        (if (= result prisoner-number) ;; If prisoner number has been found
          true ;; No need to keep opening drawers - return true
          (recur result (inc drawers-opened))))))) ;; Restart the loop using the resulting number as the drawer number

(defn try-luck [drawers drawer-searching-function]
  "Returns 1 if all prisoners find their number otherwise 0"
  (loop [prisoners (range 100)] ;; Start with 100 prisoners
    (if (empty? prisoners) ;; If they've all gone and found their number
      1 ;; Return true- they'll all live
      (let [res (-> prisoners
                    first
                    (drawer-searching-function drawers))] ;; Otherwise, have the first prisoner open drawers according to the specified method
        (if (false? res) ;; If this prisoner didn't find their number
          0 ;; no prisoners will be freed so we can return false and stop
          (recur (rest prisoners))))))) ;; Otherwise they've found the number, so we remove them from the queue and repeat with the others

(defn simulate-100-prisoners []
  "Simulates all prisoners searching the same drawers by both strategies, returns map showing whether each was successful"
  (let [drawers (random-drawers)] ;; Create 100 drawers with randomly ordered prisoner numbers
    {:random (try-luck drawers search-50-random-drawers) ;; True if all prisoners found their number using random strategy
     :optimal (try-luck drawers search-50-optimal-drawers)})) ;; True if all prisoners found their number using optimal strategy

(defn simulate-n-runs [n]
  "Simulate n runs of the 100 prisoner problem and returns a success count for each search method"
  (loop [random-successes 0
         optimal-successes 0
         run-count 0]
    (if (= n run-count) ;; If we've done the loop n times
      {:random-successes random-successes ;; return results
       :optimal-successes optimal-successes
       :run-count run-count}
      (let [next-result (simulate-100-prisoners)] ;; Otherwise, run for another batch of prisoners
        (recur (+ random-successes (:random next-result)) ;; Add result of run to the total successs count
               (+ optimal-successes (:optimal next-result))
               (inc run-count)))))) ;; increment run count and run again

(defn -main [& args]
  "For 5000 runs, print out the success frequency for both search methods"
  (let [{:keys [random-successes optimal-successes run-count]} (simulate-n-runs 5000)]
    (println (str "Probability of survival with random search: " (float (/ random-successes run-count))))
    (println (str "Probability of survival with ordered search: " (float (/ optimal-successes run-count))))))
Output:
Probability of survival with random search: 0.0
Probability of survival with ordered search: 0.3062

CLU[edit]

% This program needs to be merged with PCLU's "misc" library
% to use the random number generator.
%
% pclu -merge $CLUHOME/lib/misc.lib -compile prisoners.clu

% Seed the random number generator with the current time
init_rng = proc ()
    d: date := now()
    seed: int := ((d.hour*60) + d.minute)*60 + d.second
    random$seed(seed)
end init_rng

% Place cards in drawers randomly
make_drawers = proc (n: int) returns (sequence[int])
    d: array[int] := array[int]$predict(1,n)
    
    % place each card in its own drawer
    for i: int in int$from_to(1,n) do
        array[int]$addh(d,i)
    end
    
    % shuffle the cards
    for i: int in int$from_to_by(n,2,-1) do
        j: int := random$next(i)+1
        t: int := d[i]
        d[i] := d[j]
        d[j] := t
    end
    return(sequence[int]$a2s(d))
end make_drawers

% Random strategy
rand_strat = proc (p, tries: int, d: sequence[int]) returns (bool)
    n: int := sequence[int]$size(d)
    for i: int in int$from_to(1,tries) do
        if p = d[random$next(n)+1] then return(true) end
    end
    return(false)
end rand_strat

% Optimal strategy
opt_strat = proc (p, tries: int, d: sequence[int]) returns (bool)
    last: int := p
    for i: int in int$from_to(1,tries) do
        if d[last]=p then return(true) end
        last := d[last]
    end
    return(false)
end opt_strat

% Run one simulation given a strategy
simulate = proc (n, tries: int,
                 strat: proctype (int,int,sequence[int]) returns (bool))
           returns (bool)
    d: sequence[int] := make_drawers(n)
    for p: int in int$from_to(1,n) do
        % If one prisoner fails, they all hang
        if ~strat(p,tries,d) then return(false) end
    end
    return(true)
end simulate

% Run many simulations and count the successes
run_simulations = proc (amount, n, tries: int,
                        strat: proctype (int,int,sequence[int]) returns (bool))
                  returns (int)
    ok: int := 0
    for i: int in int$from_to(1,amount) do
        if simulate(n,tries,strat) then
            ok := ok + 1
        end
    end
    return(ok)
end run_simulations

% Run simulations and show the results
show = proc (title: string,
             amount, n, tries: int,
             strat: proctype (int,int,sequence[int]) returns (bool))
    po: stream := stream$primary_output()
    stream$puts(po, title || ": ")
    
    ok: int := run_simulations(amount, n, tries, strat)
    perc: real := real$i2r(ok)*100.0/real$i2r(amount)
    
    stream$putright(po, int$unparse(ok), 7)
    stream$puts(po, " out of ")
    stream$putright(po, int$unparse(amount), 7)
    stream$putl(po, ", " || f_form(perc, 3, 2) || "%")
end show 

start_up = proc ()
    prisoners   = 100
    tries       = 50
    simulations = 50000
    
    init_rng()

    show(" Random", simulations, prisoners, tries, rand_strat)
    show("Optimal", simulations, prisoners, tries, opt_strat)
end start_up
Output:
 Random:       0 out of   50000, 0.00%
Optimal:   15541 out of   50000, 31.08%

Commodore BASIC[edit]

It should be noted that this is a very time consuming process for a ~1 MHz 8-bit computer. Evaluating 1000 trials of each method with the algorithm below takes about 3.5 hours on the BASIC system clock (TIME$) of a stock NTSC Commodore 64, even with screen blanking. (Screen blanking seems to achieve only a 3% improvement in speed.) Actual test of 4000 trials for each method were run on the VICE emulator with warp speed engaged, otherwise the user would have had to wait a day and a half for results.

Another concern is when the prisoner's number is found. When this happens it becomes unnecessary to use whatever guesses are remaining; we should simply move on to the next prisoner. Furthermore, if any prisoner uses all 50 guesses with no luck, then everyone is out of luck and the trial is over, which means no other prisoner needs to make the attempt.

This potentially could cause problems on the stack with unfinished guessing (or prisoner) loops, especially where stack limits are extremely small however, a few things are happening to prevent this (See C64-Wiki "NEXT: Early Exits..." for reference.):

  1. The prisoner loop, and each prisoner's 50-guesses loop, are contained within a subroutine. The RETURN at the end of either subroutine terminates any unfinished loops and keeps the stack clean.
  2. When the NEXT belonging to loop 'i' is encountered, any inner loops ('g') are terminated.
  3. Similar to above, any new loop using an existing loop's variable terminates the old loop, and any nested loops within it.


The key here is avoiding the use of GOTO as a means of exiting a loop early.

10 rem 100 prisoners
20 rem set arrays
30 rem dr = drawers containing card values
40 rem ig = a list of numbers 1 through 100, shuffled to become the 
41 rem guess sequence for each inmate - method 1
50 dim dr(100),ig(100)
55 rem initialize drawers with own card in each drawer
60 for i=1 to 100:dr(i)=i:next 

1000 print chr$(147);"how many trials for each method";:input tt
1010 for m=1 to 2:su(m)=0:fa(m)=0
1015 for tn=1 to tt
1020 on m gosub 2000,3000
1025 rem ip = number of inmates who passed
1030 if ip=100 then su(m)=su(m)+1
1040 if ip<100 then fa(m)=fa(m)+1
1045 next tn
1055 next m

1060 print chr$(147);"Results:":print
1070 print "Out of";tt;"trials, the results are"
1071 print "as follows...":print
1072 print "1. Random Guessing:"
1073 print "  ";su(1);"successes"
1074 print "  ";fa(1);"failures"
1075 print "  ";su(1)/tn;"{left-crsr}% success rate.":print
1077 print "2. Chained Number Picking:"
1078 print "  ";su(2);"successes"
1079 print "  ";fa(2);"failures"
1080 print "  ";(su(2)/tn)*100;"{left-crsr}% success rate.":print
1100 print:print "Again?"
1110 get k$:if k$="" then 1110
1120 if k$="y" then 1000
1500 end

2000 rem random guessing method
2005 for x=1 to 100:ig(x)=x:next:ip=0:gosub 4000
2007 for i=1 to 100
2010 for x=1 to 100:t=ig(x):np=int(rnd(1)*100)+1:ig(x)=ig(np):ig(np)=t:next
2015 for g=1 to 50
2020 if dr(ig(g))=i then ip=ip+1:next i:return
2025 next g
2030 return

3000 rem chained method
3005 ip=0:gosub 4000
3007 rem iterate through each inmate
3010 fori=1to100
3015 ng=i:forg=1to50
3020 cd=dr(ng)
3025 ifcd=ithenip=ip+1:nexti:return
3030 ifcd<>ithenng=cd
3035 nextg:return

4000 rem shuffle the drawer cards randomly
4010 x=rnd(-ti)
4020 for i=1 to 100
4030 r=int(rnd(1)*100)+1:t=dr(i):dr(i)=dr(r):dr(r)=t:next
4040 return
Output:
Results:

Out of 4000 trials the percentage of
success is as follows...

1. Random Guessing:
   0 successes
   4000 failures
   0% success rate.

2. Chained Number Picking:
   1274 successes
   2726 failures
   31.85% success rate.

Common Lisp[edit]

Translation of: Racket
(defparameter *samples* 10000)
(defparameter *prisoners* 100)
(defparameter *max-guesses* 50)

(defun range (n)
  "Returns a list from 0 to N."
  (loop
     for i below n
     collect i))

(defun nshuffle (list)
  "Returns a shuffled LIST."
  (loop
     for i from (length list) downto 2
     do (rotatef (nth (random i) list)
                 (nth (1- i) list)))
  list)

(defun build-drawers ()
  "Returns a list of shuffled drawers."
  (nshuffle (range *prisoners*)))

(defun strategy-1 (drawers p)
  "Returns T if P is found in DRAWERS under *MAX-GUESSES* using a random strategy."
  (loop
     for i below *max-guesses*
     thereis (= p (nth (random *prisoners*) drawers))))

(defun strategy-2 (drawers p)
  "Returns T if P is found in DRAWERS under *MAX-GUESSES* using an optimal strategy."
  (loop
     for i below *max-guesses*
     for j = p then (nth j drawers)
     thereis (= p (nth j drawers))))

(defun 100-prisoners-problem (strategy &aux (drawers (build-drawers)))
  "Returns T if all prisoners find their number using the given STRATEGY."
  (every (lambda (e) (eql T e))
         (mapcar (lambda (p) (funcall strategy drawers p)) (range *prisoners*))))

(defun sampling (strategy)
  (loop
     repeat *samples*
     for result = (100-prisoners-problem strategy) 
     count result))

(defun compare-strategies ()
  (format t "Using a random strategy in ~4,2F % of the cases the prisoners are free.~%" (* (/ (sampling #'strategy-1) *samples*) 100))
  (format t "Using an optimal strategy in ~4,2F % of the cases the prisoners are free.~%" (* (/ (sampling #'strategy-2) *samples*) 100)))
Output:
CL-USER> (compare-strategies)
Using a random strategy in 0.00 % of the cases the prisoners are free.
Using an optimal strategy in 31.34 % of the cases the prisoners are free.

Cowgol[edit]

include "cowgol.coh";
include "argv.coh";

# Parameters
const Drawers     := 100;   # Amount of drawers (and prisoners)
const Attempts    := 50;    # Amount of attempts a prisoner may make
const Simulations := 2000;  # Amount of simulations to run

typedef NSim is int(0, Simulations);

# Random number generator
record RNG is
    x: uint8;
    a: uint8;
    b: uint8;
    c: uint8;
    state @at(0): int32;
end record;

sub RandomByte(r: [RNG]): (byte: uint8) is 
    r.x := r.x + 1;
    r.a := r.a ^ r.c ^ r.x;
    r.b := r.b + r.a;
    r.c := r.c + (r.b >> 1) ^ r.a;
    byte := r.c;
end sub;

sub RandomUpTo(r: [RNG], limit: uint8): (rslt: uint8) is
    var x: uint8 := 1;
    while x < limit loop
        x := x << 1;
    end loop;
    x := x - 1;
    
    loop
        rslt := RandomByte(r) & x;
        if rslt < limit then
            break;
        end if;
    end loop;
end sub;

# Drawers (though marked 0..99 instead of 1..100)
var drawers: uint8[Drawers];
typedef Drawer is @indexof drawers;
typedef Prisoner is Drawer;

# Place cards randomly in drawers
sub InitDrawers(r: [RNG]) is
    var x: Drawer := 0;
    while x < Drawers loop
        drawers[x] := x;
        x := x + 1;
    end loop;
    
    x := 0;
    while x < Drawers - 1 loop
        var y := x + RandomUpTo(r, Drawers-x);
        var t := drawers[x];
        drawers[x] := drawers[y];
        drawers[y] := t;
        x := x + 1;
    end loop;
end sub;

# A prisoner can apply a strategy and either succeed or not
interface Strategy(p: Prisoner, r: [RNG]): (success: uint8);

# The stupid strategy: open drawers randomly.
sub Stupid implements Strategy is
    # Let's assume the prisoner is smart enough not to reopen an open drawer
    var opened: Drawer[Drawers];
    MemZero(&opened[0], @bytesof opened);
    
    # Open random drawers
    success := 0;
    var triesLeft: uint8 := Attempts;
    while triesLeft != 0 loop
        var d := RandomUpTo(r, Drawers); # grab a random drawer
        if opened[d] != 0 then
            continue; # Ignore it if a drawer was already open
        else
            triesLeft := triesLeft - 1;
            opened[d] := 1;
            if drawers[d] == p then # found it!
                success := 1;
                return;
            end if;
        end if;
    end loop;
end sub;
    
# The optimal strategy: open the drawer for each number
sub Optimal implements Strategy is
    var current := p;
    var triesLeft: uint8 := Attempts;
    success := 0;
    while triesLeft != 0 loop
        current := drawers[current];
        if current == p then
            success := 1;
            return;
        end if;
        triesLeft := triesLeft - 1;
    end loop;
end sub;

# Run a simulation
sub Simulate(s: Strategy, r: [RNG]): (success: uint8) is
    InitDrawers(r); # place cards randomly in drawer
    var p: Prisoner := 0;
    success := 1; # if they all succeed the simulation succeeds
    while p < Drawers loop # but for each prisoner... 
        if s(p, r) == 0 then # if he fails, the simulation fails
            success := 0;
            return;
        end if;
        p := p + 1;
    end loop;
end sub;

# Run an amount of simulations and report the amount of successes
sub Run(n: NSim, s: Strategy, r: [RNG]): (successes: NSim) is
    successes := 0;
    while n > 0 loop
        successes := successes + Simulate(s, r) as NSim;
        n := n - 1;
    end loop;
end sub;

# Initialize RNG with number given on command line (defaults to 0)
var rng: RNG; rng.state := 0;
ArgvInit();
var arg := ArgvNext();
if arg != 0 as [uint8] then
    (rng.state, arg) := AToI(arg);
end if;

sub RunAndPrint(name: [uint8], strat: Strategy) is
    print(name);
    print(" strategy: ");
    var succ := Run(Simulations, strat, &rng) as uint32;
    print_i32(succ);
    print(" out of ");
    print_i32(Simulations);
    print(" - ");
    print_i32(succ * 100 / Simulations);
    print("%\n");
end sub;

RunAndPrint("Stupid", Stupid);
RunAndPrint("Optimal", Optimal);
Output:
Stupid strategy: 0 out of 2000 - 0%
Optimal strategy: 634 out of 2000 - 31%

Crystal[edit]

Based on the Ruby implementation

prisoners = (1..100).to_a
N = 100_000
generate_rooms = ->{ (1..100).to_a.shuffle }

res = N.times.count do
  rooms = generate_rooms.call
  prisoners.all? { |pr| rooms[1, 100].sample(50).includes?(pr) }
end
puts "Random strategy : %11.4f %%" % (res.fdiv(N) * 100)

res = N.times.count do
  rooms = generate_rooms.call
  prisoners.all? do |pr|
    cur_room = pr
    50.times.any? do
      cur_room = rooms[cur_room - 1]
      found = (cur_room == pr)
      found
    end
  end
end
puts "Optimal strategy: %11.4f %%" % (res.fdiv(N) * 100)
Output:
Random strategy :      0.0000 %
Optimal strategy:     31.3190 %

D[edit]

Translation of: Kotlin
import std.array;
import std.random;
import std.range;
import std.stdio;
import std.traits;

bool playOptimal() {
    auto secrets = iota(100).array.randomShuffle();

    prisoner:
    foreach (p; 0..100) {
        auto choice = p;
        foreach (_; 0..50) {
            if (secrets[choice] == p) continue prisoner;
            choice = secrets[choice];
        }
        return false;
    }

    return true;
}

bool playRandom() {
    auto secrets = iota(100).array.randomShuffle();

    prisoner:
    foreach (p; 0..100) {
        auto choices = iota(100).array.randomShuffle();
        foreach (i; 0..50) {
            if (choices[i] == p) continue prisoner;
        }
        return false;
    }

    return true;
}

double exec(const size_t n, bool function() play) {
    size_t success = 0;
    for (int i = n; i > 0; i--) {
        if (play()) {
            success++;
        }
    }
    return 100.0 * success / n;
}

void main() {
    enum N = 1_000_000;
    writeln("# of executions: ", N);
    writefln("Optimal play success rate: %11.8f%%", exec(N, &playOptimal));
    writefln(" Random play success rate: %11.8f%%", exec(N, &playRandom));
}
Output:
# of executions: 1000000
Optimal play success rate: 31.16100000%
 Random play success rate:  0.00000000%

Delphi[edit]

See #Pascal.

EasyLang[edit]

for i range 100
  drawer[] &= i
  sampler[] &= i
.
subr shuffle_drawer
  for i = len drawer[] downto 2
    r = random i
    swap drawer[r] drawer[i - 1]
  .
.
subr play_random
  call shuffle_drawer
  found = 1
  prisoner = 0
  while prisoner < 100 and found = 1
    found = 0
    i = 0
    while i < 50 and found = 0
      r = random (100 - i)
      card = drawer[sampler[r]]
      swap sampler[r] sampler[100 - i - 1]
      if card = prisoner
        found = 1
      .
      i += 1
    .
    prisoner += 1
  .
.
subr play_optimal
  call shuffle_drawer
  found = 1
  prisoner = 0
  while prisoner < 100 and found = 1
    reveal = prisoner
    found = 0
    i = 0
    while i < 50 and found = 0
      card = drawer[reveal]
      if card = prisoner
        found = 1
      .
      reveal = card
      i += 1
    .
    prisoner += 1
  .
.
n = 10000
pardoned = 0
for round range n
  call play_random
  pardoned += found
.
print "random: " & 100.0 * pardoned / n & "%"
# 
pardoned = 0
for round range n
  call play_optimal
  pardoned += found
.
print "optimal: " & 100.0 * pardoned / n & "%"
Output:
random: 0.000%
optimal: 30.800%

Elixir[edit]

Translation of: Ruby
defmodule HundredPrisoners do
  def optimal_room(_, _, _, []), do: []
  def optimal_room(prisoner, current_room, rooms, [_ | tail]) do
    found = Enum.at(rooms, current_room - 1) == prisoner
    next_room = Enum.at(rooms, current_room - 1)
    [found] ++ optimal_room(prisoner, next_room, rooms, tail)
  end

  def optimal_search(prisoner, rooms) do
    Enum.any?(optimal_room(prisoner, prisoner, rooms, Enum.to_list(1..50)))
  end
end

prisoners = 1..100
n = 1..10_000
generate_rooms = fn -> Enum.shuffle(1..100) end

random_strategy = Enum.count(n, 
  fn _ -> 
  rooms = generate_rooms.()
  Enum.all?(prisoners, fn pr -> pr in (rooms |> Enum.take_random(50)) end)
end)

IO.puts "Random strategy: #{random_strategy} / #{n |> Range.size}"

optimal_strategy = Enum.count(n,
  fn _ ->
  rooms = generate_rooms.()
  Enum.all?(prisoners, 
    fn pr -> HundredPrisoners.optimal_search(pr, rooms) end)
end)

IO.puts "Optimal strategy: #{optimal_strategy} / #{n |> Range.size}"
Output:
Random strategy: 0 / 10000
Optimal strategy: 3110 / 10000

F#[edit]

let rnd = System.Random()
let shuffled min max =
    [|min..max|] |> Array.sortBy (fun _ -> rnd.Next(min,max+1))

let drawers () = shuffled 1 100

// strategy randomizing drawer opening
let badChoices (drawers' : int array) =
    Seq.init 100 (fun _ -> shuffled 1 100 |> Array.take 50) // selections for each prisoner
    |> Seq.map (fun indexes -> indexes |> Array.map(fun index -> drawers'.[index-1])) // transform to cards
    |> Seq.mapi (fun i cards -> cards |> Array.contains i) // check if any card matches prisoner number
    |> Seq.contains false // true means not all prisoners got their cards
let outcomeOfRandom runs =
    let pardons = Seq.init runs (fun _ -> badChoices (drawers ()))
                  |> Seq.sumBy (fun badChoice -> if badChoice |> not then 1.0 else 0.0)
    pardons/ float runs
    
// strategy optimizing drawer opening
let smartChoice max prisoner (drawers' : int array) =
    prisoner
    |> Seq.unfold (fun selection ->
        let card = drawers'.[selection-1]
        Some (card, card))
    |> Seq.take max
    |> Seq.contains prisoner
let smartChoices (drawers' : int array) =
    seq { 1..100 }
    |> Seq.map (fun prisoner -> smartChoice 50 prisoner drawers')
    |> Seq.filter (fun result -> result |> not) // remove all but false results
    |> Seq.isEmpty // empty means all prisoners got their cards
let outcomeOfOptimize runs =
    let pardons = Seq.init runs (fun _ -> smartChoices (drawers()))
                  |> Seq.sumBy (fun smartChoice' -> if smartChoice' then 1.0 else 0.0)
    pardons/ float runs
    
printfn $"Using Random Strategy: {(outcomeOfRandom 20000):p2}"
printfn $"Using Optimum Strategy: {(outcomeOfOptimize 20000):p2}"
Output:
Using Random Strategy: 0.00%
Using Optimum Strategy: 31.06%

Factor[edit]

USING: arrays formatting fry io kernel math random sequences ;

: setup ( -- seq seq ) 100 <iota> dup >array randomize ;

: rand ( -- ? )
    setup [ 50 sample member? not ] curry find nip >boolean not ;

: trail ( m seq -- n )
    50 pick '[ [ nth ] keep over _ = ] replicate [ t = ] any?
    2nip ;

: optimal ( -- ? ) setup [ trail ] curry [ and ] map-reduce ;

: simulate ( m quot -- x )
    dupd replicate [ t = ] count swap /f 100 * ; inline

"Simulation count: 10,000" print
10,000 [ rand ] simulate "Random play success: "
10,000 [ optimal ] simulate "Optimal play success: "
[ write "%.2f%%\n" printf ] 2bi@
Output:
Simulation count: 10,000
Random play success: 0.00%
Optimal play success: 31.11%

FOCAL[edit]

01.10 T %5.02," RANDOM";S CU=0
01.20 F Z=1,2000;D 5;S CU=CU+SU
01.30 T CU/20,!,"OPTIMAL";S CU=0
01.40 F Z=1,2000;D 6;S CU=CU+SU
01.50 T CU/20,!
01.60 Q

02.01 C-- PUT CARDS IN RANDOM DRAWERS
02.10 F X=1,100;S D(X)=X
02.20 F X=1,99;D 2.3;S B=D(X);S D(X)=D(A);S D(A)=B
02.30 D 2.4;S A=X+FITR(A*(101-X))
02.40 S A=FABS(FRAN()*10);S A=A-FITR(A)

03.01 C-- PRISONER X TRIES UP TO 50 RANDOM DRAWERS
03.10 S TR=50;S SU=0
03.20 D 2.4;I (X-D(A))3.3,3.4,3.3
03.30 S TR=TR-1;I (TR),3.5,3.2
03.40 S SU=1;R
03.50 S SU=0

04.01 C-- PRISONER X TRIES OPTIMAL METHOD
04.10 S TR=50;S SU=0;S A=X
04.20 I (X-D(A))4.3,4.4,4.3
04.30 S TR=TR-1;S A=D(A);I (TR),4.5,4.2
04.40 S SU=1;R
04.50 S SU=0

05.01 C-- PRISONERS TRY RANDOM METHOD UNTIL ONE FAILS
05.10 D 2;S X=1
05.20 I (X-101)5.3,5.4
05.30 D 3;S X=X+1;I (SU),5.4,5.2
05.40 R

06.01 C-- PRISONERS TRY OPTIMAL METHOD UNTIL ONE FAILS
06.10 D 2;S X=1
06.20 I (X-101)6.3,6.4
06.30 D 4;S X=X+1;I (SU),6.4,6.2
06.40 R
Output:
 RANDOM=   0.00
OPTIMAL=  30.10

Forth[edit]

ANS Forth has no in-built facility for random numbers, but libraries are available.

Works with: ANS Forth

Here is a solution using ran4.seq from The Forth Scientific Library, available here.

Run the two strategies (random and follow the card number) 10,000 times each, and show number or successes.

INCLUDE ran4.seq

100      CONSTANT #drawers
#drawers CONSTANT #players
100000   CONSTANT #tries

CREATE drawers  #drawers CELLS ALLOT                    \ index 0..#drawers-1

: drawer[]                              ( n -- addr )   \ return address of drawer n
    CELLS drawers +
;

: random_drawer                         ( -- n )        \ n=0..#drawers-1 random drawer 
    RAN4 ( d ) XOR ( n ) #drawers MOD
;

: random_drawer[]                       ( -- addr )     \ return address of random drawer
    random_drawer drawer[]
;

: swap_indirect                         ( addr1 addr2 -- )  \ swaps the values at the two addresses
    2DUP @ SWAP @                       ( addr1 addr2 n2 n1 )
    ROT ! SWAP !                        \ store n1 at addr2 and n2 at addr1
;

: init_drawers                          ( -- ) \ shuffle cards into drawers
    #drawers 0 DO
        I I drawer[] !                  \ store cards in order
    LOOP
    #drawers 0 DO
        I drawer[]  random_drawer[]     ( addr-drawer-i addr-drawer-rnd )
        swap_indirect
    LOOP
;

: random_turn                           ( player - f )
    #drawers 2 / 0 DO
		random_drawer 
		drawer[] @ 
		OVER = IF
			DROP TRUE UNLOOP EXIT	\ found his number
		THEN
	LOOP 
	DROP FALSE
;

0 VALUE player

: cycle_turn                            ( player - f )
	DUP TO player			( next-drawer )
    #drawers 2 / 0 DO
		drawer[] @
		DUP player = IF 
			DROP TRUE UNLOOP EXIT	\ found his number
		THEN
	LOOP 
	DROP FALSE
;

: turn                                  ( strategy player - f )
    SWAP 0= IF                          \ random play 
        random_turn
    ELSE
        cycle_turn
    THEN
;

: play                                  ( strategy -- f ) \ return true if prisioners survived
    init_drawers
    #players 0 DO
        DUP I turn
        0= IF
            DROP FALSE UNLOOP EXIT 	\ this player did not survive, UNLOOP, return false
        THEN
    LOOP 
    DROP TRUE                           \ all survived, return true
;

: trie					( strategy - nr-saved )
	0				( strategy nr-saved )
	#tries 0 DO
		OVER play IF 1+ THEN
	LOOP
	NIP
;

0 trie . CR	\ random strategy
1 trie . CR	\ follow the card number strategy

output:

0 
30009 

Fortran[edit]

SUBROUTINE SHUFFLE_ARRAY(INT_ARRAY)
    ! Takes an input array and shuffles the elements by swapping them
    ! in pairs in turn 10 times
    IMPLICIT NONE

    INTEGER, DIMENSION(100), INTENT(INOUT) :: INT_ARRAY
    INTEGER, PARAMETER :: N_PASSES = 10
    ! Local Variables

    INTEGER :: TEMP_1, TEMP_2   ! Temporaries for swapping elements
    INTEGER :: I, J, PASS       ! Indices variables
    REAL :: R                   ! Randomly generator value

    CALL RANDOM_SEED()  ! Seed the random number generator

    DO PASS=1, N_PASSES
        DO I=1, SIZE(INT_ARRAY)

            ! Get a random index to swap with
            CALL RANDOM_NUMBER(R)
            J = CEILING(R*SIZE(INT_ARRAY))

            ! In case generated index value
            ! exceeds array size
            DO WHILE (J > SIZE(INT_ARRAY))
                J = CEILING(R*SIZE(INT_ARRAY))
            END DO

            !  Swap the two elements
            TEMP_1 = INT_ARRAY(I)
            TEMP_2 = INT_ARRAY(J)
            INT_ARRAY(I) = TEMP_2
            INT_ARRAY(J) = TEMP_1
        ENDDO
    ENDDO
END SUBROUTINE SHUFFLE_ARRAY

SUBROUTINE RUN_RANDOM(N_ROUNDS)
    ! Run the 100 prisoner puzzle simulation N_ROUNDS times
    ! in the scenario where each prisoner selects a drawer at random
    IMPLICIT NONE

    INTEGER, INTENT(IN) :: N_ROUNDS ! Number of simulations to run in total

    INTEGER :: ROUND, PRISONER, CHOICE, I       ! Iteration variables
    INTEGER :: N_SUCCESSES                      ! Number of successful trials
    REAL(8) :: TOTAL                            ! Total number of trials as real
    LOGICAL :: NUM_FOUND = .FALSE.              ! Prisoner has found their number

    INTEGER, DIMENSION(100) :: CARDS, CHOICES   ! Arrays representing card allocations
                                                ! to draws and drawer choice order

    ! Both cards and choices are randomly assigned.
    ! This being the drawer (allocation represented by index),
    ! and what drawer to pick for Nth/50 choice
    ! (take first 50 elements of 100 element array)
    CARDS = (/(I, I=1, 100, 1)/)
    CHOICES = (/(I, I=1, 100, 1)/)

    N_SUCCESSES = 0
    TOTAL = REAL(N_ROUNDS)

    ! Run the simulation for N_ROUNDS rounds
    ! when a prisoner fails to find their number
    ! after 50 trials, set that simulation to fail
    ! and start the next round
    ROUNDS_LOOP: DO ROUND=1, N_ROUNDS
        CALL SHUFFLE_ARRAY(CARDS)
        PRISONERS_LOOP: DO PRISONER=1, 100
            NUM_FOUND = .FALSE.
            CALL SHUFFLE_ARRAY(CHOICES)
            CHOICE_LOOP: DO CHOICE=1, 50
                IF(CARDS(CHOICE) == PRISONER) THEN
                    NUM_FOUND = .TRUE.
                    EXIT CHOICE_LOOP
                ENDIF
            ENDDO CHOICE_LOOP
            IF(.NOT. NUM_FOUND) THEN
                EXIT PRISONERS_LOOP
            ENDIF
        ENDDO PRISONERS_LOOP
        IF(NUM_FOUND) THEN
            N_SUCCESSES = N_SUCCESSES + 1
        ENDIF
    ENDDO ROUNDS_LOOP

    WRITE(*, '(A, F0.3, A)') "Random drawer selection method success rate: ", &
        100*N_SUCCESSES/TOTAL, "%"

END SUBROUTINE RUN_RANDOM

SUBROUTINE RUN_OPTIMAL(N_ROUNDS)
    ! Run the 100 prisoner puzzle simulation N_ROUNDS times in the scenario
    ! where each prisoner selects firstly the drawer with their number and then
    ! subsequently the drawer matching the number of the card present 
    ! within that current drawer
    IMPLICIT NONE

    INTEGER, INTENT(IN) :: N_ROUNDS

    INTEGER :: ROUND, PRISONER, CHOICE, I   ! Iteration variables
    INTEGER :: CURRENT_DRAW                 ! ID of the current draw
    INTEGER :: N_SUCCESSES                  ! Number of successful trials
    REAL(8) :: TOTAL                        ! Total number of trials as real
    LOGICAL :: NUM_FOUND = .FALSE.          ! Prisoner has found their number 
    INTEGER, DIMENSION(100) :: CARDS        ! Array representing card allocations

    ! Cards are randomly assigned to a drawer 
    ! (allocation represented by index),
    CARDS = (/(I, I=1, 100, 1)/)

    N_SUCCESSES = 0
    TOTAL = REAL(N_ROUNDS)

    ! Run the simulation for N_ROUNDS rounds
    ! when a prisoner fails to find their number
    ! after 50 trials, set that simulation to fail
    ! and start the next round
    ROUNDS_LOOP: DO ROUND=1, N_ROUNDS
        CARDS = (/(I, I=1, 100, 1)/)
        CALL SHUFFLE_ARRAY(CARDS)
        PRISONERS_LOOP: DO PRISONER=1, 100
            CURRENT_DRAW = PRISONER
            NUM_FOUND = .FALSE.
            CHOICE_LOOP: DO CHOICE=1, 50
                IF(CARDS(CURRENT_DRAW) == PRISONER) THEN
                    NUM_FOUND = .TRUE.
                    EXIT CHOICE_LOOP
                ELSE
                    CURRENT_DRAW = CARDS(CURRENT_DRAW)
                ENDIF
            ENDDO CHOICE_LOOP
            IF(.NOT. NUM_FOUND) THEN
                EXIT PRISONERS_LOOP
            ENDIF
        ENDDO PRISONERS_LOOP
        IF(NUM_FOUND) THEN
            N_SUCCESSES = N_SUCCESSES + 1
        ENDIF
    ENDDO ROUNDS_LOOP
    WRITE(*, '(A, F0.3, A)') "Optimal drawer selection method success rate: ", &
        100*N_SUCCESSES/TOTAL, "%"

END SUBROUTINE RUN_OPTIMAL

PROGRAM HUNDRED_PRISONERS
    ! Run the two scenarios for the 100 prisoners puzzle of random choice
    ! and optimal choice (choice based on drawer contents)
    IMPLICIT NONE
    INTEGER, PARAMETER :: N_ROUNDS = 50000
    WRITE(*,'(A, I0, A)') "Running simulation for ", N_ROUNDS, " trials..."
    CALL RUN_RANDOM(N_ROUNDS)
    CALL RUN_OPTIMAL(N_ROUNDS)
END PROGRAM HUNDRED_PRISONERS

output:

Running simulation for 50000 trials...
Random drawer selection method success rate: .000%
Optimal drawer selection method success rate: 31.360%

FreeBASIC[edit]

#include once "knuthshuf.bas"   'use the routines in https://rosettacode.org/wiki/Knuth_shuffle#FreeBASIC

function gus( i as long, strat as boolean ) as long
    if strat then return i
    return 1+int(rnd*100)
end function

sub trials( byref c_success as long, byref c_fail as long, byval strat as boolean )
        dim as long i, j, k, guess, drawer(1 to 100)
    for i = 1 to 100
        drawer(i) = i
    next i
    for j = 1 to 1000000 'one million trials of prisoners
        knuth_up( drawer() )  'shuffles the cards in the drawers
            for i = 1 to 100 'prisoner number
            guess = gus(i, strat)
            for k = 1 to 50 'each prisoner gets 50 tries
                if drawer(guess) = i then goto next_prisoner
                guess = gus(drawer(guess), strat)
            next k
            c_fail += 1
            goto next_trial
            next_prisoner:
        next i
        c_success += 1
        next_trial:
    next j
end sub

randomize timer
dim as long c_fail=0, c_success=0

trials( c_success, c_fail, false )

print using "For prisoners guessing randomly we had ####### successes and ####### failures.";c_success;c_fail

c_success = 0
c_fail = 0

trials( c_success, c_fail, true )

print using "For prisoners using the strategy we had ####### successes and ####### failures.";c_success;c_fail


FutureBasic[edit]

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
Output:
Prisoners: 100
Instances: 10000
Random - fail: 10000, success: 0 (0.00%)
Optimal - fail: 6896, success: 3104 (31.04%)

Compute time: 7.856

Gambas[edit]

Implementation of the '100 Prisoners' program written in VBA. Tested in Gambas 3.15.2

' Gambas module file

Public DrawerArray As Long[]
Public NumberFromDrawer As Long
Public FoundOwnNumber As Long

Public Sub Main()
  
  Dim NumberOfPrisoners As Long
  Dim Selections As Long
  Dim Tries As Long
  
  Print "Number of prisoners (default, 100)?"
  Try Input NumberOfPrisoners
  If Error Then NumberOfPrisoners = 100
  
  Print "Number of selections (default, half of prisoners)?" 
  Try Input Selections
  If Error Then Selections = NumberOfPrisoners / 2
  
  Print "Number of tries (default, 1000)?"
  Try Input Tries
  If Error Then Tries = 1000
  
  Dim AllFoundOptimal As Long = 0
  Dim AllFoundRandom As Long = 0
  Dim AllFoundRandomMem As Long = 0
  
  Dim i As Long
  Dim OptimalCount As Long
  Dim RandomCount As Long
  Dim RandomMenCount As Long
  
  Dim fStart As Float = Timer
  
  For i = 1 To Tries
    OptimalCount = HundredPrisoners_Optimal(NumberOfPrisoners, Selections)
    RandomCount = HundredPrisoners_Random(NumberOfPrisoners, Selections)
    RandomMenCount = HundredPrisoners_Random_Mem(NumberOfPrisoners, Selections)
    
    If OptimalCount = NumberOfPrisoners Then AllFoundOptimal += 1
    If RandomCount = NumberOfPrisoners Then AllFoundRandom += 1
    If RandomMenCount = NumberOfPrisoners Then AllFoundRandomMem += 1
  Next
  
  Dim fTime As Float = Timer - fStart
  fTime = Round(ftime, -1)
  
  Print
  Print "Result with " & NumberOfPrisoners & " prisoners, " & Selections & " selections and " & Tries & " tries. "
  Print
  Print "Optimal: " & AllFoundOptimal & " of " & Tries & ": " & Str(AllFoundOptimal / Tries * 100) & " %"
  Print "Random: " & AllFoundRandom & " of " & Tries & ": " & Str(AllFoundRandom / Tries * 100) & " %"
  Print "RandomMem: " & AllFoundRandomMem & " of " & Tries & ": " & Str(AllFoundRandomMem / Tries * 100) & " %"
  Print
  Print "Elapsed Time: " & fTime & " sec"
  Print
  Print "Trials/sec: " & Round(Tries / fTime, -1)
  
End

Function HundredPrisoners_Optimal(NrPrisoners As Long, NrSelections As Long) As Long
  
  DrawerArray = New Long[NrPrisoners]
  Dim Counter As Long
  
  For Counter = 0 To DrawerArray.Max
    DrawerArray[Counter] = Counter + 1
  Next
  
  DrawerArray.Shuffle()
  
  Dim i As Long
  Dim j As Long
  FoundOwnNumber = 0
  
  For i = 1 To NrPrisoners
    For j = 1 To NrSelections
      If j = 1 Then NumberFromDrawer = DrawerArray[i - 1]
      
      If NumberFromDrawer = i Then
        FoundOwnNumber += 1
        Break
      Endif
      NumberFromDrawer = DrawerArray[NumberFromDrawer - 1]
    Next
  Next
  Return FoundOwnNumber
  
End

Function HundredPrisoners_Random(NrPrisoners As Long, NrSelections As Long) As Long
  
  Dim RandomDrawer As Long
  Dim Counter As Long
  
  DrawerArray = New Long[NrPrisoners]
  
  For Counter = 0 To DrawerArray.Max
    DrawerArray[Counter] = Counter + 1
  Next
  
  DrawerArray.Shuffle()
  
  Dim i As Long
  Dim j As Long
  FoundOwnNumber = 0
  
  Randomize
  
  For i = 1 To NrPrisoners
    For j = 1 To NrSelections
      RandomDrawer = CLong(Rand(NrPrisoners - 1))
      NumberFromDrawer = DrawerArray[RandomDrawer]
      If NumberFromDrawer = i Then
        FoundOwnNumber += 1
        Break
      Endif
    Next
  Next
  Return FoundOwnNumber
  
End

Function HundredPrisoners_Random_Mem(NrPrisoners As Long, NrSelections As Long) As Long
  
  Dim SelectionArray As New Long[NrPrisoners]
  Dim Counter As Long
  
  DrawerArray = New Long[NrPrisoners]
  
  For Counter = 0 To DrawerArray.Max
    DrawerArray[Counter] = Counter + 1
    
  Next
  
  For Counter = 0 To SelectionArray.Max
    SelectionArray[Counter] = Counter + 1
    
  Next
  
  DrawerArray.Shuffle()
  
  Dim i As Long
  Dim j As Long
  FoundOwnNumber = 0
  
  For i = 1 To NrPrisoners
    SelectionArray.Shuffle()
    For j = 1 To NrSelections
      NumberFromDrawer = DrawerArray[SelectionArray[j - 1] - 1]
      If NumberFromDrawer = i Then
        FoundOwnNumber += 1
        Break
      Endif
      NumberFromDrawer = DrawerArray[NumberFromDrawer - 1]
    Next
  Next
  Return FoundOwnNumber
  
End
Output:
Number of prisoners (default, 100)?
100
Number of selections (default, half of prisoners)?
50
Number of tries (default, 1000)?


Result with 100 prisoners, 50 selections and 1000 tries. 

Optimal: 311 of 1000: 31,1 %
Random: 0 of 1000: 0 %
RandomMem: 0 of 1000: 0 %

Elapsed Time: 8.7 sec

Trials/sec: 114.9


Go[edit]

package main

import (
    "fmt"
    "math/rand"
    "time"
)

// Uses 0-based numbering rather than 1-based numbering throughout.
func doTrials(trials, np int, strategy string) {
    pardoned := 0
trial:
    for t := 0; t < trials; t++ {
        var drawers [100]int
        for i := 0; i < 100; i++ {
            drawers[i] = i
        }
        rand.Shuffle(100, func(i, j int) {
            drawers[i], drawers[j] = drawers[j], drawers[i]
        })
    prisoner:
        for p := 0; p < np; p++ {
            if strategy == "optimal" {
                prev := p
                for d := 0; d < 50; d++ {
                    this := drawers[prev]
                    if this == p {
                        continue prisoner
                    }
                    prev = this
                }
            } else {
                // Assumes a prisoner remembers previous drawers (s)he opened
                // and chooses at random from the others.
                var opened [100]bool
                for d := 0; d < 50; d++ {
                    var n int
                    for {
                        n = rand.Intn(100)
                        if !opened[n] {
                            opened[n] = true
                            break
                        }
                    }
                    if drawers[n] == p {
                        continue prisoner
                    }
                }
            }
            continue trial
        }
        pardoned++
    }
    rf := float64(pardoned) / float64(trials) * 100
    fmt.Printf("  strategy = %-7s  pardoned = %-6d relative frequency = %5.2f%%\n\n", strategy, pardoned, rf)
}

func main() {
    rand.Seed(time.Now().UnixNano())
    const trials = 100000
    for _, np := range []int{10, 100} {
        fmt.Printf("Results from %d trials with %d prisoners:\n\n", trials, np)
        for _, strategy := range [2]string{"random", "optimal"} {
            doTrials(trials, np, strategy)
        }
    }
}
Output:
Results from 100000 trials with 10 prisoners:

  strategy = random   pardoned = 99     relative frequency =  0.10%

  strategy = optimal  pardoned = 31205  relative frequency = 31.20%

Results from 100000 trials with 100 prisoners:

  strategy = random   pardoned = 0      relative frequency =  0.00%

  strategy = optimal  pardoned = 31154  relative frequency = 31.15%

Groovy[edit]

Translation of: Java
import java.util.function.Function
import java.util.stream.Collectors
import java.util.stream.IntStream

class Prisoners {
    private static boolean playOptimal(int n) {
        List<Integer> secretList = IntStream.range(0, n).boxed().collect(Collectors.toList())
        Collections.shuffle(secretList)

        prisoner:
        for (int i = 0; i < secretList.size(); ++i) {
            int prev = i
            for (int j = 0; j < secretList.size() / 2; ++j) {
                if (secretList.get(prev) == i) {
                    continue prisoner
                }
                prev = secretList.get(prev)
            }
            return false
        }
        return true
    }

    private static boolean playRandom(int n) {
        List<Integer> secretList = IntStream.range(0, n).boxed().collect(Collectors.toList())
        Collections.shuffle(secretList)

        prisoner:
        for (Integer i : secretList) {
            List<Integer> trialList = IntStream.range(0, n).boxed().collect(Collectors.toList())
            Collections.shuffle(trialList)

            for (int j = 0; j < trialList.size() / 2; ++j) {
                if (Objects.equals(trialList.get(j), i)) {
                    continue prisoner
                }
            }

            return false
        }
        return true
    }

    private static double exec(int n, int p, Function<Integer, Boolean> play) {
        int succ = 0
        for (int i = 0; i < n; ++i) {
            if (play.apply(p)) {
                succ++
            }
        }
        return (succ * 100.0) / n
    }

    static void main(String[] args) {
        final int n = 100_000
        final int p = 100
        System.out.printf("# of executions: %d\n", n)
        System.out.printf("Optimal play success rate: %f%%\n", exec(n, p, Prisoners.&playOptimal))
        System.out.printf("Random play success rate: %f%%\n", exec(n, p, Prisoners.&playRandom))
    }
}
Output:
# of executions: 100000
Optimal play success rate: 31.215000%
Random play success rate: 0.000000%

Haskell[edit]

import System.Random
import Control.Monad.State

numRuns        = 10000
numPrisoners   = 100
numDrawerTries = 50
type Drawers   = [Int]
type Prisoner  =  Int
type Prisoners = [Int]

main = do
  gen <- getStdGen
  putStrLn $ "Chance of winning when choosing randomly: "  ++ (show $ evalState runRandomly gen)
  putStrLn $ "Chance of winning when choosing optimally: " ++ (show $ evalState runOptimally gen)


runRandomly :: State StdGen Double
runRandomly =
  let runResults = replicateM numRuns $ do
         drawers <- state $ shuffle [1..numPrisoners]
         allM (\prisoner -> openDrawersRandomly drawers prisoner numDrawerTries) [1..numPrisoners]
   in  ((/ fromIntegral numRuns) . fromIntegral . sum . map fromEnum) `liftM` runResults

openDrawersRandomly :: Drawers -> Prisoner -> Int -> State StdGen Bool
openDrawersRandomly drawers prisoner triesLeft = go triesLeft []
  where go 0 _ = return False
        go triesLeft seenDrawers = do
          try <- state $ randomR (1, numPrisoners)
          case try of
            x | x == prisoner        -> return True
              | x `elem` seenDrawers -> go triesLeft seenDrawers
              | otherwise            -> go (triesLeft - 1) (x:seenDrawers)

runOptimally :: State StdGen Double
runOptimally =
  let runResults = replicateM numRuns $ do
         drawers <- state $ shuffle [1..numPrisoners]
         return $ all (\prisoner -> openDrawersOptimally drawers prisoner numDrawerTries) [1..numPrisoners]
   in  ((/ fromIntegral numRuns) . fromIntegral . sum . map fromEnum) `liftM` runResults

openDrawersOptimally :: Drawers -> Prisoner -> Int -> Bool
openDrawersOptimally drawers prisoner triesLeft = go triesLeft prisoner
  where go 0 _ = False
        go triesLeft drawerToTry =
          let thisDrawer = drawers !! (drawerToTry - 1)
           in if thisDrawer == prisoner then True else go (triesLeft - 1) thisDrawer


-- Haskel stdlib is lacking big time, so here some necessary 'library' functions

-- make a list of 'len' random values in range 'range' from 'gen'
randomLR :: Integral a => Random b => a -> (b, b) -> StdGen -> ([b], StdGen)
randomLR 0 range gen = ([], gen)
randomLR len range gen =
  let (x, newGen) = randomR range gen
      (xs, lastGen) = randomLR (len - 1) range newGen
  in (x : xs, lastGen)


-- shuffle a list by a generator
shuffle :: [a] -> StdGen -> ([a], StdGen)
shuffle list gen = (shuffleByNumbers numbers list, finalGen)
  where
    n = length list
    (numbers, finalGen) = randomLR n (0, n-1) gen
    shuffleByNumbers :: [Int] -> [a] -> [a]
    shuffleByNumbers [] _ = []
    shuffleByNumbers _ [] = []
    shuffleByNumbers (i:is) xs = let (start, x:rest) = splitAt (i `mod` length xs) xs
                                 in x : shuffleByNumbers is (start ++ rest)

-- short-circuit monadic all
allM :: Monad m => (a -> m Bool) -> [a] -> m Bool
allM func [] = return True
allM func (x:xs) = func x >>= \res -> if res then allM func xs else return False
Output:
Chance of winning when choosing randomly: 0.0
Chance of winning when choosing optimally: 0.3188

J[edit]

NB. game is solvable by optimal strategy when the length (#) of the
NB. longest (>./) cycle (C.) is at most 50.
opt=: 50 >: [: >./ [: > [: #&.> C.

NB. for each prisoner randomly open 50 boxes ((50?100){y) and see if 
NB. the right card is there (p&e.). if not return 0.
rand=: monad define
for_p. i.100 do. if. -.p e.(50?100){y do. 0 return. end.
end. 1
)

NB. use both strategies on the same shuffles y times.
simulate=: monad define
'o r'=. y %~ 100 * +/ ((rand,opt)@?~)"0 y # 100
('strategy';'win rate'),('random';(":o),'%'),:'optimal';(":r),'%'
)
Output:
   simulate 10000000
┌────────┬────────┐
│strategy│win rate│
├────────┼────────┤
│random  │0%      │
├────────┼────────┤
│optimal │31.1816%│
└────────┴────────┘

Janet[edit]

(math/seedrandom (os/cryptorand 8))

(defn drawers
  "create list and shuffle it"
  [prisoners]
  (var x (seq [i :range [0 prisoners]] i))
  (loop [i :down [(- prisoners 1) 0]]
    (var j (math/floor (* (math/random) (+ i 1))))
    (var k (get x i))
    (put x i (get x j))
    (put x j k))
  x)

(defn optimal-play
  "optimal decision path"
  [prisoners drawers]
  (var result 0)
  (loop [i :range [0 prisoners]]
    (var choice i)
    (loop [j :range [0 50] :until (= (get drawers choice) i)]
      (set choice (get drawers choice)))
    (cond
      (= (get drawers choice) i) (++ result)
      (break)))
  result)

(defn random-play
  "random decision path"
  [prisoners d]
  (var result 0)
  (var options (drawers prisoners))
  (loop [i :range [0 prisoners]]
    (var choice 0)
    (loop [j :range [0 (/ prisoners 2)] :until (= (get d j) (get options i))]
      (set choice j))
    (cond
      (= (get d choice) (get options i)) (++ result)
      (break)))
  result)

(defn main [& args]
  (def prisoners 100)
  (var optimal-success 0)
  (var random-success 0)
  (var sims 10000)
  (for i 0 sims
    (var d (drawers prisoners))
    (if (= (optimal-play prisoners d) prisoners)
      (++ optimal-success))
    (if (= (random-play prisoners d) prisoners)
      (++ random-success)))
  (printf "Simulation count:  %d" sims)
  (printf "Optimal play wins: %.1f%%" (* (/ optimal-success sims) 100))
  (printf "Random play wins:  %.1f%%" (* (/ random-success sims) 100)))

Output:

Simulation count:  10000
Optimal play wins: 33.1%
Random play wins:  0.0%

Java[edit]

Translation of: Kotlin
import java.util.Collections;
import java.util.List;
import java.util.Objects;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    private static boolean playOptimal(int n) {
        List<Integer> secretList = IntStream.range(0, n).boxed().collect(Collectors.toList());
        Collections.shuffle(secretList);

        prisoner:
        for (int i = 0; i < secretList.size(); ++i) {
            int prev = i;
            for (int j = 0; j < secretList.size() / 2; ++j) {
                if (secretList.get(prev) == i) {
                    continue prisoner;
                }
                prev = secretList.get(prev);
            }
            return false;
        }
        return true;
    }

    private static boolean playRandom(int n) {
        List<Integer> secretList = IntStream.range(0, n).boxed().collect(Collectors.toList());
        Collections.shuffle(secretList);

        prisoner:
        for (Integer i : secretList) {
            List<Integer> trialList = IntStream.range(0, n).boxed().collect(Collectors.toList());
            Collections.shuffle(trialList);

            for (int j = 0; j < trialList.size() / 2; ++j) {
                if (Objects.equals(trialList.get(j), i)) {
                    continue prisoner;
                }
            }

            return false;
        }
        return true;
    }

    private static double exec(int n, int p, Function<Integer, Boolean> play) {
        int succ = 0;
        for (int i = 0; i < n; ++i) {
            if (play.apply(p)) {
                succ++;
            }
        }
        return (succ * 100.0) / n;
    }

    public static void main(String[] args) {
        final int n = 100_000;
        final int p = 100;
        System.out.printf("# of executions: %d\n", n);
        System.out.printf("Optimal play success rate: %f%%\n", exec(n, p, Main::playOptimal));
        System.out.printf("Random play success rate: %f%%\n", exec(n, p, Main::playRandom));
    }
}
Output:
# of executions: 100000
Optimal play success rate: 31.343000%
Random play success rate: 0.000000%

JavaScript[edit]

Translation of: C#
Works with: Node.js
const _ = require('lodash');

const numPlays = 100000;

const setupSecrets = () => {
	// setup the drawers with random cards
	let secrets = [];

	for (let i = 0; i < 100; i++) {
		secrets.push(i);
	}

	return _.shuffle(secrets);
}

const playOptimal = () => {
	
	let secrets = setupSecrets();
	

	// Iterate once per prisoner
	loop1:
	for (let p = 0; p < 100; p++) {
		
		// whether the prisoner succeedss
		let success = false;
		
		// the drawer number the prisoner chose
		let choice = p;
		
		
		// The prisoner can choose up to 50 cards
		loop2:
		for (let i = 0; i < 50; i++) {
			
			// if the card in the drawer that the prisoner chose is his card
			if (secrets[choice] === p){
				success = true;
				break loop2;
			}

			// the next drawer the prisoner chooses will be the number of the card he has.
			choice = secrets[choice];
		
		}	// each prisoner gets 50 chances

		
		if (!success) return false;

	} // iterate for each prisoner 

	return true;
}

const playRandom = () => {

	let secrets = setupSecrets();

	// iterate for each prisoner 
	for (let p = 0; p < 100; p++) {

		let choices = setupSecrets();
		
		let success = false;
		
		for (let i = 0; i < 50; i++) {

			if (choices[i] === p) {
				success = true;
				break;
			}
		}

		if (!success) return false;
	}

	return true;
}

const execOptimal = () => {

	let success = 0;
	
	for (let i = 0; i < numPlays; i++) {

		if (playOptimal()) success++;
			
	}

	return 100.0 * success / 100000;
}

const execRandom = () => {

	let success = 0;

	for (let i = 0; i < numPlays; i++) {

		if (playRandom()) success++;

	}

	return 100.0 * success / 100000;
}

console.log("# of executions: " + numPlays);
console.log("Optimal Play Success Rate: " + execOptimal());
console.log("Random Play Success Rate: " + execRandom());

School example[edit]

Works with: JavaScript version Node.js 16.13.0 (LTS)
"use strict";

// Simulate several thousand instances of the game:
const gamesCount = 2000;

// ...where the prisoners randomly open drawers.
const randomResults = playGame(gamesCount, randomStrategy);

// ...where the prisoners use the optimal strategy mentioned in the Wikipedia article.
const optimalResults = playGame(gamesCount, optimalStrategy);

// Show and compare the computed probabilities of success for the two strategies.
console.log(`Games count: ${gamesCount}`);
console.log(`Probability of success with "random" strategy: ${computeProbability(randomResults, gamesCount)}`);
console.log(`Probability of success with "optimal" strategy: ${computeProbability(optimalResults, gamesCount)}`);

function playGame(gamesCount, strategy, prisonersCount = 100) {
    const results = new Array();

    for (let game = 1; game <= gamesCount; game++) {
        // A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
        // Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
        const drawers = initDrawers(prisonersCount);

        // A prisoner tries to find his own number.
        // Prisoners start outside the room.
        // They can decide some strategy before any enter the room.
        let found = 0;
        for (let prisoner = 1; prisoner <= prisonersCount; prisoner++, found++)
            if (!find(prisoner, drawers, strategy)) break;

        // If all 100 findings find their own numbers then they will all be pardoned. If any don't then all sentences stand.
        results.push(found == prisonersCount);
    }

    return results;
}

function find(prisoner, drawers, strategy) {
    // A prisoner can open no more than 50 drawers.
    const openMax = Math.floor(drawers.length / 2);

    // Prisoners start outside the room.
    let card;
    for (let open = 0; open < openMax; open++) {
        // A prisoner tries to find his own number.
        card = strategy(prisoner, drawers, card);

        // A prisoner finding his own number is then held apart from the others.
        if (card == prisoner)
            break;
    }

    return (card == prisoner);
}

function randomStrategy(prisoner, drawers, card) {
    // Simulate the game where the prisoners randomly open drawers.

    const min = 0;
    const max = drawers.length - 1;

    return drawers[draw(min, max)];
}

function optimalStrategy(prisoner, drawers, card) {
    // Simulate the game where the prisoners use the optimal strategy mentioned in the Wikipedia article.

    // First opening the drawer whose outside number is his prisoner number.
    // If the card within has his number then he succeeds...
    if (typeof card === "undefined")
        return drawers[prisoner - 1];
   
    // ...otherwise he opens the drawer with the same number as that of the revealed card.
    return drawers[card - 1];
}

function initDrawers(prisonersCount) {
    const drawers = new Array();
    for (let card = 1; card <= prisonersCount; card++)
        drawers.push(card);

    return shuffle(drawers);
}

function shuffle(drawers) {
    const min = 0;
    const max = drawers.length - 1;
    for (let i = min, j; i < max; i++)     {
        j = draw(min, max);
        if (i != j)
            [drawers[i], drawers[j]] = [drawers[j], drawers[i]];
    }

    return drawers;
}

function draw(min, max) {
    // See: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function computeProbability(results, gamesCount) {
    return Math.round(results.filter(x => x == true).length * 10000 / gamesCount) / 100;
}

Output:

Games count: 2000
Probability of success with "random" strategy: 0
Probability of success with "optimal" strategy: 33.2

jq[edit]

Works with: jq

jq does not have a built-in PRNG and so the jq program used here presupposes an external source of entropy such as /dev/urandom. The output shown below was obtained by invoking jq as follows:

export LC_ALL=C
< /dev/urandom tr -cd '0-9' | fold -w 1 | jq -MRcnr -f 100-prisoners.jq

In the following jq program:

  • `np` is the number of prisoners
  • the number of drawers is `np` and the maximum number of draws per prisoner is `np/2|floor`

Preliminaries

def count(s): reduce s as $x (0; .+1);

# Output: a PRN in range(0;$n) where $n is .
def prn:
  if . == 1 then 0
  else . as $n
  | (($n-1)|tostring|length) as $w
  | [limit($w; inputs)] | join("") | tonumber
  | if . < $n then . else ($n | prn) end
  end;

def knuthShuffle:
  length as $n
  | if $n <= 1 then .
    else {i: $n, a: .}
    | until(.i ==  0;
        .i += -1
        | (.i + 1 | prn) as $j
        | .a[.i] as $t
        | .a[.i] = .a[$j]
        | .a[$j] = $t)
    | .a 
    end;

np Prisoners

# Output: if all the prisoners succeed, emit true, otherwise false
def optimalStrategy($drawers; np):
  # Does prisoner $p succeed?
  def succeeds($p):
    first( foreach range(0; np/2) as $d ({prev: $p};
             .curr = ($drawers[.prev])
             | if .curr == $p
               then .success = true
               else .prev = .curr
               end;
             select(.success))) // false;
  
  all( range(0; np); succeeds(.) );
  
# Output: if all the prisoners succeed, emit true, otherwise false
def randomStrategy($drawers; np):
  (np/2) as $maxd
  # Does prisoner $p succeed?
  | def succeeds($p):
      {success: false }
      | first(.d = 0
              | .opened = []
              | until( (.d >= $maxd) or .success;
                  (np|prn) as $n
                  | if .opened[$n] then .
                    else .opened[$n] = true
                    | .d += 1
                    | .success = $drawers[$n] == $p
                    end )
              | select(.success) ) // false;

  all( range(0; np); succeeds(.) );


def run(strategy; trials; np):
  count(range(0; trials)
    | ([range(0;np)] | knuthShuffle) as $drawers
    | select (if strategy == "optimal"
              then optimalStrategy($drawers; np)
              else randomStrategy($drawers; np)
              end ) );

def task($trials):
  def percent: "\(10000 * . | round / 100)%";
  def summary(strategy):
    "With \(strategy) strategy: pardoned = \(.), relative frequency = \(./$trials | percent)";

  (10, 100) as $np
  | "Results from \($trials) trials with \($np) prisoners:",
    (run("random";  $trials; $np) | summary("random")),
    (run("optimal"; $trials; $np) | summary("optimal")),
    ""
;

task(100000)
Output:
Results from 100000 trials with 10 prisoners:
With random strategy: pardoned = 92, relative frequency = 0.09%
With optimal strategy: pardoned = 31212, relative frequency = 31.21%

Results from 100000 trials with 100 prisoners:
With random strategy: pardoned = 0, relative frequency = 0%
With optimal strategy: pardoned = 31026, relative frequency = 31.03%

Julia[edit]

Translation of: Python
using Random, Formatting

function randomplay(n, numprisoners=100)
    pardoned, indrawer, found = 0, collect(1:numprisoners), false
    for i in 1:n
        shuffle!(indrawer)
        for prisoner in 1:numprisoners
            found = false
            for reveal in randperm(numprisoners)[1:div(numprisoners, 2)]
                indrawer[reveal] == prisoner && (found = true) && break
            end
            !found && break
        end
        found && (pardoned += 1)
    end
    return 100.0 * pardoned / n
end

function optimalplay(n, numprisoners=100)
    pardoned, indrawer, found = 0, collect(1:numprisoners), false
    for i in 1:n
        shuffle!(indrawer)
        for prisoner in 1:numprisoners
            reveal = prisoner
            found = false
            for j in 1:div(numprisoners, 2)
                card = indrawer[reveal]
                card == prisoner && (found = true) && break
                reveal = card
            end
            !found && break
        end
        found && (pardoned += 1)
    end
    return 100.0 * pardoned / n
 end

const N = 100_000
println("Simulation count: $N")
println("Random play wins: ", format(randomplay(N), precision=8), "% of simulations.")
println("Optimal play wins: ", format(optimalplay(N), precision=8), "% of simulations.")
Output:
Simulation count: 100000
Random play wins: 0.00000000% of simulations.
Optimal play wins: 31.18100000% of simulations.

Kotlin[edit]

val playOptimal: () -> Boolean = {
    val secrets = (0..99).toMutableList()
    var ret = true
    secrets.shuffle()
    prisoner@ for(i in 0 until 100){
        var prev = i
        draw@ for(j in 0 until  50){
            if (secrets[prev] == i) continue@prisoner
            prev = secrets[prev]
        }
        ret = false
        break@prisoner
    }
    ret
}

val playRandom: ()->Boolean = {
    var ret = true
    val secrets = (0..99).toMutableList()
    secrets.shuffle()
    prisoner@ for(i in 0 until 100){
        val opened = mutableListOf<Int>()
        val genNum : () ->Int = {
            var r = (0..99).random()
            while (opened.contains(r)) {
                r = (0..99).random()
            }
            r
        }
        for(j in 0 until 50){
            val draw = genNum()
            if ( secrets[draw] == i) continue@prisoner
            opened.add(draw)
        }
        ret = false
        break@prisoner
    }
    ret
}

fun exec(n:Int, play:()->Boolean):Double{
    var succ = 0
    for (i in IntRange(0, n-1)){
        succ += if(play()) 1 else 0
    }
    return (succ*100.0)/n
}

fun main() {
    val N = 100_000
    println("# of executions: $N")
    println("Optimal play success rate: ${exec(N, playOptimal)}%")
    println("Random play success rate: ${exec(N, playRandom)}%")
}
Output:
# of executions: 100000
Optimal play success rate: 31.451%
Random play success rate: 0.0%

Lua[edit]

Translation of: lang
function shuffle(tbl)
  for i = #tbl, 2, -1 do
    local j = math.random(i)
    tbl[i], tbl[j] = tbl[j], tbl[i]
  end
  return tbl
end

function playOptimal()
    local secrets = {}
    for i=1,100 do
        secrets[i] = i
    end
    shuffle(secrets)

    for p=1,100 do
        local success = false

        local choice = p
        for i=1,50 do
            if secrets[choice] == p then
                success = true
                break
            end
            choice = secrets[choice]
        end

        if not success then
            return false
        end
    end

    return true
end

function playRandom()
    local secrets = {}
    for i=1,100 do
        secrets[i] = i
    end
    shuffle(secrets)

    for p=1,100 do
        local choices = {}
        for i=1,100 do
            choices[i] = i
        end
        shuffle(choices)

        local success = false
        for i=1,50 do
            if choices[i] == p then
                success = true
                break
            end
        end

        if not success then
            return false
        end
    end

    return true
end

function exec(n,play)
    local success = 0
    for i=1,n do
        if play() then
            success = success + 1
        end
    end
    return 100.0 * success / n
end

function main()
    local N = 1000000
    print("# of executions: "..N)
    print(string.format("Optimal play success rate: %f", exec(N, playOptimal)))
    print(string.format("Random play success rate: %f", exec(N, playRandom)))
end

main()
Output:
# of executions: 1000000
Optimal play success rate: 31.237500
Random play success rate: 0.000000

Maple[edit]

Don"t bother to simulate the random method: each prisoner has a probability p to win with:

p:=simplify(1-product(1-1/(2*n-k),k=0..n-1));
# p=1/2

Since all prisoners' attempts are independent, the probability that they all win is:

p^100;
evalf(%);

# 1/1267650600228229401496703205376
# 7.888609052e-31

Even with billions of simulations, chances are we won't find even one successful escape.

On the other hand, if they try the optimal strategy, then their success is governed by the cycle decomposition of the permutation of numbers in boxes. That is, the function f(i)=j where i is the number on the box, and j the number in the box, is a permutation of 1..100. This permutation has a cycle decomposition. It's not difficult to see that all prisoners with a number in the same cycle, need the same number of attempts before finding their number, and it's the cycle length. Hence, for all prisoners to escape, the maximum cycle length must not exceed 50.

Here is a simulation based on this, assuming that the permutation of numbers in boxes is random:

a:=[seq(max(GroupTheory[PermCycleType](Perm(Statistics[Shuffle]([$1..100])))),i=1..100000)]:
nops(select(n->n<=50,a))/nops(a);
evalf(%);
# 31239/100000
# 0.3123900000

The probability of success is now better than 30%, which is far better than the random approach.

It can be proved that the probability with the second strategy is in fact:

1-(harmonic(100)-harmonic(50));
evalf(%);

# 21740752665556690246055199895649405434183/69720375229712477164533808935312303556800
# 0.3118278207

Mathematica/Wolfram Language[edit]

ClearAll[PlayRandom, PlayOptimal]
PlayRandom[n_] := 
 Module[{pardoned = 0, sampler, indrawer, found, reveal},
  sampler = indrawer = Range[100];
  Do[
   indrawer //= RandomSample;
   found = 0;
   Do[
    reveal = RandomSample[sampler, 50];
    If[MemberQ[indrawer[[reveal]], p],
     found++;
     ]
    ,
    {p, 100}
    ];
   If[found == 100, pardoned++];
   ,
   {n}
   ];
  N[pardoned/n]
  ]
PlayOptimal[n_] := 
 Module[{pardoned = 0, indrawer, reveal, found, card},
  indrawer = Range[100];
  Do[
   indrawer //= RandomSample;
   Do[
    reveal = p;
    found = False;
    Do[
     card = indrawer[[reveal]];
     If[card == p,
      found = True;
      Break[];
      ];
     reveal = card;
     ,
     {g, 50}
     ];
    If[! found, Break[]];
    ,
    {p, 100}
    ];
   If[found, pardoned++];
   ,
   {n}
   ];
  N[pardoned/n]
  ];
PlayRandom[1000]
PlayOptimal[10000]
Output:
0.
0.3116

MATLAB[edit]

function [randSuccess,idealSuccess]=prisoners(numP,numG,numT)
    %numP is the number of prisoners
    %numG is the number of guesses
    %numT is the number of trials
    randSuccess=0;
    
    %Random
    for trial=1:numT
        drawers=randperm(numP);
        won=1;
        for i=1:numP
            correct=0;
            notopened=drawers;
            for j=1:numG
                ind=randi(numel(notopened));
                m=notopened(ind);
                if m==i
                    correct=1;
                    break;
                end
                notopened(ind)=[];
            end
            if correct==0
                won=0;
                break;
            end
        end
        randSuccess=randSuccess*(trial-1)/trial+won/trial;
    end
    

    %Ideal
    idealSuccess=0;

    for trial=1:numT
        drawers=randperm(numP);
        won=1;
        for i=1:numP
            correct=0;
            guess=i;
            for j=1:numG
                m=drawers(guess);
                if m==i
                    correct=1;
                    break;
                end
                guess=m;
            end
            if correct==0
                won=0;
                break;
            end
        end
        idealSuccess=idealSuccess*(trial-1)/trial+won/trial;
    end
    disp(['Probability of success with random strategy: ' num2str(randSuccess*100) '%']);
    disp(['Probability of success with ideal strategy: ' num2str(idealSuccess*100) '%']);
end
Output:
>> [randSuccess,idealSuccess]=prisoners(100,50,10000);
Probability of success with random strategy: 0%
Probability of success with ideal strategy: 31.93%

MiniScript[edit]

Translation of: Python
playRandom = function(n)
    // using 0-99 instead of 1-100
    pardoned = 0
    numInDrawer = range(99)
    choiceOrder = range(99)
    for round in range(1, n)
    	numInDrawer.shuffle
        choiceOrder.shuffle
        for prisoner in range(99)
            found = false
            for card in choiceOrder[:50]
                if card == prisoner then
                    found = true
                    break
                end if
            end for
            if not found then break
        end for
        if found then pardoned = pardoned + 1
    end for
    return pardoned / n * 100
end function

playOptimal = function(n)
    // using 0-99 instead of 1-100
    pardoned = 0
    numInDrawer = range(99)
    for round in range(1, n)
    	numInDrawer.shuffle
        for prisoner in range(99)
            found = false
	    drawer = prisoner
            for i in range(1,50)
                card = numInDrawer[drawer]
                if card == prisoner then
                    found = true
                    break
                end if
                drawer = card
            end for
            if not found then break
        end for
        if found then pardoned = pardoned + 1
    end for
    return pardoned / n * 100
end function

print "Random:  " + playRandom(10000) + "%"
print "Optimal: " + playOptimal(10000) + "%"
Output:
Random:  0%
Optimal: 31.06%

Nim[edit]

Imperative style.

import random, sequtils, strutils

type
  Sample = tuple
    succ: int
    fail: int

const
  numPrisoners = 100
  numDrawsEachPrisoner = numPrisoners div 2
  numDrawings: Positive = 1_000_000 div 1

proc `$`(s: Sample): string =
  "Succs: $#\tFails: $#\tTotal: $#\tSuccess Rate: $#%." % [$s.succ, $s.fail, $(s.succ + s.fail), $(s.succ.float / (s.succ + s.fail).float * 100.0)]

proc prisonersWillBeReleasedSmart(): bool =
  result = true
  var drawers = toSeq(0..<numPrisoners)
  drawers.shuffle
  for prisoner in 0..<numPrisoners:
    var drawer = prisoner
    block inner:
      for _ in 0..<numDrawsEachPrisoner:
        if drawers[drawer] == prisoner: break inner
        drawer = drawers[drawer]
      return false

proc prisonersWillBeReleasedRandom(): bool =
  result = true
  var drawers = toSeq(0..<numPrisoners)
  drawers.shuffle
  for prisoner in 0..<numPrisoners:
    var selectDrawer = toSeq(0..<numPrisoners)
    selectDrawer.shuffle
    block inner:
      for i in 0..<numDrawsEachPrisoner:
        if drawers[selectDrawer[i]] == prisoner: break inner
      return false

proc massDrawings(prisonersWillBeReleased: proc(): bool): Sample =
  var success = 0
  for i in 1..numDrawings:
    if prisonersWillBeReleased():
      inc(success)
  return (success, numDrawings - success)

randomize()
echo $massDrawings(prisonersWillBeReleasedSmart)
echo $massDrawings(prisonersWillBeReleasedRandom)
Output:
Succs: 312225   Fails: 687775   Total: 1000000  Success Rate: 31.2225%.
Succs: 0        Fails: 1000000  Total: 1000000  Success Rate: 0.0%.

Pascal[edit]

Works with: Free Pascal

searching the longest cycle length as stated on talk page and increment an counter for that cycle length.

program Prisoners100;

const
  rounds  = 100000;

type
  tValue = Uint32;
  tPrisNum = array of tValue;
var
  drawers,
  PrisonersChoice : tPrisNum;

procedure shuffle(var N:tPrisNum);
var
  i,j,lmt : nativeInt;
  tmp: tValue;
Begin
  lmt := High(N);
  For i := lmt downto 1 do
  begin
    //take on from index i..limit
    j := random(i+1);
    //exchange with i
    tmp := N[i];N[i]:= N[j];N[j]:= tmp;
  end;
end;

function PardonedRandom(maxTestNum: NativeInt):boolean;
var
  PrisNum,TestNum,Lmt : NativeUint;
  Pardoned : boolean;
Begin
  IF maxTestNum <=0 then
  Begin
    PardonedRandom := false;
    EXIT;
  end;
  Lmt := High(drawers);
  IF (maxTestNum >= Lmt) then
  Begin
    PardonedRandom := true;
    EXIT;
  end;

  shuffle(drawers);
  PrisNum := 0;
  repeat
    //every prisoner uses his own list of drawers
    shuffle(PrisonersChoice);
    TestNum := 0;
    repeat
      Pardoned := drawers[PrisonersChoice[TestNum]] = PrisNum;
      inc(TestNum);
    until Pardoned OR (TestNum>=maxTestNum);
    IF Not(Pardoned) then
      BREAK;
    inc(PrisNum);
  until PrisNum>=Lmt;
  PardonedRandom:= Pardoned;
end;

function PardonedOptimized(maxTestNum: NativeUint):boolean;
var
  PrisNum,TestNum,NextNum,Cnt,Lmt : NativeUint;
  Pardoned : boolean;
Begin
  IF maxTestNum <=0 then
  Begin
    PardonedOptimized := false;
    EXIT;
  end;
  Lmt := High(drawers);
  IF (maxTestNum >= Lmt) then
  Begin
    PardonedOptimized := true;
    EXIT;
  end;

  shuffle(drawers);
  Lmt := High(drawers);
  IF maxTestNum >= Lmt then
  Begin
    PardonedOptimized := true;
    EXIT;
  end;
  PrisNum := 0;
  repeat
    Cnt := 0;
    NextNum := PrisNum;
    repeat
      TestNum := NextNum;
      NextNum := drawers[TestNum];
      inc(cnt);
      Pardoned := NextNum = PrisNum;
    until Pardoned OR (cnt >=maxTestNum);

    IF Not(Pardoned) then
      BREAK;
    inc(PrisNum);
  until PrisNum>Lmt;
  PardonedOptimized := Pardoned;
end;

procedure CheckRandom(testCount : NativeUint);
var
  i,cnt : NativeInt;
Begin
  cnt := 0;
  For i := 1 to rounds do
    IF PardonedRandom(TestCount) then
      inc(cnt);
  writeln('Randomly  ',cnt/rounds*100:7:2,'% get pardoned out of ',rounds,' checking max ',TestCount);
end;

procedure CheckOptimized(testCount : NativeUint);
var
  i,cnt : NativeInt;
Begin
  cnt := 0;
  For i := 1 to rounds do
    IF PardonedOptimized(TestCount) then
      inc(cnt);
  writeln('Optimized ',cnt/rounds*100:7:2,'% get pardoned out of ',rounds,' checking max ',TestCount);
end;

procedure OneCompareRun(PrisCnt:NativeInt);
var
  i,lmt :nativeInt;
begin
  setlength(drawers,PrisCnt);
  For i := 0 to PrisCnt-1 do
    drawers[i] := i;
  PrisonersChoice := copy(drawers);

  //test
  writeln('Checking ',PrisCnt,' prisoners');

  lmt := PrisCnt;
  repeat
    CheckOptimized(lmt);
    dec(lmt,PrisCnt DIV 10);
  until lmt < 0;
  writeln;

  lmt := PrisCnt;
  repeat
    CheckRandom(lmt);
    dec(lmt,PrisCnt DIV 10);
  until lmt < 0;
  writeln;
  writeln;
end;

Begin
  //init
  randomize;
  OneCompareRun(20);
  OneCompareRun(100);
end.
Output:
Checking 20 prisoners
Optimized  100.00% get pardoned out of 100000 checking max 20
Optimized   89.82% get pardoned out of 100000 checking max 18
Optimized   78.25% get pardoned out of 100000 checking max 16
Optimized   65.31% get pardoned out of 100000 checking max 14
Optimized   50.59% get pardoned out of 100000 checking max 12
Optimized   33.20% get pardoned out of 100000 checking max 10
Optimized   15.28% get pardoned out of 100000 checking max 8
Optimized    3.53% get pardoned out of 100000 checking max 6
Optimized    0.10% get pardoned out of 100000 checking max 4
Optimized    0.00% get pardoned out of 100000 checking max 2
Optimized    0.00% get pardoned out of 100000 checking max 0

Randomly   100.00% get pardoned out of 100000 checking max 20
Randomly    13.55% get pardoned out of 100000 checking max 18
Randomly     1.38% get pardoned out of 100000 checking max 16
Randomly     0.12% get pardoned out of 100000 checking max 14
Randomly     0.00% get pardoned out of 100000 checking max 12
Randomly     0.00% get pardoned out of 100000 checking max 10
Randomly     0.00% get pardoned out of 100000 checking max 8
Randomly     0.00% get pardoned out of 100000 checking max 6
Randomly     0.00% get pardoned out of 100000 checking max 4
Randomly     0.00% get pardoned out of 100000 checking max 2
Randomly     0.00% get pardoned out of 100000 checking max 0


Checking 100 prisoners
Optimized  100.00% get pardoned out of 100000 checking max 100
Optimized   89.48% get pardoned out of 100000 checking max 90
Optimized   77.94% get pardoned out of 100000 checking max 80
Optimized   64.48% get pardoned out of 100000 checking max 70
Optimized   49.35% get pardoned out of 100000 checking max 60
Optimized   31.10% get pardoned out of 100000 checking max 50
Optimized   13.38% get pardoned out of 100000 checking max 40
Optimized    2.50% get pardoned out of 100000 checking max 30
Optimized    0.05% get pardoned out of 100000 checking max 20
Optimized    0.00% get pardoned out of 100000 checking max 10
Optimized    0.00% get pardoned out of 100000 checking max 0

Randomly   100.00% get pardoned out of 100000 checking max 100
Randomly     0.01% get pardoned out of 100000 checking max 90
Randomly     0.00% get pardoned out of 100000 checking max 80
Randomly     0.00% get pardoned out of 100000 checking max 70
Randomly     0.00% get pardoned out of 100000 checking max 60
Randomly     0.00% get pardoned out of 100000 checking max 50
Randomly     0.00% get pardoned out of 100000 checking max 40
Randomly     0.00% get pardoned out of 100000 checking max 30
Randomly     0.00% get pardoned out of 100000 checking max 20
Randomly     0.00% get pardoned out of 100000 checking max 10
Randomly     0.00% get pardoned out of 100000 checking max 0

Alternative for optimized[edit]

program Prisoners100;
{$IFDEF FPC}
  {$MODE DELPHI}{$OPTIMIZATION ON,ALL}
{$ELSE}
  {$APPTYPE CONSOLE}
{$ENDIF}
type
  tValue  = NativeUint;
  tpValue = pNativeUint;
  tPrisNum = array of tValue;

const
  rounds  = 1000000;
  cAlreadySeen = High(tValue);
var
  drawers,
  Visited,
  CntToPardoned : tPrisNum;
  PrisCount : NativeInt;

procedure shuffle(var N:tPrisNum;lmt : nativeInt = 0);
var
  pN : tpValue;
  i,j : nativeInt;
  tmp: tValue;
Begin
  pN := @N[0];
  if lmt = 0 then
    lmt := High(N);
  For i := lmt downto 1 do
  begin
    //take one from index [0..i]
    j := random(i+1);
    //exchange with i
    tmp := pN[i];pN[i]:= pN[j];pN[j]:= tmp;
  end;
end;

procedure CopyDrawers2Visited;
//drawers and Visited are of same size, so only moving values
Begin
  Move(drawers[0],Visited[0],SizeOf(tValue)*PrisCount);
end;

function GetMaxCycleLen:NativeUint;
var
  pVisited : tpValue;
  cycleLen,MaxCycLen,Num,NumBefore : NativeUInt;
Begin
  CopyDrawers2Visited;
  pVisited := @Visited[0];
  MaxCycLen := 0;
  cycleLen := MaxCycLen;
  Num := MaxCycLen;
  repeat
    NumBefore := Num;
    Num := pVisited[Num];
    pVisited[NumBefore] := cAlreadySeen;
    inc(cycleLen);
    IF (Num= NumBefore) or (Num = cAlreadySeen) then
    begin
      IF Num = cAlreadySeen then
        dec(CycleLen);
      IF MaxCycLen < cycleLen then
        MaxCycLen := cycleLen;
      Num := 0;
      while (Num< PrisCount) AND (pVisited[Num] = cAlreadySeen) do
        inc(Num);
      //all cycles found
      IF Num >= PrisCount then
        BREAK;
      cycleLen :=0;
    end;
  until false;
  GetMaxCycleLen := MaxCycLen-1;
end;

procedure CheckOptimized(testCount : NativeUint);
var
  factor: extended;
  i,sum,digit,delta : NativeInt;
Begin
  For i := 1 to rounds do
  begin
    shuffle(drawers);
    inc(CntToPardoned[GetMaxCycleLen]);
  end;

  digit := 0;
  sum := rounds;
  while sum > 100 do
  Begin
    inc(digit);
    sum := sum DIV 10;
  end;
  factor := 100.0/rounds;

  delta :=0;
  sum := 0;
  For i := 0 to High(drawers) do
  Begin
    inc(sum,CntToPardoned[i]);
    dec(delta);
    IF delta <= 0 then
    Begin
      writeln(sum*factor:Digit+5:Digit,'% get pardoned checking max ',i+1);
      delta := delta+Length(drawers) DIV 10;
    end;
  end;
end;

procedure OneCompareRun(PrisCnt:NativeInt);
var
  i,lmt :nativeInt;
begin
  PrisCount := PrisCnt;
  setlength(drawers,PrisCnt);
  For i := 0 to PrisCnt-1 do
    drawers[i] := i;
  setlength(Visited,PrisCnt);
  setlength(CntToPardoned,PrisCnt);
  //test
  writeln('Checking ',PrisCnt,' prisoners for ',rounds,' rounds');
  lmt := PrisCnt;
  CheckOptimized(lmt);
  writeln;

  setlength(CntToPardoned,0);
  setlength(Visited,0);
  setlength(drawers,0);
end;

Begin
  randomize;
  OneCompareRun(10);
  OneCompareRun(100);
  OneCompareRun(1000);
end.
Output:
Checking 10 prisoners for 1000000 rounds
   0.0000% get pardoned checking max 1
   0.2584% get pardoned checking max 2
   4.7431% get pardoned checking max 3
  17.4409% get pardoned checking max 4
  35.4983% get pardoned checking max 5
  52.1617% get pardoned checking max 6
  66.4807% get pardoned checking max 7
  78.9761% get pardoned checking max 8
  90.0488% get pardoned checking max 9
 100.0000% get pardoned checking max 10

Checking 100 prisoners for 1000000 rounds
   0.0000% get pardoned checking max 1
   0.0000% get pardoned checking max 10
   0.0459% get pardoned checking max 20
   2.5996% get pardoned checking max 30
  13.5071% get pardoned checking max 40
  31.2258% get pardoned checking max 50
  49.3071% get pardoned checking max 60
  64.6128% get pardoned checking max 70
  77.8715% get pardoned checking max 80
  89.5385% get pardoned checking max 90
 100.0000% get pardoned checking max 100

Checking 1000 prisoners for 1000000 rounds
   0.0000% get pardoned checking max 1
   0.0000% get pardoned checking max 100
   0.0374% get pardoned checking max 200
   2.3842% get pardoned checking max 300
  13.1310% get pardoned checking max 400
  30.7952% get pardoned checking max 500
  48.9710% get pardoned checking max 600
  64.3555% get pardoned checking max 700
  77.6950% get pardoned checking max 800
  89.4515% get pardoned checking max 900
 100.0000% get pardoned checking max 1000

real    0m9,975s

Perl[edit]

Translation of: Raku
use strict;
use warnings;
use feature 'say';
use List::Util 'shuffle';

sub simulation {
    my($population,$trials,$strategy) = @_;
    my $optimal   = $strategy =~ /^o/i ? 1 : 0;
    my @prisoners = 0..$population-1;
    my $half      = int $population / 2;
    my $pardoned  = 0;

    for (1..$trials) {
        my @drawers = shuffle @prisoners;
        my $total = 0;
        for my $prisoner (@prisoners) {
            my $found = 0;
            if ($optimal) {
                my $card = $drawers[$prisoner];
                if ($card == $prisoner) {
                    $found = 1;
                } else {
                    for (1..$half-1) {
                        $card = $drawers[$card];
                        ($found = 1, last) if $card == $prisoner
                    }
                }
            } else {
                for my $card ( (shuffle @drawers)[0..$half]) {
                    ($found = 1, last) if $card == $prisoner
                }
            }
            last unless $found;
            $total++;
        }
        $pardoned++ if $total == $population;
    }
    $pardoned / $trials * 100
}

my $population = 100;
my $trials     = 10000;
say " Simulation count: $trials\n" .
(sprintf " Random strategy pardons: %6.3f%% of simulations\n", simulation $population, $trials, 'random' ) .
(sprintf "Optimal strategy pardons: %6.3f%% of simulations\n", simulation $population, $trials, 'optimal');

$population = 10;
$trials     = 100000;
say " Simulation count: $trials\n" .
(sprintf " Random strategy pardons: %6.3f%% of simulations\n", simulation $population, $trials, 'random' ) .
(sprintf "Optimal strategy pardons: %6.3f%% of simulations\n", simulation $population, $trials, 'optimal');
Output:
 Simulation count: 10000
 Random strategy pardons:  0.000% of simulations
Optimal strategy pardons: 31.510% of simulations

 Simulation count: 1000000
 Random strategy pardons:  0.099% of simulations
Optimal strategy pardons: 35.420% of simulations

PicoLisp[edit]

Built so you could easily build and test your own strategies.

(de shuffle (Lst)
   (by '(NIL (rand)) sort Lst) )

# Extend this class with a `next-guess>` method and a `str>` method.
(class +Strategy +Entity)
(dm prev-drawer> (Num)
   (=: prev Num) )

(class +Random +Strategy)
(dm T (Prisoner)
   (=: guesses (nth (shuffle (range 1 100)) 51)) )
(dm next-guess> ()
   (pop (:: guesses)) )
(dm str> ()
   "Random" )

(class +Optimal +Strategy)
(dm T (Prisoner)
   (=: prisoner-id Prisoner) )
(dm next-guess> ()
   (or (: prev) (: prisoner-id)) )
(dm str> ()
   "Optimal/Wikipedia" )


(de test-strategy (Strategy)
   "Simulate one round of 100 prisoners who use `Strategy`"
   (let Drawers (shuffle (range 1 100))
      (for Prisoner (range 1 100)
         (NIL # Break and return NIL if any prisoner fails their test.
            (let Strat (new (list Strategy) Prisoner)
               (do 50 # Try 50 iterations of `Strat`. Break and return T iff success.
                  (T (= Prisoner (prev-drawer> Strat (get Drawers (next-guess> Strat))))
                     T ) ) ) )
         T ) ) )

(de test-strategy-n-times (Strategy N)
   "Simulate `N` rounds of 100 prisoners who use `Strategy`"
   (let Successes 0
      (do N
         (when (test-strategy Strategy)
            (inc 'Successes) ) )
      (prinl "We have a " (/ (* 100 Successes) N) "% success rate with " N " trials.")
      (prinl "This is using the " (str> Strategy) " strategy.") ) )

Then run

(test-strategy-n-times '+Random 10000)
(test-strategy-n-times '+Optimal 10000)
Output:
We have a 0% success rate with 10000 trials.
This is using the Random strategy.
We have a 31% success rate with 10000 trials.
This is using the Optimal/Wikipedia strategy.

Phix[edit]

function play(integer prisoners, iterations, bool optimal)
    sequence drawers = shuffle(tagset(prisoners))
    integer pardoned = 0
    bool found = false
    for i=1 to iterations do
        drawers = shuffle(drawers)
        for prisoner=1 to prisoners do
            found = false
            integer drawer = iff(optimal?prisoner:rand(prisoners))
            for j=1 to prisoners/2 do
                drawer = drawers[drawer]
                if drawer==prisoner then found = true exit end if
                if not optimal then drawer = rand(prisoners) end if
            end for
            if not found then exit end if
        end for
        pardoned += found
    end for
    return 100*pardoned/iterations
end function
 
constant iterations = 100_000
printf(1,"Simulation count: %d\n",iterations)
for prisoners=10 to 100 by 90 do
    atom random = play(prisoners,iterations,false),
         optimal = play(prisoners,iterations,true)
    printf(1,"Prisoners:%d, random:%g, optimal:%g\n",{prisoners,random,optimal})
end for
Output:
Simulation count: 100000
Prisoners:10, random:0.006, optimal:35.168
Prisoners:100, random:0, optimal:31.098

Phixmonti[edit]

Translation of: Yabasic
/# Rosetta Code problem: http://rosettacode.org/wiki/100_prisoners
by Galileo, 05/2022 #/

include ..\Utilitys.pmt

def random rand * 1 + int enddef

def shuffle
    len var l
    l for var a
        l random var b
        b get var p
        a get b set
        p a set
    endfor
enddef

def play var optimal var iterations var prisoners
    0 var pardoned

    ( prisoners for endfor )
    
    iterations for drop
        shuffle
        prisoners for var prisoner
            false var found
            optimal if prisoner else prisoners random endif
            prisoners 2 / int for drop
                get dup prisoner == if true var found exitfor
                else
                    optimal not if drop prisoners random endif
                endif
            endfor
            found not if exitfor endif
            drop
        endfor
        pardoned found + var pardoned
    endfor
    drop
    pardoned 100 * iterations /
enddef

"Please, be patient ..." ?

( "Optimal: " 100 10000 true play
  " Random: " 100 10000 false play
  " Prisoners: " prisoners ) lprint
Output:
Please, be patient ...
Optimal: 31.65 Random: 0 Prisoners: 100
=== Press any key to exit ===

PL/M[edit]

100H:
/* PARAMETERS */
DECLARE N$DRAWERS  LITERALLY '100';  /* AMOUNT OF DRAWERS */
DECLARE N$ATTEMPTS LITERALLY '50';   /* ATTEMPTS PER PRISONER */
DECLARE N$SIMS     LITERALLY '2000'; /* N. OF SIMULATIONS TO RUN */ 
DECLARE RAND$SEED  LITERALLY '193';  /* RANDOM SEED */

/* CP/M CALLS */
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0, 0); END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9, S); END PRINT;

/* PRINT NUMBER */
PRINT$NUMBER: PROCEDURE (N);
    DECLARE S (6) BYTE INITIAL ('.....$');
    DECLARE (P, N) ADDRESS, C BASED P BYTE;
    P = .S(5);
DIGIT:
    P = P - 1;
    C = N MOD 10 + '0';
    N = N / 10;
    IF N > 0 THEN GO TO DIGIT;
    CALL PRINT(P);
END PRINT$NUMBER;

/* RANDOM NUMBER GENERATOR */
RAND$BYTE: PROCEDURE BYTE;
    DECLARE (X, A, B, C) BYTE 
        INITIAL (RAND$SEED, RAND$SEED, RAND$SEED, RAND$SEED);
    X = X+1;
    A = A XOR C XOR X;
    B = B+A;
    C = C+SHR(B,1)+A;
    RETURN C;
END RAND$BYTE;

/* GENERATE RANDOM NUMBER FROM 0 TO MAX */
RAND$MAX: PROCEDURE (MAX) BYTE;
    DECLARE (X, R, MAX) BYTE;
    X = 1;
    DO WHILE X < MAX;
        X = SHL(X,1);
    END;
    X = X-1;
    DO WHILE 1;
        R = RAND$BYTE AND X;
        IF R < MAX THEN RETURN R;
    END;
END RAND$MAX;

/* PLACE CARDS RANDOMLY IN DRAWERS */
INIT$DRAWERS: PROCEDURE (DRAWERS);
    DECLARE DRAWERS ADDRESS, (D BASED DRAWERS, I, J, K) BYTE;
    DO I=0 TO N$DRAWERS-1;
        D(I) = I;
    END;
    DO I=0 TO N$DRAWERS-1;
        J = I + RAND$MAX(N$DRAWERS-I);
        K = D(I);
        D(I) = D(J);
        D(J) = K;
    END;
END INIT$DRAWERS;

/* PRISONER OPENS RANDOM DRAWERS */
RANDOM$STRATEGY: PROCEDURE (DRAWERS, P) BYTE;
    DECLARE DRAWERS ADDRESS, D BASED DRAWERS BYTE;
    DECLARE (P, I, TRIES) BYTE;
    
    /* KEEP TRACK OF WHICH DRAWERS HAVE BEEN OPENED */
    DECLARE OPEN (N$DRAWERS) BYTE;
    DO I=0 TO N$DRAWERS-1;
        OPEN(I) = 0;
    END;
    
    /* OPEN RANDOM DRAWERS */
    TRIES = N$ATTEMPTS;
    DO WHILE TRIES > 0;
        IF NOT OPEN(I := RAND$MAX(N$DRAWERS)) THEN DO;
            /* IF WE FIND OUR NUMBER, SUCCESS */
            IF D(I) = P THEN RETURN 1;
            OPEN(I) = 1;    
            TRIES = TRIES - 1;
        END;
    END;
    
    RETURN 0; /* WE DID NOT FIND OUR NUMBER */
END RANDOM$STRATEGY;

/* PRISONER USES OPTIMAL STRATEGY */
OPTIMAL$STRATEGY: PROCEDURE (DRAWERS, P) BYTE;
    DECLARE DRAWERS ADDRESS, D BASED DRAWERS BYTE;
    DECLARE (P, I, TRIES) BYTE;
    TRIES = N$ATTEMPTS;
    I = P;
    DO WHILE TRIES > 0;
        I = D(I); /* OPEN DRAWER W/ CURRENT NUMBER */
        IF I = P THEN RETURN 1; /* DID WE FIND IT? */
        TRIES = TRIES - 1;
    END;
    RETURN 0;
END OPTIMAL$STRATEGY;

/* RUN A SIMULATION */
DECLARE RANDOM LITERALLY '0';
DECLARE OPTIMAL LITERALLY '1';
SIMULATE: PROCEDURE (STRAT) BYTE;
    DECLARE (STRAT, P, R) BYTE;
    
    /* PLACE CARDS IN DRAWERS */
    DECLARE DRAWERS (N$DRAWERS) BYTE;
    CALL INIT$DRAWERS(.DRAWERS);
    
    /* TRY EACH PRISONER */
    DO P=0 TO N$DRAWERS-1;
        DO CASE STRAT;
            R = RANDOM$STRATEGY(.DRAWERS, P);
            R = OPTIMAL$STRATEGY(.DRAWERS, P);
        END;
        
        /* IF ONE PRISONER FAILS THEY ALL HANG */
        IF NOT R THEN RETURN 0;
    END;
    
    RETURN 1; /* IF THEY ALL SUCCEED NONE HANG */
END SIMULATE;

/* RUN MANY SIMULATIONS AND COUNT THE SUCCESSES */
RUN$SIMULATIONS: PROCEDURE (N, STRAT) ADDRESS;
    DECLARE STRAT BYTE, (I, N, SUCC) ADDRESS;
    SUCC = 0;
    DO I=1 TO N;
        SUCC = SUCC + SIMULATE(STRAT);
    END;
    RETURN SUCC;
END RUN$SIMULATIONS;

/* RUN AND PRINT SIMULATIONS */
RUN$AND$PRINT: PROCEDURE (NAME, STRAT, N);
    DECLARE (NAME, N, S) ADDRESS, STRAT BYTE;
    CALL PRINT(NAME);
    CALL PRINT(.' STRATEGY: $');
    S = RUN$SIMULATIONS(N, STRAT);
    CALL PRINT$NUMBER(S);
    CALL PRINT(.' OUT OF $');
    CALL PRINT$NUMBER(N);
    CALL PRINT(.' - $');
    CALL PRINT$NUMBER( S*10 / (N/10) );
    CALL PRINT(.(37,13,10,'$'));
END RUN$AND$PRINT;

CALL RUN$AND$PRINT(.'RANDOM$', RANDOM, N$SIMS);
CALL RUN$AND$PRINT(.'OPTIMAL$', OPTIMAL, N$SIMS);
CALL EXIT;
EOF
Output:
RANDOM STRATEGY: 0 OUT OF 2000 - 0%
OPTIMAL STRATEGY: 653 OUT OF 2000 - 32%

Pointless[edit]

optimalSeq(drawers, n) =
  iterate(ind => drawers[ind - 1], n)
  |> takeUntil(ind => drawers[ind - 1] == n)

optimalTrial(drawers) =
  range(1, 100)
  |> map(optimalSeq(drawers))

randomSeq(drawers, n) =
  iterate(ind => randRange(1, 100), randRange(1, 100))
  |> takeUntil(ind => drawers[ind - 1] == n)

randomTrial(drawers) =
  range(1, 100)
  |> map(randomSeq(drawers))

checkLength(seq) =
  length(take(51, seq)) <= 50

numTrials = 3000

runTrials(trialFunc) =
  for t in range(1, numTrials)
  yield
    range(1, 100)
    |> shuffle
    |> toArray
    |> trialFunc
    |> map(checkLength)
    |> all

countSuccess(trialFunc) =
  runTrials(trialFunc)
  |> filter(id)
  |> length

optimalCount = countSuccess(optimalTrial)
randomCount = countSuccess(randomTrial)

output =
  format("optimal: {} / {} = {} prob\nrandom: {} / {} = {} prob", [
    optimalCount, numTrials, optimalCount / numTrials,
    randomCount, numTrials, randomCount / numTrials,
  ])
  |> println
Output:
optimal: 923 / 3000 = 0.30766666666666664 prob
random: 0 / 3000 = 0.0 prob

PowerShell[edit]

Translation of: Chris
### Clear Screen from old Output
Clear-Host

Function RandomOpening () 
  {
    $Prisoners = 1..100 | Sort-Object {Get-Random}
    $Cupboard = 1..100 | Sort-Object {Get-Random}
    ## Loop for the Prisoners
    $Survived = $true
    for ($I=1;$I -le 100;$i++)
      {
          $OpeningListe = 1..100 | Sort-Object {Get-Random}
          $Gefunden = $false
          ## Loop for the trys of every prisoner
          for ($X=1;$X -le 50;$X++)
            {
                $OpenNumber = $OpeningListe[$X]
                IF ($Cupboard[$OpenNumber] -eq $Prisoners[$I])
                  {
                      $Gefunden = $true
                  }
                ## Cancel loop if prisoner found his number (yeah i know, dirty way ^^ )  
                IF ($Gefunden)
                  {
                    $X = 55
                  }
            }
          IF ($Gefunden -eq $false)
            {
              $I = 120
              $Survived = $false
            }            
      }
    Return $Survived
  }

  Function StrategyOpening () 
  {
    $Prisoners = 1..100 | Sort-Object {Get-Random}
    $Cupboard = 1..100 | Sort-Object {Get-Random}
    $Survived = $true
    for ($I=1;$I -le 100;$i++)
      {
          $Gefunden = $false
          $OpeningNumber = $Prisoners[$I-1]
          for ($X=1;$X -le 50;$X++)
            {
                IF ($Cupboard[$OpeningNumber-1] -eq $Prisoners[$I-1])
                  {
                      $Gefunden = $true
                  }
                else 
                  {
                    $OpeningNumber = $Cupboard[$OpeningNumber-1]                  
                  } 
                IF ($Gefunden)
                  {
                    $X = 55
                  }
            }
          IF ($Gefunden -eq $false)
            {
              $I = 120
              $Survived = $false
            }            
      }
    Return $Survived
  }

$MaxRounds = 10000

Function TestRandom
  {
    $WinnerRandom = 0
    for ($Round = 1; $Round -le $MaxRounds;$Round++)
      {
        IF (($Round%1000) -eq 0)
          {
            $Time = Get-Date
            Write-Host "Currently we are at rount $Round at $Time"
          }
        $Rueckgabewert = RandomOpening
        IF ($Rueckgabewert)
          {
            $WinnerRandom++
          }
      }
    
    $Prozent = (100/$MaxRounds)*$WinnerRandom
    Write-Host "There are $WinnerRandom survivors whit random opening. This is $Prozent percent"
  }

Function TestStrategy
  {
    $WinnersStrategy = 0 
      for ($Round = 1; $Round -le $MaxRounds;$Round++)
        {
          IF (($Round%1000) -eq 0)
            {
              $Time = Get-Date
              Write-Host "Currently we are at $Round at $Time"
            }
          $Rueckgabewert = StrategyOpening
          IF ($Rueckgabewert)
            {
              $WinnersStrategy++
            }
        }
    
    $Prozent = (100/$MaxRounds)*$WinnersStrategy
    Write-Host "There are $WinnersStrategy survivors whit strategic opening. This is $Prozent percent"
  }

Function Main () 
  {
    Clear-Host
    TestRandom
    TestStrategy
  }

Main
Output:
# of executions: 10000
There are 0 survivors whit random opening. This is 0 percent
There are 3104 survivors whit strategic opening. This is 31,04 percent"

Processing[edit]

IntList drawers = new IntList();
int trials = 100000;
int succes_count;

void setup() {
  for (int i = 0; i < 100; i++) {
    drawers.append(i);
  }
  println(trials + " trials\n");

  //Random strategy
  println("Random strategy");
  succes_count = trials;
  for (int i = 0; i < trials; i++) {
    drawers.shuffle();
    for (int prisoner = 0; prisoner < 100; prisoner++) {
      boolean found = false;
      for (int attempt = 0; attempt < 50; attempt++) {
        if (drawers.get(int(random(drawers.size()))) == prisoner) {
          found = true;
          break;
        }
      }
      if (!found) {
        succes_count--;
        break;
      }
    }
  }
  println(" Succeses: " + succes_count);
  println(" Succes rate: " + 100.0 * succes_count / trials + "%\n");

  //Optimal strategy
  println("Optimal strategy");
  succes_count = trials;
  for (int i = 0; i < trials; i++) {
    drawers.shuffle();
    for (int prisoner = 0; prisoner < 100; prisoner++) {
      boolean found = false;
      int next = prisoner;
      for (int attempt = 0; attempt < 50; attempt++) {
        next = drawers.get(next);
        if (next == prisoner) {
          found = true;
          break;
        }
      }
      if (!found) {
        succes_count--;
        break;
      }
    }
  }
  println(" Succeses: " + succes_count);
  print(" Succes rate: " + 100.0 * succes_count / trials + "%");
}
Output:
100000 trials

Random strategy
 Succeses: 0
 Succes rate: 0.0%

Optimal strategy
 Succeses: 31134
 Succes rate: 31.134%

PureBasic[edit]

#PRISONERS=100
#DRAWERS  =100
#LOOPS    = 50
#MAXPROBE = 10000
OpenConsole()

Dim p1(#PRISONERS,#DRAWERS)
Dim p2(#PRISONERS,#DRAWERS)
Dim d(#DRAWERS)

For i=1 To #DRAWERS : d(i)=i : Next
Start:
For probe=1 To #MAXPROBE
  RandomizeArray(d(),1,100)
  c1=0 : c2=0 
  For m=1 To #PRISONERS
    p2(m,1)=d(m) : If d(m)=m : p2(m,0)=1 : EndIf
    For n=1 To #LOOPS
      p1(m,n)=d(Random(100,1))
      If p1(m,n)=m : p1(m,0)=1 : EndIf
      If n>1 : p2(m,n)=d(p2(m,n-1)) : If p2(m,n)=m : p2(m,0)=1 : EndIf : EndIf
    Next n
  Next m
  
  For m=1 To #PRISONERS
    If p1(m,0) : c1+1 : p1(m,0)=0 : EndIf 
    If p2(m,0) : c2+1 : p2(m,0)=0 : EndIf
  Next m
  
  If c1=#PRISONERS : w1+1 : EndIf
  If c2=#PRISONERS : w2+1 : EndIf
Next probe
Print("TRIALS: "+Str(#MAXPROBE))
Print("  RANDOM= "+StrF(100*w1/#MAXPROBE,2)+"%   STATEGY= "+StrF(100*w2/#MAXPROBE,2)+"%")
PrintN(~"\tFIN =q.") : inp$=Input()
w1=0 : w2=0
If inp$<>"q" : Goto Start : EndIf
Output:
TRIALS: 10000  RANDOM= 0.00%   STATEGY= 30.83%	FIN =q.

TRIALS: 10000  RANDOM= 0.00%   STATEGY= 31.60%	FIN =q.

TRIALS: 10000  RANDOM= 0.00%   STATEGY= 31.20%	FIN =q.

Python[edit]

Procedural[edit]

import random

def play_random(n):
    # using 0-99 instead of ranges 1-100
    pardoned = 0
    in_drawer = list(range(100))
    sampler = list(range(100))
    for _round in range(n):
        random.shuffle(in_drawer)
        found = False
        for prisoner in range(100):
            found = False
            for reveal in random.sample(sampler, 50):
                card = in_drawer[reveal]
                if card == prisoner:
                    found = True
                    break
            if not found:
                break
        if found:
            pardoned += 1
    return pardoned / n * 100   # %

def play_optimal(n):
    # using 0-99 instead of ranges 1-100
    pardoned = 0
    in_drawer = list(range(100))
    for _round in range(n):
        random.shuffle(in_drawer)
        for prisoner in range(100):
            reveal = prisoner
            found = False
            for go in range(50):
                card = in_drawer[reveal]
                if card == prisoner:
                    found = True
                    break
                reveal = card
            if not found:
                break
        if found:
            pardoned += 1
    return pardoned / n * 100   # %

if __name__ == '__main__':
    n = 100_000
    print(" Simulation count:", n)
    print(f" Random play wins: {play_random(n):4.1f}% of simulations")
    print(f"Optimal play wins: {play_optimal(n):4.1f}% of simulations")
Output:
 Simulation count: 100000
 Random play wins:  0.0% of simulations
Optimal play wins: 31.1% of simulations


Or, an alternative procedural approach:

# http://rosettacode.org/wiki/100_prisoners

import random


def main():
    NUM_DRAWERS = 10
    NUM_REPETITIONS = int(1E5)

    print('{:15}: {:5} ({})'.format('approach', 'wins', 'ratio'))
    for approach in PrisionersGame.approaches:
        num_victories = 0
        for _ in range(NUM_REPETITIONS):
            game = PrisionersGame(NUM_DRAWERS)
            num_victories += PrisionersGame.victory(game.play(approach))

        print('{:15}: {:5} ({:.2%})'.format(
            approach.__name__, num_victories, num_victories / NUM_REPETITIONS))


class PrisionersGame:
    """docstring for PrisionersGame"""
    def __init__(self, num_drawers):
        assert num_drawers % 2 == 0
        self.num_drawers = num_drawers
        self.max_attempts = int(self.num_drawers / 2)
        self.drawer_ids = list(range(1, num_drawers + 1))
        shuffled = self.drawer_ids[:]
        random.shuffle(shuffled)
        self.drawers = dict(zip(self.drawer_ids, shuffled))

    def play_naive(self, player_number):
        """ Randomly open drawers """
        for attempt in range(self.max_attempts):
            if self.drawers[random.choice(self.drawer_ids)] == player_number:
                return True

        return False

    def play_naive_mem(self, player_number):
        """ Randomly open drawers but avoiding repetitions """
        not_attemped = self.drawer_ids[:]
        for attempt in range(self.max_attempts):
            guess = random.choice(not_attemped)
            not_attemped.remove(guess)

            if self.drawers[guess] == player_number:
                return True

        return False

    def play_optimum(self, player_number):
        """ Open the drawer that matches the player number and then open the drawer
        with the revealed number.
        """
        prev_attempt = player_number
        for attempt in range(self.max_attempts):
            if self.drawers[prev_attempt] == player_number:
                return True
            else:
                prev_attempt = self.drawers[prev_attempt]

        return False

    @classmethod
    def victory(csl, results):
        """Defines a victory of a game: all players won"""
        return all(results)

    approaches = [play_naive, play_naive_mem, play_optimum]

    def play(self, approach):
        """Plays this game and returns a list of booleans with
        True if a player one, False otherwise"""
        return [approach(self, player) for player in self.drawer_ids]


if __name__ == '__main__':
    main()
Output:
With 10 drawers (100k runs)
approach       : wins  (ratio)
play_naive     :    14 (0.01%)
play_naive_mem :    74 (0.07%)
play_optimum   : 35410 (35.41%)

With 100 drawers (10k runs)
approach       : wins  (ratio)
play_naive     :     0 (0.00%)
play_naive_mem :     0 (0.00%)
play_optimum   :  3084 (30.84%)

Functional[edit]

There is some inefficiency entailed in repeatedly re-calculating the fixed sequence of drawers defined by index-chasing in the optimal strategy. Parts of the same paths from drawer to drawer are followed by several different prisoners.

We can avoid redundant recalculation by first obtaining the full set of drawer-chasing cycles that are defined by the sequence of any given shuffle.

We may also notice that the collective fate of the prisoners turns on whether any of the cyclical paths formed by a given shuffle are longer than 50 items. If a shuffle produces a single over-sized cycle, then not every prisoner will be able to reach their card in 50 moves.

The computation below returns a survival failure as soon as a cycle of more than 50 items is found for any given shuffle:

Works with: Python version 3.7
'''100 Prisoners'''

from random import randint, sample


# allChainedPathsAreShort :: Int -> IO (0|1)
def allChainedPathsAreShort(n):
    '''1 if none of the index-chasing cycles in a shuffled
       sample of [1..n] cards are longer than half the
       sample size. Otherwise, 0.
    '''
    limit = n // 2
    xs = range(1, 1 + n)
    shuffled = sample(xs, k=n)

    # A cycle of boxes, drawn from a shuffled
    # sample, which includes the given target.
    def cycleIncluding(target):
        boxChain = [target]
        v = shuffled[target - 1]
        while v != target:
            boxChain.append(v)
            v = shuffled[v - 1]
        return boxChain

    # Nothing if the target list is empty, or if the cycle which contains the
    # first target is larger than half the sample size.
    # Otherwise, just a cycle of enchained boxes containing the first target
    # in the list, tupled with the residue of any remaining targets which
    # fall outside that cycle.
    def boxCycle(targets):
        if targets:
            boxChain = cycleIncluding(targets[0])
            return Just((
                difference(targets[1:])(boxChain),
                boxChain
            )) if limit >= len(boxChain) else Nothing()
        else:
            return Nothing()

    # No cycles longer than half of total box count ?
    return int(n == sum(map(len, unfoldr(boxCycle)(xs))))


# randomTrialResult :: RandomIO (0|1) -> Int -> (0|1)
def randomTrialResult(coin):
    '''1 if every one of the prisoners finds their ticket
       in an arbitrary half of the sample. Otherwise 0.
    '''
    return lambda n: int(all(
        coin(x) for x in range(1, 1 + n)
    ))


# TEST ----------------------------------------------------
# main :: IO ()
def main():
    '''Two sampling techniques constrasted with 100 drawers
       and 100 prisoners, over 100,000 trial runs.
    '''
    halfOfDrawers = randomRInt(0)(1)

    def optimalDrawerSampling(x):
        return allChainedPathsAreShort(x)

    def randomDrawerSampling(x):
        return randomTrialResult(halfOfDrawers)(x)

    # kSamplesWithNBoxes :: Int -> Int -> String
    def kSamplesWithNBoxes(k):
        tests = range(1, 1 + k)
        return lambda n: '\n\n' + fTable(
            str(k) + ' tests of optimal vs random drawer-sampling ' +
            'with ' + str(n) + ' boxes: \n'
        )(fName)(lambda r: '{:.2%}'.format(r))(
            lambda f: sum(f(n) for x in tests) / k
        )([
            optimalDrawerSampling,
            randomDrawerSampling,
        ])

    print(kSamplesWithNBoxes(10000)(10))

    print(kSamplesWithNBoxes(10000)(100))

    print(kSamplesWithNBoxes(100000)(100))


# ------------------------DISPLAY--------------------------

# fTable :: String -> (a -> String) ->
# (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
    '''Heading -> x display function -> fx display function ->
       f -> xs -> tabular string.
    '''
    def go(xShow, fxShow, f, xs):
        ys = [xShow(x) for x in xs]
        w = max(map(len, ys))
        return s + '\n' + '\n'.join(map(
            lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
            xs, ys
        ))
    return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
        xShow, fxShow, f, xs
    )


# fname :: (a -> b) -> String
def fName(f):
    '''Name bound to the given function.'''
    return f.__name__


# ------------------------GENERIC -------------------------

# Just :: a -> Maybe a
def Just(x):
    '''Constructor for an inhabited Maybe (option type) value.
       Wrapper containing the result of a computation.
    '''
    return {'type': 'Maybe', 'Nothing': False, 'Just': x}


# Nothing :: Maybe a
def Nothing():
    '''Constructor for an empty Maybe (option type) value.
       Empty wrapper returned where a computation is not possible.
    '''
    return {'type': 'Maybe', 'Nothing': True}


# difference :: Eq a => [a] -> [a] -> [a]
def difference(xs):
    '''All elements of xs, except any also found in ys.'''
    return lambda ys: list(set(xs) - set(ys))


# randomRInt :: Int -> Int -> IO () -> Int
def randomRInt(m):
    '''The return value of randomRInt is itself
       a function. The returned function, whenever
       called, yields a a new pseudo-random integer
       in the range [m..n].
    '''
    return lambda n: lambda _: randint(m, n)


# unfoldr(lambda x: Just((x, x - 1)) if 0 != x else Nothing())(10)
# -> [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
# unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
def unfoldr(f):
    '''Dual to reduce or foldr.
       Where catamorphism reduces a list to a summary value,
       the anamorphic unfoldr builds a list from a seed value.
       As long as f returns Just(a, b), a is prepended to the list,
       and the residual b is used as the argument for the next
       application of f.
       When f returns Nothing, the completed list is returned.
    '''
    def go(v):
        xr = v, v
        xs = []
        while True:
            mb = f(xr[0])
            if mb.get('Nothing'):
                return xs
            else:
                xr = mb.get('Just')
                xs.append(xr[1])
        return xs
    return lambda x: go(x)


# MAIN ---
if __name__ == '__main__':
    main()
Output:
10000 tests of optimal vs random drawer-sampling with 10 boxes: 

optimalDrawerSampling -> 35.47%
 randomDrawerSampling -> 0.09%

10000 tests of optimal vs random drawer-sampling with 100 boxes: 

optimalDrawerSampling -> 30.40%
 randomDrawerSampling -> 0.00%

100000 tests of optimal vs random drawer-sampling with 100 boxes: 

optimalDrawerSampling -> 31.17%
 randomDrawerSampling -> 0.00%

R[edit]

t = 100000 #number of trials
success.r = rep(0,t) #this will keep track of how many prisoners find their ticket on each trial for the random method
success.o = rep(0,t) #this will keep track of how many prisoners find their ticket on each trial for the optimal method

#random method
for(i in 1:t){
  escape = rep(F,100)
  ticket = sample(1:100)
  for(j in 1:length(prisoner)){
    escape[j] = j %in% sample(ticket,50)
  }
  success.r[i] = sum(escape)
}

#optimal method
for(i in 1:t){
  escape = rep(F,100)
  ticket = sample(1:100)
  for(j in 1:100){
    boxes = 0
    current.box = j
    while(boxes<50 && !escape[j]){
      boxes=boxes+1
      escape[j] = ticket[current.box]==j
      current.box = ticket[current.box]
    }
  }
  success.o[i] = sum(escape)
}

cat("Random method resulted in a success rate of ",100*mean(success.r==100),
    "%.\nOptimal method resulted in a success rate of ",100*mean(success.o==100),"%.",sep="")
Output:
Random method resulted in a success rate of 0%.
Optimal method resulted in a success rate of 31.129%.

QB64[edit]

Const Found = -1, Searching = 0, Status = 1, Tries = 2
Const Attempt = 1, Victories = 2, RandomW = 1, ChainW = 2
Randomize Timer

Dim Shared Prisoners(1 To 100, Status To Tries) As Integer, Drawers(1 To 100) As Integer, Results(1 To 2, 1 To 2) As Integer
Print "100 prisoners"
Print "Random way to search..."
For a = 1 To 2000
    Init
    Results(RandomW, Attempt) = Results(RandomW, Attempt) + 1
    RandomWay
    If verify% Then Results(RandomW, Victories) = Results(RandomW, Victories) + 1
Next

Print: Print "Chain way to search..."
For a = 1 To 2000
    Init
    Results(ChainW, Attempt) = Results(ChainW, Attempt) + 1
    ChainWay
    If verify% Then Results(ChainW, Victories) = Results(ChainW, Victories) + 1
Next
Print: Print "Results: "
Print " Attempts "; Results(RandomW, Attempt); " "; "Victories "; Results(RandomW, Victories); " Ratio:"; Results(RandomW, Victories); "/"; Results(RandomW, Attempt)
Print
Print " Attempts "; Results(ChainW, Attempt); " "; "Victories "; Results(ChainW, Victories); " Ratio:"; Results(ChainW, Victories); "/"; Results(ChainW, Attempt)
End

Function verify%
    Dim In As Integer
    Print "veryfing "
    verify = 0
    For In = 1 To 100
        If Prisoners(In, Status) = Searching Then Exit For
    Next
    If In = 101 Then verify% = Found
End Function

Sub ChainWay
    Dim In As Integer, ChainChoice As Integer
    Print "Chain search"
    For In = 1 To 100
        ChainChoice = In
        Do
            Prisoners(In, Tries) = Prisoners(In, Tries) + 1
            If Drawers(ChainChoice) = In Then Prisoners(In, Status) = Found: Exit Do
            ChainChoice = Drawers(ChainChoice)
        Loop Until Prisoners(In, Tries) = 50
    Next In
End Sub

Sub RandomWay
    Dim In As Integer, RndChoice As Integer
    Print "Random search"
    For In = 1 To 100
        Do
            Prisoners(In, Tries) = Prisoners(In, Tries) + 1
            If Drawers(Int(Rnd * 100) + 1) = In Then Prisoners(In, Status) = Found: Exit Do
        Loop Until Prisoners(In, Tries) = 50
    Next
    Print "Executed "
End Sub


Sub Init
    Dim I As Integer, I2 As Integer
    Print "initialization"
    For I = 1 To 100
        Prisoners(I, Status) = Searching
        Prisoners(I, Tries) = Searching
        Do
            Drawers(I) = Int(Rnd * 100) + 1
            For I2 = 1 To I
                If Drawers(I2) = Drawers(I) Then Exit For
            Next
            If I2 = I Then Exit Do
        Loop
    Next I
    Print "Done "
End Sub

Quackery[edit]

  [ this ] is 100prisoners.qky

  [ dup size 2 / split ]                          is halve     (   [ --> [ [ )

  [ stack ]                                       is successes (     --> s   )

  [ [] swap times [ i join ] shuffle ]            is drawers   (   n --> [   )

  [ false unrot
    temp put 
    dup shuffle
    halve drop
    witheach
      [ dip dup peek
        temp share = if
        [ dip not
          conclude ] ]
    drop
    temp release ]                                is naive     ( [ n --> b   )

  [ false unrot 
    dup temp put
    over size 2 / times 
      [ dip dup peek
        dup temp share = if
        [ rot not unrot
          conclude ] ]
    2drop
    temp release ]                                is smart     ( [ n --> b   )

  [ ]'[ temp put
    drawers
    0 successes put
    dup size times 
      [ dup i temp share do
        successes tally ]
    size successes take = 
    temp release ]                                is prisoners (   n --> b   )
 
  [ say "100 naive prisoners were pardoned "
    0 10000 times [ 100 prisoners naive + ] echo
    say " times out of 10000 simulations." cr

    say "100 smart prisoners were pardoned "
    0 10000 times [ 100 prisoners smart + ] echo
    say " times out of 10000 simulations." cr ]   is simulate  (     -->     )

Output:

/O>  [ $ '100prisoners.qky' loadfile ] now!
...  simulate
... 
100 naive prisoners were pardoned 0 times out of 10000 simulations.
100 smart prisoners were pardoned 3158 times out of 10000 simulations.

Stack empty.

Racket[edit]

#lang racket
(require srfi/1)

(define current-samples (make-parameter 10000))
(define *prisoners* 100)
(define *max-guesses* 50)

(define (evaluate-strategy instance-solved? strategy (s (current-samples)))
  (/ (for/sum ((_ s) #:when (instance-solved? strategy)) 1) s))

(define (build-drawers)
  (list->vector (shuffle (range *prisoners*))))

(define (100-prisoners-problem strategy)
  (every (strategy (build-drawers)) (range *prisoners*)))

(define ((strategy-1 drawers) p)
  (any (λ (_) (= p (vector-ref drawers (random *prisoners*)))) (range *max-guesses*)))

(define ((strategy-2 drawers) p)
  (define-values (_ found?)
    (for/fold ((d p) (found? #f)) ((_ *max-guesses*)) #:break found?
      (let ((card (vector-ref drawers d))) (values card (= card p)))))
  found?)

(define (print-sample-percentage caption f (s (current-samples)))
  (printf "~a: ~a%~%" caption (real->decimal-string (* 100 f) (- (order-of-magnitude s) 2))))

(module+ main
  (print-sample-percentage "random" (evaluate-strategy 100-prisoners-problem strategy-1))
  (print-sample-percentage "optimal" (evaluate-strategy 100-prisoners-problem strategy-2)))
Output:
random: 0.00%
optimal: 31.18%

Raku[edit]

(formerly Perl 6)

Works with: Rakudo version 2019.07.1

Accepts command line parameters to modify the number of prisoners and the number of simulations to run.

Also test with 10 prisoners to verify that the logic is correct for random selection. Random selection should succeed with 10 prisoners at a probability of (1/2)**10, so in 100_000 simulations, should get pardons about .0977 percent of the time.

unit sub MAIN (:$prisoners = 100, :$simulations = 10000);
my @prisoners = ^$prisoners;
my $half = floor +@prisoners / 2;

sub random ($n) {
    ^$n .race.map( {
        my @drawers = @prisoners.pick: *;
        @prisoners.map( -> $prisoner {
            my $found = 0;
            for @drawers.pick($half) -> $card {
                $found = 1 and last if $card == $prisoner
            }
            last unless $found;
            $found
        }
        ).sum == @prisoners
    }
    ).grep( *.so ).elems / $n * 100
}

sub optimal ($n) {
    ^$n .race.map( {
        my @drawers = @prisoners.pick: *;
        @prisoners.map( -> $prisoner {
            my $found = 0;
            my $card = @drawers[$prisoner];
            if $card == $prisoner {
                $found = 1
            } else {
                for ^($half - 1) {
                    $card = @drawers[$card];
                    $found = 1 and last if $card == $prisoner
                }
            }
            last unless $found;
            $found
        }
        ).sum == @prisoners
    }
    ).grep( *.so ).elems / $n * 100
}

say "Testing $simulations simulations with $prisoners prisoners.";
printf " Random play wins: %.3f%% of simulations\n", random $simulations;
printf "Optimal play wins: %.3f%% of simulations\n", optimal $simulations;
Output:

With defaults

Testing 10000 simulations with 100 prisoners.
 Random play wins: 0.000% of simulations
Optimal play wins: 30.510% of simulations

With passed parameters: --prisoners=10, --simulations=100000

Testing 100000 simulations with 10 prisoners.
 Random play wins: 0.099% of simulations
Optimal play wins: 35.461% of simulations

Red[edit]

Red []

K_runs: 100000
repeat n 100 [append rand_arr: []  n]              ;; define array/series with numbers 1..100

;;-------------------------------
strat_optimal: function [pris ][
;;-------------------------------
  locker: pris                                    ;; start with locker equal to prisoner number
  loop 50 [
    if Board/:locker = pris [ return true ]       ;; locker with prisoner number found
    locker: Board/:locker
  ]
  false                                           ;; number not found - fail
]
;;-------------------------------
strat_rand: function [pris ][
;;-------------------------------
  random rand_arr                                                 ;; define set of  random lockers
  repeat n 50 [ if Board/(rand_arr/:n) = pris [ return true ]  ]  ;; try first 50, found ? then return success
  false 
]

;;------------------------------
check_board: function [ strat][
;;------------------------------
repeat pris 100 [                                                   ;; for each prisoner
  either  strat = 'optimal [ unless strat_optimal pris [return false ]  ]  
                            [ unless strat_rand pris [return false ]  ]  
]  
  true                                                  ;; all 100 prisoners passed test
]

saved: saved_rand: 0                                    ;; count all saved runs per strategy
loop K_runs [
  Board: random copy rand_arr                           ;; new board for every run
  if  check_board 'optimal [saved: saved + 1]           ;; optimal stategy
  if  check_board 'rand [saved_rand: saved_rand + 1]  ;; random strategy
]

print ["runs" k_runs newline  "Percent saved opt.strategy:" saved * 100.0 / k_runs ]
print ["Percent saved random strategy:" saved_rand * 100.0 / k_runs ]
Output:

runs 100000 Percent saved opt.strategy: 31.165 Percent saved random strategy: 0.0

REXX[edit]

/*REXX program to simulate the problem of 100 prisoners:  random,  and optimal strategy.*/
parse arg men trials seed .                      /*obtain optional arguments from the CL*/
if    men=='' |    men==","  then    men=    100 /*number of   prisoners   for this run.*/
if trials=='' | trials==","  then trials= 100000 /*  "     "  simulations   "    "   "  */
if datatype(seed, 'W')  then call random ,,seed  /*seed for the random number generator.*/
try= men % 2;                swaps= men * 3      /*number tries for searching for a card*/
$.1= ' a simple ';           $.2= "an optimal"   /*literals used for the SAY instruction*/
say center(' running'  commas(trials)   "trials with"  commas(men)  'prisoners ', 70, "═")
say
    do strategy=1  for 2;    pardons= 0          /*perform the two types of strategies. */

      do trials;             call gCards         /*do trials for a strategy;  gen cards.*/
        do p=1  for men  until failure           /*have each prisoner go through process*/
        if strategy==1  then failure= simple()   /*Is 1st strategy?  Use simple strategy*/
                        else failure= picker()   /* " 2nd     "       "  optimal   "    */
        end   /*p*/                              /*FAILURE ≡ 1?  Then a prisoner failed.*/
      if #==men  then pardons= pardons + 1       /*was there a pardon of all prisoners? */
      end     /*trials*/                         /*if 1 prisoner fails, then they all do*/

    pc= format( pardons/trials*100, , 3);                           _= left('', pc<10)
    say right('Using', 9)  $.strategy  "strategy yields pardons "   _||pc"%  of the time."
    end       /*strategy*/
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas:  parse arg _;  do c=length(_)-3  to 1  by -3; _= insert(',', _, c); end;  return _
/*──────────────────────────────────────────────────────────────────────────────────────*/
gCards: #= 0;                do j=1  for men;  @.j= j             /*define seq. of cards*/
                             end   /*j*/                          /*same as seq. of men.*/
               do swaps;             a= random(1, men)            /*get 1st rand number.*/
                   do until  b\==a;  b= random(1, men)            /* "  2nd   "     "   */
                   end   /*until*/                                /* [↑] ensure A ¬== B */
               parse value  @.a @.b  with  @.b @.a                /*swap 2 random cards.*/
               end       /*swaps*/;  return
/*──────────────────────────────────────────────────────────────────────────────────────*/
simple: !.= 0; do try;         do until !.?==0; ?= random(1, men) /*get random card ··· */
                               end   /*until*/                    /*··· not used before.*/
               if @.?==p  then do;   #= #+1;  return 0;  end      /*found his own card? */
               !.?= 1                                             /*flag as being used. */
               end   /*try*/;        return 1                     /*didn't find his card*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
picker: ?= p;  do try; if @.?==p  then do;   #= #+1;    return 0  /*Found his own card? */
                                       end       /* [↑]  indicate success for prisoner. */
               ?= @.?                            /*choose next drawer from current card.*/
               end   /*try*/;        return 1    /*choose half of the number of drawers.*/
output   when using the default inputs:
══════════════ running 100,000 trials with 100 prisoners ══════════════

    Using  a simple  strategy yields pardons   0.000%  of the time.
    Using an optimal strategy yields pardons  31.186%  of the time.
output   when using the input of:     10
══════════════ running 100,000 trials with 10 prisoners ══════════════

    Using  a simple  strategy yields pardons   0.086%  of the time.
    Using an optimal strategy yields pardons  31.204%  of the time.

Ruby[edit]

prisoners = [*1..100]
N = 10_000
generate_rooms = ->{ [nil]+[*1..100].shuffle }
 
res = N.times.count do
  rooms = generate_rooms[]
  prisoners.all? {|pr| rooms[1,100].sample(50).include?(pr)}
end
puts "Random strategy : %11.4f %%" % (res.fdiv(N) * 100)

res = N.times.count do
  rooms = generate_rooms[]
  prisoners.all? do |pr|
    cur_room = pr
    50.times.any? do
      found = (rooms[cur_room] == pr)
      cur_room = rooms[cur_room]
      found
    end
  end
end
puts "Optimal strategy: %11.4f %%" % (res.fdiv(N) * 100)
Output:
Random strategy :      0.0000 %
Optimal strategy:     30.7400 %

Rust[edit]

Fairly naive implementation. Could probably be made more idiomatic. Depends on extern rand crate.

Cargo.toml

[dependencies]
rand = '0.7.2'

src/main.rs

extern crate rand;

use rand::prelude::*;

// Do a full run of checking boxes in a random order for a single prisoner
fn check_random_boxes(prisoner: u8, boxes: &[u8]) -> bool {
    let checks = {
        let mut b: Vec<u8> = (1u8..=100u8).collect();
        b.shuffle(&mut rand::thread_rng());
        b
    };
    checks.into_iter().take(50).any(|check| boxes[check as usize - 1] == prisoner)
}

// Do a full run of checking boxes in the optimized order for a single prisoner
fn check_ordered_boxes(prisoner: u8, boxes: &[u8]) -> bool {
    let mut next_check = prisoner;
    (0..50).any(|_| {
        next_check = boxes[next_check as usize - 1];
        next_check == prisoner
    })
}

fn main() {
    let mut boxes: Vec<u8> = (1u8..=100u8).collect();

    let trials = 100000;

    let ordered_successes = (0..trials).filter(|_| {
        boxes.shuffle(&mut rand::thread_rng());
        (1u8..=100u8).all(|prisoner| check_ordered_boxes(prisoner, &boxes))
    }).count();

    let random_successes = (0..trials).filter(|_| {
        boxes.shuffle(&mut rand::thread_rng());
        (1u8..=100u8).all(|prisoner| check_random_boxes(prisoner, &boxes))
    }).count();

    println!("{} / {} ({:.02}%) successes in ordered", ordered_successes, trials, ordered_successes as f64 * 100.0 / trials as f64);
    println!("{} / {} ({:.02}%) successes in random", random_successes, trials, random_successes as f64 * 100.0 / trials as f64);

}
Output:
31106 / 100000 (31.11%) successes in ordered
0 / 100000 (0.00%) successes in random

Sather[edit]

class MAIN is
   shuffle (a: ARRAY{INT}) is
      ARR_PERMUTE_ALG{INT, ARRAY{INT}}::shuffle(a);
   end;

   try_random (n: INT, drawers: ARRAY{INT}, tries: INT): BOOL is
      my_tries ::= drawers.inds; shuffle(my_tries);
      loop tries.times!;
         if drawers[my_tries.elt!] = n then return true; end;
      end;
      return false;
   end;

   try_optimal (n: INT, drawers: ARRAY{INT}, tries: INT): BOOL is
      num ::= n;
      loop tries.times!;
         num := drawers[num];
         if num = n then return true; end;
      end;
      return false;
   end;

   stats (label: STR, rounds, successes: INT): STR is
      return #FMT("<^###########>: <#######> rounds. Successes: <#######> (<##.###>%%)\n",
                   label, rounds, successes, (successes.flt / rounds.flt)*100.0).str;
   end;

   try (name: STR, nrounds, ndrawers, npris, ntries: INT,
        strategy: ROUT{INT,ARRAY{INT},INT}:BOOL)
   is
      drawers: ARRAY{INT} := #(ndrawers);
      loop drawers.set!(drawers.ind!); end;
      successes ::= 0;
      loop nrounds.times!;
         shuffle(drawers);
         success ::= true;
         loop
            n ::= npris.times!;
            if ~strategy.call(n, drawers, ntries) then
               success := false;
               break!;
            end;
         end;
         if success then successes := successes + 1; end;
      end;
      #OUT + stats(name, nrounds, successes);
   end;

   main is
      RND::seed := #TIMES.wall_time;
      #OUT +"100 prisoners, 100 drawers, 50 tries:\n";
      try("random",  100000, 100, 100, 50, bind(try_random(_, _, _)));
      try("optimal", 100000, 100, 100, 50, bind(try_optimal(_, _, _)));

      #OUT +"\n10 prisoners, 10 drawers, 5 tries:\n";
      try("random",  100000, 10, 10, 5, bind(try_random(_, _, _)));
      try("optimal", 100000, 10, 10, 5, bind(try_optimal(_, _, _)));
   end;
end;
Output:
100 prisoners, 100 drawers, 50 tries:
random      :  100000 rounds. Successes:       0 ( 0.000%)
optimal     :  100000 rounds. Successes:   31378 (31.378%)

10 prisoners, 10 drawers, 5 tries:
random      :  100000 rounds. Successes:     113 ( 0.113%)
optimal     :  100000 rounds. Successes:   35633 (35.633%)

Scala[edit]

Translation of: Java
import scala.util.Random
import scala.util.control.Breaks._

object Main {
  def playOptimal(n: Int): Boolean = {
    val secretList = Random.shuffle((0 until n).toBuffer)

    for (i <- secretList.indices) {
      var prev = i
      breakable {
        for (_ <- 0 until secretList.size / 2) {
          if (secretList(prev) == i) {
            break()
          }
          prev = secretList(prev)
        }
        return false
      }
    }

    true
  }

  def playRandom(n: Int): Boolean = {
    val secretList = Random.shuffle((0 until n).toBuffer)

    for (i <- secretList.indices) {
      val trialList = Random.shuffle((0 until n).toBuffer)

      breakable {
        for (j <- 0 until trialList.size / 2) {
          if (trialList(j) == i) {
            break()
          }
        }
        return false
      }
    }

    true
  }

  def exec(n: Int, p: Int, play: Int => Boolean): Double = {
    var succ = 0.0
    for (_ <- 0 until n) {
      if (play(p)) {
        succ += 1
      }
    }
    (succ * 100.0) / n
  }

  def main(args: Array[String]): Unit = {
    val n = 100000
    val p = 100
    printf("# of executions: %,d\n", n)
    printf("Optimal play success rate: %f%%\n", exec(n, p, playOptimal))
    printf("Random play success rate: %f%%\n", exec(n, p, playRandom))
  }
}
Output:
# of executions: 100,000
Optimal play success rate: 31.201000%
Random play success rate: 0.000000%

Swift[edit]

import Foundation

struct PrisonersGame {
  let strategy: Strategy
  let numPrisoners: Int
  let drawers: [Int]

  init(numPrisoners: Int, strategy: Strategy) {
    self.numPrisoners = numPrisoners
    self.strategy = strategy
    self.drawers = (1...numPrisoners).shuffled()
  }

  @discardableResult
  func play() -> Bool {
    for num in 1...numPrisoners {
      guard findNumber(num) else {
        return false
      }
    }

    return true
  }

  private func findNumber(_ num: Int) -> Bool {
    var tries = 0
    var nextDrawer = num - 1

    while tries < 50 {
      tries += 1

      switch strategy {
      case .random where drawers.randomElement()! == num:
        return true
      case .optimum where drawers[nextDrawer] == num:
        return true
      case .optimum:
        nextDrawer = drawers[nextDrawer] - 1
      case _:
        continue
      }
    }

    return false
  }

  enum Strategy {
    case random, optimum
  }
}

let numGames = 100_000
let lock = DispatchSemaphore(value: 1)
var done = 0

print("Running \(numGames) games for each strategy")

DispatchQueue.concurrentPerform(iterations: 2) {i in
  let strat = i == 0 ? PrisonersGame.Strategy.random : .optimum
  var numPardoned = 0

  for _ in 0..<numGames {
    let game = PrisonersGame(numPrisoners: 100, strategy: strat)

    if game.play() {
      numPardoned += 1
    }
  }

  print("Probability of pardon with \(strat) strategy: \(Double(numPardoned) / Double(numGames))")

  lock.wait()
  done += 1
  lock.signal()

  if done == 2 {
    exit(0)
  }
}

dispatchMain()
Output:
Running 100000 games for each strategy
Probability of pardon with optimum strategy: 0.31099
Probability of pardon with random strategy: 0.0

Tcl[edit]

Translation of: Common Lisp
set Samples 10000
set Prisoners 100
set MaxGuesses 50
set Strategies {random optimal}

# returns a random number between 0 and N-1.
proc random {n} {
  expr int(rand()*$n)
}

# Returns a list from 0 to N-1.
proc range {n} {
  set res {}
  for {set i 0} {$i < $n} {incr i} {
    lappend res $i
  }
  return $res
}

# Returns shuffled LIST.
proc nshuffle {list} {
    set len [llength $list]
    while {$len} {
        set n [expr {int($len * rand())}]
        set tmp [lindex $list $n]
        lset list $n [lindex $list [incr len -1]]
        lset list $len $tmp
    }
    return $list
}

# Returns a list of shuffled drawers.
proc buildDrawers {} {
  global Prisoners
  nshuffle [range $Prisoners]
}

# Returns true if P is found in DRAWERS within $MaxGuesses attempts using a
# random strategy.
proc randomStrategy {drawers p} {
  global Prisoners MaxGuesses
  foreach i [range $MaxGuesses] {
    if {$p == [lindex $drawers [random $Prisoners]]} {
      return 1
    }
  }
  return 0
}

# Returns true if P is found in DRAWERS within $MaxGuesses attempts using an
# optimal strategy.
proc optimalStrategy {drawers p} {
  global Prisoners MaxGuesses
  set j $p
  foreach i [range $MaxGuesses] {
    set k [lindex $drawers $j]
    if {$k == $p} {
      return 1
    }
    set j $k
  }
  return 0
}

# Returns true if all prisoners find their number using the given STRATEGY.
proc run100prisonersProblem {strategy} {
  global Prisoners
  set drawers [buildDrawers]
  foreach p [range $Prisoners] {
    if {![$strategy $drawers $p]} {
      return 0
    }
  }
  return 1
}

# Runs the given STRATEGY $Samples times and returns the number of times all
# prisoners succeed.
proc sampling {strategy} {
  global Samples
  set successes 0
  foreach s [range $Samples] {
    if {[run100prisonersProblem $strategy]} {
      incr successes
    }
  }
  return $successes
}

# Returns true if the given STRING starts with a vowel.
proc startsWithVowel {string} {
  expr [lsearch -exact {a e i o u} [string index $string 0]] >= 0
}

# Runs each of the STRATEGIES and prints a report on how well they
# worked.
proc compareStrategies {strategies} {
  global Samples
  set fmt "Using %s %s strategy, the prisoners were freed in %5.2f%% of the cases."
  foreach strategy $strategies {
    set article [expr [startsWithVowel $strategy] ? {"an"} : {"a"}]
    set pct [expr [sampling ${strategy}Strategy] / $Samples.0 * 100]
    puts [format $fmt $article $strategy $pct]
  }
}

compareStrategies $Strategies
Output:
Using a random strategy, the prisoners were freed in  0.00% of the cases.
Using an optimal strategy, the prisoners were freed in 32.35% of the cases.

Transact-SQL[edit]

School example[edit]

Works with: Transact-SQL version SQL Server 2017
USE rosettacode;
GO

SET NOCOUNT ON;
GO

CREATE TABLE dbo.numbers (n INT PRIMARY KEY);
GO

-- NOTE If you want to play more than 10000 games, you need to extend the query generating the numbers table by adding
-- next cross joins. Now the table contains enough values to solve the task and it takes less processing time.

WITH sample100 AS (
    SELECT TOP(100) object_id
    FROM master.sys.objects
)
INSERT numbers
    SELECT ROW_NUMBER() OVER (ORDER BY A.object_id) AS n
    FROM sample100 AS A
        CROSS JOIN sample100 AS B;
GO

CREATE TABLE dbo.drawers (drawer INT PRIMARY KEY, card INT);
GO

CREATE TABLE dbo.results (strategy VARCHAR(10), game INT, result BIT, PRIMARY KEY (game, strategy));
GO

CREATE PROCEDURE dbo.shuffleDrawers @prisonersCount INT
AS BEGIN
    SET NOCOUNT ON;

    IF NOT EXISTS (SELECT * FROM drawers)
        INSERT drawers (drawer, card)
        SELECT n AS drawer, n AS card
        FROM numbers
        WHERE n <= @prisonersCount;

    DECLARE @randoms TABLE (n INT, random INT);
    DECLARE @n INT = 1;
    WHILE @n <= @prisonersCount BEGIN
        INSERT @randoms VALUES (@n, ROUND(RAND() * (@prisonersCount - 1), 0) + 1);

        SET @n = @n + 1;
    END;

    WITH ordered AS (
        SELECT ROW_NUMBER() OVER (ORDER BY random ASC) AS drawer,
            n AS card
        FROM @randoms
    )
    UPDATE drawers
    SET card = o.card
    FROM drawers AS s
        INNER JOIN ordered AS o
            ON o.drawer = s.drawer;
END
GO

CREATE PROCEDURE dbo.find @prisoner INT, @strategy VARCHAR(10)
AS BEGIN
    -- A prisoner can open no more than 50 drawers.
    DECLARE @drawersCount INT = (SELECT COUNT(*) FROM drawers);
    DECLARE @openMax INT = @drawersCount / 2;

    -- Prisoners start outside the room.
    DECLARE @card INT = NULL;
    DECLARE @open INT = 1;
    WHILE @open <= @openMax BEGIN
        -- A prisoner tries to find his own number.
        IF @strategy = 'random' BEGIN
            DECLARE @random INT = ROUND(RAND() * (@drawersCount - 1), 0) + 1;
            SET @card = (SELECT TOP(1) card FROM drawers WHERE drawer = @random);
        END
        IF @strategy = 'optimal' BEGIN
            IF @card IS NULL BEGIN
                SET @card = (SELECT TOP(1) card FROM drawers WHERE drawer = @prisoner);
            END ELSE BEGIN
                SET @card = (SELECT TOP(1) card FROM drawers WHERE drawer = @card);
            END
        END

        -- A prisoner finding his own number is then held apart from the others.
        IF @card = @prisoner
            RETURN 1;

        SET @open = @open + 1;
    END

    RETURN 0;
END
GO

CREATE PROCEDURE dbo.playGame @gamesCount INT, @strategy VARCHAR(10), @prisonersCount INT = 100
AS BEGIN
    SET NOCOUNT ON;

    IF @gamesCount <> (SELECT COUNT(*) FROM results WHERE strategy = @strategy) BEGIN
        DELETE results
        WHERE strategy = @strategy;

        INSERT results (strategy, game, result)
        SELECT @strategy AS strategy, n AS game, 0 AS result
        FROM numbers
        WHERE n <= @gamesCount;
    END

    UPDATE results
    SET result = 0
    WHERE strategy = @strategy;

    DECLARE @game INT = 1;
    WHILE @game <= @gamesCount BEGIN
        -- A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
        -- Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
        EXECUTE shuffleDrawers @prisonersCount;

        -- A prisoner tries to find his own number.
        -- Prisoners start outside the room.
        -- They can decide some strategy before any enter the room.
        DECLARE @prisoner INT = 1;
        DECLARE @found INT = 0;
        WHILE @prisoner <= @prisonersCount BEGIN
            EXECUTE @found = find @prisoner, @strategy;
            IF @found = 1
                SET @prisoner = @prisoner + 1;
            ELSE
                BREAK;
        END;

        -- If all 100 findings find their own numbers then they will all be pardoned. If any don't then all sentences stand.
        IF @found = 1
            UPDATE results SET result = 1 WHERE strategy = @strategy AND game = @game;
    
        SET @game = @game + 1;
    END
END
GO

CREATE FUNCTION dbo.computeProbability(@strategy VARCHAR(10))
RETURNS decimal (18, 2)
AS BEGIN
    RETURN (
        SELECT (SUM(CAST(result AS INT)) * 10000 / COUNT(*)) / 100
        FROM results
        WHERE strategy = @strategy
    );
END
GO

-- Simulate several thousand instances of the game:
DECLARE @gamesCount INT = 2000;

-- ...where the prisoners randomly open drawers.
EXECUTE playGame @gamesCount, 'random';

-- ...where the prisoners use the optimal strategy mentioned in the Wikipedia article.
EXECUTE playGame @gamesCount, 'optimal';

-- Show and compare the computed probabilities of success for the two strategies.
DECLARE @log VARCHAR(max);
SET @log = CONCAT('Games count: ', @gamesCount);
RAISERROR (@log, 0, 1) WITH NOWAIT;
SET @log = CONCAT('Probability of success with "random" strategy: ', dbo.computeProbability('random'));
RAISERROR (@log, 0, 1) WITH NOWAIT;
SET @log = CONCAT('Probability of success with "optimal" strategy: ', dbo.computeProbability('optimal'));
RAISERROR (@log, 0, 1) WITH NOWAIT;
GO

DROP FUNCTION dbo.computeProbability;
DROP PROCEDURE dbo.playGame;
DROP PROCEDURE dbo.find;
DROP PROCEDURE dbo.shuffleDrawers;
DROP TABLE dbo.results;
DROP TABLE dbo.drawers;
DROP TABLE dbo.numbers;
GO

Output:

Games count: 2000
Probability of success with "random" strategy: 0.00 
Probability of success with "optimal" strategy: 31.00

VBA/Visual Basic[edit]

Sub HundredPrisoners()

    NumberOfPrisoners = Int(InputBox("Number of Prisoners", "Prisoners", 100))
    Tries = Int(InputBox("Numer of Tries", "Tries", 1000))
    Selections = Int(InputBox("Number of Selections", "Selections", NumberOfPrisoners / 2))

    StartTime = Timer

    AllFoundOptimal = 0
    AllFoundRandom = 0
    AllFoundRandomMem = 0

    For i = 1 To Tries
        OptimalCount = HundredPrisoners_Optimal(NumberOfPrisoners, Selections)
        RandomCount = HundredPrisoners_Random(NumberOfPrisoners, Selections)
        RandomMemCount = HundredPrisoners_Random_Mem(NumberOfPrisoners, Selections)
        
        If OptimalCount = NumberOfPrisoners Then
            AllFoundOptimal = AllFoundOptimal + 1
        End If
        If RandomCount = NumberOfPrisoners Then
            AllFoundRandom = AllFoundRandom + 1
        End If
        If RandomMemCount = NumberOfPrisoners Then
            AllFoundRandomMem = AllFoundRandomMem + 1
        End If
    Next i


    ResultString = "Optimal: " & AllFoundOptimal & " of " & Tries & ": " & AllFoundOptimal / Tries * 100 & "%"
    ResultString = ResultString & Chr(13) & "Random: " & AllFoundRandom & " of " & Tries & ": " & AllFoundRandom / Tries * 100 & "%"
    ResultString = ResultString & Chr(13) & "RandomMem: " & AllFoundRandomMem & " of " & Tries & ": " & AllFoundRandomMem / Tries * 100 & "%"

    EndTime = Timer

    ResultString = ResultString & Chr(13) & "Elapsed Time: " & Round(EndTime - StartTime, 2) & " s"
    ResultString = ResultString & Chr(13) & "Trials/sec: " & Tries / Round(EndTime - StartTime, 2)

    MsgBox ResultString, vbOKOnly, "Results"

End Sub

Function HundredPrisoners_Optimal(ByVal NrPrisoners, ByVal NrSelections) As Long
    Dim DrawerArray() As Long
    
    ReDim DrawerArray(NrPrisoners - 1)
    
    For Counter = LBound(DrawerArray) To UBound(DrawerArray)
        DrawerArray(Counter) = Counter + 1
    Next Counter

    FisherYates DrawerArray
    
    For i = 1 To NrPrisoners
        NumberFromDrawer = DrawerArray(i - 1)
        For j = 1 To NrSelections - 1
            If NumberFromDrawer = i Then
                FoundOwnNumber = FoundOwnNumber + 1
                Exit For
            End If
            NumberFromDrawer = DrawerArray(NumberFromDrawer - 1)
        Next j
    Next i
    HundredPrisoners_Optimal = FoundOwnNumber
End Function

Function HundredPrisoners_Random(ByVal NrPrisoners, ByVal NrSelections) As Long
    Dim DrawerArray() As Long
    ReDim DrawerArray(NrPrisoners - 1)
    
    FoundOwnNumber = 0
    
    For Counter = LBound(DrawerArray) To UBound(DrawerArray)
        DrawerArray(Counter) = Counter + 1
    Next Counter

    FisherYates DrawerArray
    
    
    For i = 1 To NrPrisoners
        For j = 1 To NrSelections
            RandomDrawer = Int(NrPrisoners * Rnd)
            NumberFromDrawer = DrawerArray(RandomDrawer)
            If NumberFromDrawer = i Then
                FoundOwnNumber = FoundOwnNumber + 1
                Exit For
            End If
        Next j
    Next i
    HundredPrisoners_Random = FoundOwnNumber
End Function

Function HundredPrisoners_Random_Mem(ByVal NrPrisoners, ByVal NrSelections) As Long
    Dim DrawerArray() As Long
    Dim SelectionArray() As Long
    ReDim DrawerArray(NrPrisoners - 1)
    ReDim SelectionArray(NrPrisoners - 1)
    
    HundredPrisoners_Random_Mem = 0
    FoundOwnNumberMem = 0
    
    For Counter = LBound(DrawerArray) To UBound(DrawerArray)
        DrawerArray(Counter) = Counter + 1
    Next Counter
    
    For Counter = LBound(SelectionArray) To UBound(SelectionArray)
        SelectionArray(Counter) = Counter + 1
    Next Counter

    FisherYates DrawerArray
    
    For i = 1 To NrPrisoners
        FisherYates SelectionArray
        For j = 1 To NrSelections
            NumberFromDrawer = DrawerArray(SelectionArray(j - 1) - 1)
            If NumberFromDrawer = i Then
                FoundOwnNumberMem = FoundOwnNumberMem + 1
                Exit For
            End If
        Next j
    Next i
    HundredPrisoners_Random_Mem = FoundOwnNumberMem
End Function

Sub FisherYates(ByRef InputArray() As Long)
 
    Dim Temp As Long
    Dim PosRandom As Long
    Dim Counter As Long
    Dim Upper As Long
    Dim Lower As Long
     
    Lower = LBound(InputArray)
    Upper = UBound(InputArray)
     
    Randomize
     
    For Counter = Upper To (Lower + 1) Step -1
        PosRandom = CLng(Int((Counter - Lower + 1) * Rnd + Lower))
        Temp = InputArray(Counter)
        InputArray(Counter) = InputArray(PosRandom)
        InputArray(PosRandom) = Temp
    Next Counter
 
End Sub
Output:
Optimal: 29090 of 100000: 29.09%
Random: 0 of 100000: 0%
RandomMem: 0 of 100000: 0%
Elapsed Time: 388.41 s

Visual Basic .NET[edit]

Translation of: C#
Module Module1

    Function PlayOptimal() As Boolean
        Dim secrets = Enumerable.Range(0, 100).OrderBy(Function(a) Guid.NewGuid).ToList

        For p = 1 To 100
            Dim success = False

            Dim choice = p - 1
            For i = 1 To 50
                If secrets(choice) = p - 1 Then
                    success = True
                    Exit For
                End If
                choice = secrets(choice)
            Next

            If Not success Then
                Return False
            End If
        Next

        Return True
    End Function

    Function PlayRandom() As Boolean
        Dim secrets = Enumerable.Range(0, 100).OrderBy(Function(a) Guid.NewGuid).ToList

        For p = 1 To 100
            Dim choices = Enumerable.Range(0, 100).OrderBy(Function(a) Guid.NewGuid).ToList

            Dim success = False
            For i = 1 To 50
                If choices(i - 1) = p Then
                    success = True
                    Exit For
                End If
            Next

            If Not success Then
                Return False
            End If
        Next

        Return True
    End Function

    Function Exec(n As UInteger, play As Func(Of Boolean))
        Dim success As UInteger = 0
        For i As UInteger = 1 To n
            If play() Then
                success += 1
            End If
        Next
        Return 100.0 * success / n
    End Function

    Sub Main()
        Dim N = 1_000_000
        Console.WriteLine("# of executions: {0}", N)
        Console.WriteLine("Optimal play success rate: {0:0.00000000000}%", Exec(N, AddressOf PlayOptimal))
        Console.WriteLine(" Random play success rate: {0:0.00000000000}%", Exec(N, AddressOf PlayRandom))
    End Sub

End Module
Output:
# of executions: 1000000
Optimal play success rate: 31.12990000000%
 Random play success rate: 0.00000000000%

VBScript[edit]

option explicit
const npris=100
const ntries=50
const ntests=1000.
dim drawer(100),opened(100),i
for i=1 to npris: drawer(i)=i:next
shuffle drawer
wscript.echo rf(tests(false)/ntests*100,10," ")  &" % success for random"
wscript.echo rf(tests(true) /ntests*100,10," ")  &" % success for optimal strategy"

function rf(v,n,s) rf=right(string(n,s)& v,n):end function 

sub shuffle(d) 'knut's shuffle
dim i,j,t
randomize timer
for i=1 to npris
   j=int(rnd()*i+1)
   t=d(i):d(i)=d(j):d(j)=t
next
end sub

function tests(strat)
dim cntp,i,j
tests=0
for i=1 to ntests
  shuffle drawer
  cntp=0
  if strat then
      for j=1 to npris
	if not trystrat(j) then exit for
      next
  else		
     for j=1 to npris
       if not tryrand(j) then exit for
     next      
  end if
  if j>=npris then tests=tests+1
next
end function 
	   
function tryrand(pris)
  dim i,r 
	erase opened
  for i=1 to ntries
    do 
      r=int(rnd*npris+1)
    loop until opened(r)=false
    opened(r)=true
    if drawer(r)= pris then tryrand=true : exit function
  next
  tryrand=false
end function   

function trystrat(pris)
  dim i,r
  r=pris
  for i=1 to ntries
    if drawer(r)= pris then trystrat=true	:exit function
    r=drawer(r)
  next
  trystrat=false
end function

Output:

         0 % success for random
      32.9 % success for optimal strategy

Vlang[edit]

Translation of: Wren
import rand
import rand.seed
// Uses 0-based numbering rather than 1-based numbering throughout.
fn do_trials(trials int, np int, strategy string) {
    mut pardoned := 0
    for _ in 0..trials {
        mut drawers := []int{len: 100, init: it}
        rand.shuffle<int>(mut drawers) or {panic('shuffle failed')}
        mut next_trial := false
        for p in 0..np {
            mut next_prisoner := false
            if strategy == "optimal" {
                mut prev := p
                for _ in 0..50 {
                    this := drawers[prev]
                    if this == p {
                        next_prisoner = true
                        break
                    }
                    prev = this
                }
            } else {
                // Assumes a prisoner remembers previous drawers (s)he opened
                // and chooses at random from the others.
                mut opened := [100]bool{}
                for _ in 0..50 {
                    mut n := 0
                    for {
                        n = rand.intn(100) or {0}
                        if !opened[n] {
                            opened[n] = true
                            break
                        }
                    }
                    if drawers[n] == p {
                        next_prisoner = true
                        break
                    }
                }
            }
            if !next_prisoner {
                next_trial = true
                break
            }
        }
        if !next_trial {
            pardoned++
        }
    }
    rf := f64(pardoned) / f64(trials) * 100
    println("  strategy = ${strategy:-7}  pardoned = ${pardoned:-6} relative frequency = ${rf:-5.2f}%\n")
}
 
fn main() {
    rand.seed(seed.time_seed_array(2))
    trials := 100000
    for np in [10, 100] {
        println("Results from $trials trials with $np prisoners:\n")
        for strategy in ["random", "optimal"] {
            do_trials(trials, np, strategy)
        }
    }
}
Output:

Sample run:

Results from 100000 trials with 10 prisoners:

  strategy = random   pardoned = 91     relative frequency = 0.09 %

  strategy = optimal  pardoned = 31321  relative frequency = 31.32%

Results from 100000 trials with 100 prisoners:

  strategy = random   pardoned = 0      relative frequency = 0.00 %

  strategy = optimal  pardoned = 31318  relative frequency = 31.32%

Wren[edit]

Translation of: Go
Library: Wren-fmt
import "random" for Random
import "/fmt" for Fmt

var rand = Random.new()

var doTrials = Fn.new{ |trials, np, strategy|
    var pardoned = 0
    for (t in 0...trials) {
        var drawers = List.filled(100, 0)
        for (i in 0..99) drawers[i] = i
        rand.shuffle(drawers)
        var nextTrial = false
        for (p in 0...np) {
            var nextPrisoner = false
            if (strategy == "optimal") {
                var prev = p
                for (d in 0..49) {
                    var curr = drawers[prev]
                    if (curr == p) {
                        nextPrisoner = true
                        break
                    }
                    prev = curr
                }
            } else {
                var opened = List.filled(100, false)
                for (d in 0..49) {
                    var n
                    while (true) {
                        n = rand.int(100)
                        if (!opened[n]) {
                            opened[n] = true
                            break
                        }
                    }
                    if (drawers[n] == p) {
                        nextPrisoner = true
                        break
                    }
                }
            }
            if (!nextPrisoner) {
               nextTrial = true
               break
            }
        }
        if (!nextTrial) pardoned = pardoned + 1
    }
    var rf = pardoned/trials * 100
    Fmt.print("  strategy = $-7s  pardoned = $,6d relative frequency = $5.2f\%\n", strategy, pardoned, rf)
}

var trials = 1e5
for (np in [10, 100]) {
    Fmt.print("Results from $,d trials with $d prisoners:\n", trials, np)
    for (strategy in ["random", "optimal"]) doTrials.call(trials, np, strategy)
}
Output:

Sample run:

Results from 100,000 trials with 10 prisoners:

  strategy = random   pardoned =     98 relative frequency =  0.10%

  strategy = optimal  pardoned = 31,212 relative frequency = 31.21%

Results from 100,000 trials with 100 prisoners:

  strategy = random   pardoned =      0 relative frequency =  0.00%

  strategy = optimal  pardoned = 31,139 relative frequency = 31.14%

XPL0[edit]

int     Drawer(100);

proc KShuffle;          \Randomly rearrange the cards in the drawers
\(Woe unto thee if Stattolo shuffle is used instead of Knuth shuffle.)
int  I, J, T;
[for I:= 100-1 downto 1 do
    [J:= Ran(I+1);      \range [0..I]
    T:= Drawer(I);  Drawer(I):= Drawer(J);  Drawer(J):= T;
    ];
];

func Stategy2;          \Return 'true' if stragegy succeeds
int  Prisoner, Card, Try;
[for Prisoner:= 1 to 100 do
   [Card:= Drawer(Prisoner-1);
   Try:= 1;
   loop [if Card = Prisoner then quit;
        if Try >= 50 then return false;
        Card:= Drawer(Card-1);
        Try:= Try+1;
        ];
    ];
return true;
];

func Stategy1;          \Return 'true' if stragegy succeeds
int  Prisoner, I, D(100);
[for Prisoner:= 1 to 100 do
   loop [for I:= 0 to 100-1 do D(I):= I+1;
        KShuffle;
        for I:= 1 to 50 do
            if Drawer(D(I-1)) = Prisoner then quit;
        return false;
        ];
return true;
];

proc Strategy(S);
int  S, I, Sample;
real Successes;
[Successes:= 0.;
for Sample:= 1 to 100_000 do
    [for I:= 0 to 100-1 do Drawer(I):= I+1;
    KShuffle;
    case S of
     1: if Stategy1 then Successes:= Successes + 1.;
     2: if Stategy2 then Successes:= Successes + 1.
    other [];
    ];
RlOut(0, Successes/100_000.*100.);  Text(0, "%^m^j");
];

[Format(3, 12);
Text(0, "Random strategy success rate:  ");
Strategy(1);
Text(0, "Optimal strategy success rate: ");
Strategy(2);
]
Output:
Random strategy success rate:    0.000000000000%
Optimal strategy success rate:  31.085000000000%

Yabasic[edit]

Translation of: Phix
// Rosetta Code problem: http://rosettacode.org/wiki/100_prisoners
// by Galileo, 05/2022

sub play(prisoners, iterations, optimal)
    local prisoner, pardoned, found, drawer, drawers(prisoners), i, j, k, p, x

    for i = 1 to prisoners : drawers(i) = i : next

    for i = 1 to iterations
        for k = 1 to prisoners : x = ran(prisoners) + 1 : p = drawers(x) : drawers(x) = drawers(k) : drawers(k) = p : next
        for prisoner = 1 to prisoners
            found = false
            if optimal then drawer = prisoner else drawer = ran(prisoners) + 1 end if
            for j = 1 to prisoners / 2
                drawer = drawers(drawer)
                if drawer = prisoner found = true : break
                if not optimal drawer = ran(prisoners) + 1
            next
            if not found break
        next
        pardoned = pardoned + found
    next

    return 100 * pardoned / iterations
end sub
 
iterations = 10000
print "Simulation count: ", iterations
for prisoners = 10 to 100 step 90
    random = play(prisoners, iterations, false)
    optimal = play(prisoners, iterations, true)
    print "Prisoners: ", prisoners, ", random: ", random, ", optimal: ", optimal
next
Output:
Simulation count: 10000
Prisoners: 10, random: 0.01, optimal: 35.83
Prisoners: 100, random: 0, optimal: 31.2
---Program done, press RETURN---

zkl[edit]

const SLOTS=100, PRISONERS=100, TRIES=50, N=10_000;
fcn oneHundredJDI{	// just do it strategy
   cupboard,picks := [0..SLOTS-1].walk().shuffle(), cupboard.copy();
   // if this prisoner can't find their number in TRIES, all fail
   foreach p in (PRISONERS){ if(picks.shuffle().find(p)>=TRIES) return(False); }
   True		// all found their number
}
fcn oneHundredO{	// Optimal strategy
   cupboard := [0..SLOTS-1].walk().shuffle();
   foreach p in (PRISONERS){
      d:=p;
      do(TRIES){ if((d=cupboard[d]) == p) continue(2) }  // found my number
      return(False);  // this prisoner failed to find their number, all fail
   }
   True		// all found their number
}
s:=N.pump(Ref(0).incN,oneHundredJDI).value.toFloat()/N*100;
println("Just do it strategy (%,d simulatations): %.2f%%".fmt(N,s));

s:=N.pump(Ref(0).incN,oneHundredO).value.toFloat()/N*100;
println("Optimal strategy    (%,d simulatations): %.2f%%".fmt(N,s));
Output:
Just do it strategy (10,000 simulatations): 0.00%
Optimal strategy    (10,000 simulatations): 31.16%

And a sanity check (from the Raku entry):

const SLOTS=100, PRISONERS=10, TRIES=50, N=100_000;
Output:
Just do it strategy (100,000 simulatations): 0.09%
Optimal strategy    (100,000 simulatations): 31.13%