100 prisoners: Difference between revisions

Content added Content deleted

Inline

Revision as of 10:23, 28 July 2020

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

Simulate several thousand instances of the game where the prisoners randomly open drawers
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

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

Ada

<lang Ada> 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; </lang> <lang Ada> 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; </lang> <lang Ada> 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; </lang>

Output:

Optimal Strategy = 31.80%
Random Strategy =  0.00%

Applesoft BASIC

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.

<lang gwbasic>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 </lang>

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.

C

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; }

</lang>

$ 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#

Translation of: D

<lang csharp>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));
       }
   }

}</lang>

Output:

# of executions: 1000000
Optimal play success rate: 31.21310000000%
 Random play success rate: 0.00000000000%

C++

<lang cpp>#include <iostream> //for output

include <algorithm> //for shuffle
include <stdlib.h> //for rand()

using namespace std;

int* setDrawers() { int drawers[100]; for (int i = 0; i < 100; i++) { drawers[i] = i; } random_shuffle(&drawers[0], &drawers[99]); return drawers; }

bool playRandom() { int* drawers = setDrawers(); 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 < 50; i++) { //loops through 50 draws for each prisoner int drawerNum; while (true) { drawerNum = rand() % 100; if (!openedDrawers[drawerNum]) { openedDrawers[drawerNum] = true; cout << endl; break; } } if (*(drawers + drawerNum) == prisonerNum) { prisonerSuccess = true; break; } } if (!prisonerSuccess) return false; } return true; }

bool playOptimal() { int* drawers = setDrawers(); for (int prisonerNum = 0; prisonerNum < 100; prisonerNum++) { bool prisonerSuccess = false; int checkDrawerNum = prisonerNum; for (int i = 0; i < 50; i++) { if (*(drawers + checkDrawerNum) == prisonerNum) { prisonerSuccess = true; break; } else checkDrawerNum = *(drawers + checkDrawerNum); } if (!prisonerSuccess) return false; } return true; }

double simulate(string strategy) { int numberOfSuccesses = 0; for (int i = 0; i <= 10000; i++) { if ((strategy == "random" && playRandom()) || (strategy == "optimal" && playOptimal())) //will run playRandom or playOptimal but not both becuase of short-circuit evaluation numberOfSuccesses++; } return numberOfSuccesses / 100.0; }

int main() { cout << "Random Strategy: " << simulate("random") << "%" << endl; cout << "Optimal Strategy: " << simulate("optimal") << "%" << endl; system("PAUSE"); return 0; }</lang>

Output:

Random Strategy: 0%
Optimal Strategy: 31.51%

Clojure

<lang Clojure>(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))))))</lang>

Output:

Probability of survival with random search: 0.0
Probability of survival with ordered search: 0.3062

Commodore BASIC

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.):

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.
When the NEXT belonging to loop 'i' is encountered, any inner loops ('g') are terminated.
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.

<lang gwbasic> 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 </lang>

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

Translation of: Racket

<lang lisp> (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)))

</lang>

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.

Crystal

Based on the Ruby implementation

<lang crystal>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)</lang>

Output:

Random strategy :      0.0000 %
Optimal strategy:     31.3190 %

D

Translation of: Kotlin

<lang d>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));

}</lang>

Output:

# of executions: 1000000
Optimal play success rate: 31.16100000%
 Random play success rate:  0.00000000%

EasyLang

<lang EasyLang>intvars 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 & "%"</lang>

Output:

random: 0.000%
optimal: 30.800%

Factor

<lang factor>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@</lang>

Output:

Simulation count: 10,000
Random play success: 0.00%
Optimal play success: 31.11%

FreeBASIC

<lang freebasic>#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</lang>

Go

<lang go>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 = 100_000
   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)
       }
   }

}</lang>

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

Translation of: Java

<lang groovy>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))
   }

}</lang>

Output:

# of executions: 100000
Optimal play success rate: 31.215000%
Random play success rate: 0.000000%

Haskell

<lang haskell>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 </lang>

Output:

Chance of winning when choosing randomly: 0.0
Chance of winning when choosing optimally: 0.3188

J

<lang J> 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),'%' )</lang>

Output:

   simulate 10000000
