# 100 prisoners

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

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

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

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

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

## C++

`#include <iostream>	//for output#include <algorithm>	//for shuffle#include <stdlib.h>	//for rand() using namespace std; int* setDrawers() {	int drawers;	for (int i = 0; i < 100; i++) {		drawers[i] = i;	}	random_shuffle(&drawers, &drawers);	return drawers;} bool playRandom(){	int* drawers = setDrawers();	bool openedDrawers = { 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;}`
Output:
```Random Strategy: 0%
Optimal Strategy: 31.51%
```

## EasyLang

`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 = 10000pardoned = 0for round range n  call play_random  pardoned += found.print "random: " & 100.0 * pardoned / n & "%"# pardoned = 0for round range n  call play_optimal  pardoned += found.print "optimal: " & 100.0 * pardoned / n & "%"`
Output:
```random: 0.000%
optimal: 30.800%
```

## 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" print10,000 [ rand ] simulate "Random play success: "10,000 [ optimal ] simulate "Optimal play success: "[ write "%.2f%%\n" printf ] [email protected]`
Output:
```Simulation count: 10,000
Random play success: 0.00%
Optimal play success: 31.11%
```

## 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 := 0trial:    for t := 0; t < trials; t++ {        var drawers 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 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 string{"random", "optimal"} {            doTrials(trials, np, strategy)        }    }}`
Output:
```Results from 100000 trials with 10 prisoners:

strategy = random   pardoned = 99     relative frequency =  0.10%

strategy = optimal  pardoned = 31205  relative frequency = 31.20%

Results from 100000 trials with 100 prisoners:

strategy = random   pardoned = 0      relative frequency =  0.00%

strategy = optimal  pardoned = 31154  relative frequency = 31.15%
```

## Julia

Translation of: Python
`using Random, Formatting function randomplay(n, numprisoners=100)    pardoned, indrawer, found = 0, collect(1:numprisoners), false    for i in 1:n        shuffle!(indrawer)        for prisoner in 1:numprisoners            found = false            for reveal in randperm(numprisoners)[1:div(numprisoners, 2)]                indrawer[reveal] == prisoner && (found = true) && break            end            !found && break        end        found && (pardoned += 1)    end    return 100.0 * pardoned / nend 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_000println("Simulation count: \$N")println("Random play wins: ", format(randomplay(N), precision=8), "% of simulations.")println("Optimal play wins: ", format(optimalplay(N), precision=8), "% of simulations.") `
Output:
```Simulation count: 100000
Random play wins: 0.00000000% of simulations.
Optimal play wins: 31.18100000% of simulations.
```

## Kotlin

`val playOptimal: () -> Boolean = {    val secrets = (0..99).toMutableList()    var ret = true    secrets.shuffle()    [email protected] for(i in 0 until 100){        var prev = i        [email protected] for(j in 0 until  50){            if (secrets[prev] == i) [email protected]            prev = secrets[prev]        }        ret = false        [email protected]    }    ret} val playRandom: ()->Boolean = {    var ret = true    val secrets = (0..99).toMutableList()    secrets.shuffle()    [email protected] 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) [email protected]            opened.add(draw)        }        ret = false        [email protected]    }    ret} fun exec(n:Int, play:()->Boolean):Double{    var succ = 0    for (i in IntRange(0, n-1)){        succ += if(play()) 1 else 0    }    return (succ*100.0)/n} fun main() {    val N = 100_000    println("# of executions: \$N")    println("Optimal play success rate: \${exec(N, playOptimal)}%")    println("Random play success rate: \${exec(N, playRandom)}%")} `

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

## 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`
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
`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 * 100end 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 * 100end function print "Random:  " + playRandom(10000) + "%"print "Optimal: " + playOptimal(10000) + "%"`
Output:
```Random:  0%
Optimal: 31.06%```

## Pascal

Works with: Free 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.`
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```

## Perl