┌────────┬────────┐
│strategy│win rate│
├────────┼────────┤
│random  │0%      │
├────────┼────────┤
│optimal │31.1816%│
└────────┴────────┘

Java

Translation of: Kotlin

<lang java>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));
   }

}</lang>

Output:

# of executions: 100000
Optimal play success rate: 31.343000%
Random play success rate: 0.000000%

JavaScript

Translation of: C#

Works with: Node.js

<lang javascript> 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()); </lang>

Julia

Translation of: Python

<lang julia>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.")

</lang>

Output:

Simulation count: 100000
Random play wins: 0.00000000% of simulations.
Optimal play wins: 31.18100000% of simulations.

Kotlin

<lang scala>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)}%")

}</lang>

Output:

# of executions: 100000
Optimal play success rate: 31.451%
Random play success rate: 0.0%

Lua

Translation of: lang

<lang lua>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()</lang>

Output:

# of executions: 1000000
Optimal play success rate: 31.237500
Random play success rate: 0.000000

MATLAB

<lang MATLAB>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</lang>

Output:

>> [randSuccess,idealSuccess]=prisoners(100,50,10000);
Probability of success with random strategy: 0%
Probability of success with ideal strategy: 31.93%

MiniScript

Translation of: Python

<lang MiniScript>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) + "%"</lang>

Output:

Random:  0%
Optimal: 31.06%

Nim

Imperative style. <lang Nim>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)</lang>

Output:

Succs: 312225   Fails: 687775   Total: 1000000  Success Rate: 31.2225%.
Succs: 0        Fails: 1000000  Total: 1000000  Success Rate: 0.0%.

Pascal

Works with: Free Pascal

searching the longest cycle length as stated on talk page and increment an counter for that cycle length. <lang pascal>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.</lang>

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

<lang pascal>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.</lang>

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

Translation of: Raku

<lang perl>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');</lang>

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

Phix

<lang Phix>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</lang>

Output:

Simulation count: 100000
Prisoners:10, random:0.006, optimal:35.168
Prisoners:100, random:0, optimal:31.098

PowerShell

Translation of: Chris

1. 1. 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 </lang>

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"

Python

Procedural

<lang python>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")</lang>

Output:

 Simulation count: 100000
 Random play wins:  0.0% of simulations
Optimal play wins: 31.1% of simulations

Or, an alternative procedural approach: <lang python># 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()</lang>

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

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

<lang python>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()</lang>

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%

Racket

<lang racket>#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)))</lang>

Output:

random: 0.00%
optimal: 31.18%

Raku

(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.

<lang perl6>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;</lang>

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

<lang Rebol> 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 ] </lang>

Output:

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

REXX

<lang rexx>/*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.*/</lang>

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

<lang ruby>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) </lang>

Output:

Random strategy :      0.0000 %
Optimal strategy:     30.7400 %

Rust

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

Cargo.toml <lang toml>[dependencies] rand = '0.7.2'</lang>

src/main.rs <lang rust>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);

}</lang>

Output:

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

Scala

Translation of: Java

<lang scala>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))
 }

}</lang>

Output:

# of executions: 100,000
Optimal play success rate: 31.201000%
Random play success rate: 0.000000%

Swift

<lang swift>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()</lang>

Output:

Running 100000 games for each strategy
Probability of pardon with optimum strategy: 0.31099
Probability of pardon with random strategy: 0.0

VBA

<lang VBA>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
               GoTo Finish
           End If
           NumberFromDrawer = DrawerArray(NumberFromDrawer - 1)
       Next j

Finish:

   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
               GoTo Finish
           End If
       Next j

Finish:

   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
               GoTo Finish2
           End If
       Next j

Finish2:

   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</lang>

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

Translation of: C#

<lang vbnet>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</lang>

Output:

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

Wren

Translation of: Go

Library: Wren-fmt

<lang ecmascript>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)

}</lang>

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%

zkl

<lang zkl>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

}</lang> <lang zkl>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));</lang>

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): <lang zkl>const SLOTS=100, PRISONERS=10, TRIES=50, N=100_000;</lang>

Output:

Just do it strategy (100,000 simulatations): 0.09%
Optimal strategy    (100,000 simulatations): 31.13%