Translation of: Perl 6
`use strict;use warnings;use feature 'say';use List::Util 'shuffle'; sub simulation {    my(\$population,\$trials,\$strategy) = @_;    my \$optimal   = \$strategy =~ /^o/i ? 1 : 0;    my @prisoners = 0..\$population-1;    my \$half      = int \$population / 2;    my \$pardoned  = 0;     for (1..\$trials) {        my @drawers = shuffle @prisoners;        my \$total = 0;        for my \$prisoner (@prisoners) {            my \$found = 0;            if (\$optimal) {                my \$card = \$drawers[\$prisoner];                if (\$card == \$prisoner) {                    \$found = 1;                } else {                    for (1..\$half-1) {                        \$card = \$drawers[\$card];                        (\$found = 1, last) if \$card == \$prisoner                    }                }            } else {                for my \$card ( (shuffle @drawers)[0..\$half]) {                    (\$found = 1, last) if \$card == \$prisoner                }            }            last unless \$found;            \$total++;        }        \$pardoned++ if \$total == \$population;    }    \$pardoned / \$trials * 100} my \$population = 100;my \$trials     = 10000;say " Simulation count: \$trials\n" .(sprintf " Random strategy pardons: %6.3f%% of simulations\n", simulation \$population, \$trials, 'random' ) .(sprintf "Optimal strategy pardons: %6.3f%% of simulations\n", simulation \$population, \$trials, 'optimal'); \$population = 10;\$trials     = 100000;say " Simulation count: \$trials\n" .(sprintf " Random strategy pardons: %6.3f%% of simulations\n", simulation \$population, \$trials, 'random' ) .(sprintf "Optimal strategy pardons: %6.3f%% of simulations\n", simulation \$population, \$trials, 'optimal');`
Output:
``` Simulation count: 10000
Random strategy pardons:  0.000% of simulations
Optimal strategy pardons: 31.510% of simulations

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

## Perl 6

Works with: Rakudo version 2019.07.1

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

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

`unit sub MAIN (:\$prisoners = 100, :\$simulations = 10000);my @prisoners = ^\$prisoners;my \$half = floor +@prisoners / 2; sub random (\$n) {    ^\$n .race.map( {        my @drawers = @prisoners.pick: *;        @prisoners.map( -> \$prisoner {            my \$found = 0;            for @drawers.pick(\$half) -> \$card {                \$found = 1 and last if \$card == \$prisoner            }            last unless \$found;            \$found        }        ).sum == @prisoners    }    ).grep( *.so ).elems / \$n * 100} sub optimal (\$n) {    ^\$n .race.map( {        my @drawers = @prisoners.pick: *;        @prisoners.map( -> \$prisoner {            my \$found = 0;            my \$card = @drawers[\$prisoner];            if \$card == \$prisoner {                \$found = 1            } else {                for ^(\$half - 1) {                    \$card = @drawers[\$card];                    \$found = 1 and last if \$card == \$prisoner                }            }            last unless \$found;            \$found        }        ).sum == @prisoners    }    ).grep( *.so ).elems / \$n * 100} say "Testing \$simulations simulations with \$prisoners prisoners.";printf " Random play wins: %.3f%% of simulations\n", random \$simulations;printf "Optimal play wins: %.3f%% of simulations\n", optimal \$simulations;`
Output:

With defaults

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

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

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

## Python

### Procedural

`import random def play_random(n):    # using 0-99 instead of ranges 1-100    pardoned = 0    in_drawer = list(range(100))    sampler = list(range(100))    for _round in range(n):        random.shuffle(in_drawer)        found = False        for prisoner in range(100):            found = False            for reveal in random.sample(sampler, 50):                card = in_drawer[reveal]                if card == prisoner:                    found = True                    break            if not found:                break        if found:            pardoned += 1    return pardoned / n * 100   # % def play_optimal(n):    # using 0-99 instead of ranges 1-100    pardoned = 0    in_drawer = list(range(100))    for _round in range(n):        random.shuffle(in_drawer)        for prisoner in range(100):            reveal = prisoner            found = False            for go in range(50):                card = in_drawer[reveal]                if card == prisoner:                    found = True                    break                reveal = card            if not found:                break        if found:            pardoned += 1    return pardoned / n * 100   # % if __name__ == '__main__':    n = 100_000    print(" Simulation count:", n)    print(f" Random play wins: {play_random(n):4.1f}% of simulations")    print(f"Optimal play wins: {play_optimal(n):4.1f}% of simulations")`
Output:
``` Simulation count: 100000
Random play wins:  0.0% of simulations
Optimal play wins: 31.1% of simulations```

Or, an alternative procedural approach:

`# http://rosettacode.org/wiki/100_prisoners import random  def main():    NUM_DRAWERS = 10    NUM_REPETITIONS = int(1E5)     print('{:15}: {:5} ({})'.format('approach', 'wins', 'ratio'))    for approach in PrisionersGame.approaches:        num_victories = 0        for _ in range(NUM_REPETITIONS):            game = PrisionersGame(NUM_DRAWERS)            num_victories += PrisionersGame.victory(game.play(approach))         print('{:15}: {:5} ({:.2%})'.format(            approach.__name__, num_victories, num_victories / NUM_REPETITIONS))  class PrisionersGame:    """docstring for PrisionersGame"""    def __init__(self, num_drawers):        assert num_drawers % 2 == 0        self.num_drawers = num_drawers        self.max_attempts = int(self.num_drawers / 2)        self.drawer_ids = list(range(1, num_drawers + 1))        shuffled = self.drawer_ids[:]        random.shuffle(shuffled)        self.drawers = dict(zip(self.drawer_ids, shuffled))     def play_naive(self, player_number):        """ Randomly open drawers """        for attempt in range(self.max_attempts):            if self.drawers[random.choice(self.drawer_ids)] == player_number:                return True         return False     def play_naive_mem(self, player_number):        """ Randomly open drawers but avoiding repetitions """        not_attemped = self.drawer_ids[:]        for attempt in range(self.max_attempts):            guess = random.choice(not_attemped)            not_attemped.remove(guess)             if self.drawers[guess] == player_number:                return True         return False     def play_optimum(self, player_number):        """ Open the drawer that matches the player number and then open the drawer        with the revealed number.        """        prev_attempt = player_number        for attempt in range(self.max_attempts):            if self.drawers[prev_attempt] == player_number:                return True            else:                prev_attempt = self.drawers[prev_attempt]         return False     @classmethod    def victory(csl, results):        """Defines a victory of a game: all players won"""        return all(results)     approaches = [play_naive, play_naive_mem, play_optimum]     def play(self, approach):        """Plays this game and returns a list of booleans with        True if a player one, False otherwise"""        return [approach(self, player) for player in self.drawer_ids]  if __name__ == '__main__':    main()`
Output:
```With 10 drawers (100k runs)
approach       : wins  (ratio)
play_naive     :    14 (0.01%)
play_naive_mem :    74 (0.07%)
play_optimum   : 35410 (35.41%)

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

### Functional

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

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

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

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

Works with: Python version 3.7
`'''100 Prisoners''' from random import randint, sample  # allChainedPathsAreShort :: Int -> IO (0|1)def allChainedPathsAreShort(n):    '''1 if none of the index-chasing cycles in a shuffled       sample of [1..n] cards are longer than half the       sample size. Otherwise, 0.    '''    limit = n // 2    xs = range(1, 1 + n)    shuffled = sample(xs, k=n)     # A cycle of boxes, drawn from a shuffled    # sample, which includes the given target.    def cycleIncluding(target):        boxChain = [target]        v = shuffled[target - 1]        while v != target:            boxChain.append(v)            v = shuffled[v - 1]        return boxChain     # Nothing if the target list is empty, or if the cycle which contains the    # first target is larger than half the sample size.    # Otherwise, just a cycle of enchained boxes containing the first target    # in the list, tupled with the residue of any remaining targets which    # fall outside that cycle.    def boxCycle(targets):        if targets:            boxChain = cycleIncluding(targets)            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] -> Stringdef 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) -> Stringdef fName(f):    '''Name bound to the given function.'''    return f.__name__  # ------------------------GENERIC ------------------------- # Just :: a -> Maybe adef 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 adef 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 () -> Intdef 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)            if mb.get('Nothing'):                return xs            else:                xr = mb.get('Just')                xs.append(xr)        return xs    return lambda x: go(x)  # MAIN ---if __name__ == '__main__':    main()`
Output:
```10000 tests of optimal vs random drawer-sampling with 10 boxes:

optimalDrawerSampling -> 35.47%
randomDrawerSampling -> 0.09%

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

optimalDrawerSampling -> 30.40%
randomDrawerSampling -> 0.00%

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

optimalDrawerSampling -> 31.17%
randomDrawerSampling -> 0.00%```

## 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)))`
Output:
```random: 0.00%
optimal: 31.18%```

## 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.*/`
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.
```

## Rust

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

Cargo.toml

`[dependencies]rand = '0.7.2'`

src/main.rs

`extern crate rand; use rand::prelude::*; // Do a full run of checking boxes in a random order for a single prisonerfn 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 prisonerfn check_ordered_boxes(prisoner: u8, boxes: &[u8]) -> bool {    let mut next_check = prisoner;    (0..50).any(|_| {        next_check = boxes[next_check as usize - 1];        next_check == prisoner    })} fn main() {    let mut boxes: Vec<u8> = (1u8..=100u8).collect();     let trials = 100000;     let ordered_successes = (0..trials).filter(|_| {        boxes.shuffle(&mut rand::thread_rng());        (1u8..=100u8).all(|prisoner| check_ordered_boxes(prisoner, &boxes))    }).count();     let random_successes = (0..trials).filter(|_| {        boxes.shuffle(&mut rand::thread_rng());        (1u8..=100u8).all(|prisoner| check_random_boxes(prisoner, &boxes))    }).count();     println!("{} / {} ({:.02}%) successes in ordered", ordered_successes, trials, ordered_successes as f64 * 100.0 / trials as f64);    println!("{} / {} ({:.02}%) successes in random", random_successes, trials, random_successes as f64 * 100.0 / trials as f64); }`
Output:
```31106 / 100000 (31.11%) successes in ordered
0 / 100000 (0.00%) successes in random```

## 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}`
`s:=N.pump(Ref(0).incN,oneHundredJDI).value.toFloat()/N*100;println("Just do it strategy (%,d simulatations): %.2f%%".fmt(N,s)); s:=N.pump(Ref(0).incN,oneHundredO).value.toFloat()/N*100;println("Optimal strategy    (%,d simulatations): %.2f%%".fmt(N,s));`
Output:
```Just do it strategy (10,000 simulatations): 0.00%
Optimal strategy    (10,000 simulatations): 31.16%
```

And a sanity check (from the Perl6 entry):

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