100 prisoners
You are encouraged to solve this task according to the task description, using any language you may know.
- The Problem
- 100 prisoners are individually numbered 1 to 100
- A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
- Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
- Prisoners start outside the room
- They can decide some strategy before any enter the room.
- Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
- A prisoner can open no more than 50 drawers.
- A prisoner tries to find his own number.
- A prisoner finding his own number is then held apart from the others.
- If all 100 prisoners find their own numbers then they will all be pardoned. If any don't then all sentences stand.
- The task
- Simulate several thousand instances of the game where the prisoners randomly open draws
- 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.
C
<lang C>
- include<stdbool.h>
- include<stdlib.h>
- include<stdio.h>
- include<time.h>
- define LIBERTY false
- define DEATH true
typedef struct{ int id; int cardNum; bool hasBeenOpened; }drawer;
typedef struct{ int id; bool foundCard; }prisoner;
drawer *drawerSet; prisoner *prisonerGang;
void initialize(int prisoners){ int i,j,card; bool unique;
drawerSet = (drawer*)malloc(prisoners * sizeof(drawer)); prisonerGang = (prisoner*)malloc(prisoners * sizeof(prisoner));
for(i=0;i<prisoners;i++){ prisonerGang[i] = (prisoner){.id = i+1, .foundCard = false};
card = rand()%prisoners + 1;
if(i==0) drawerSet[i] = (drawer){.id = i+1, .cardNum = card, .hasBeenOpened = false}; else{ 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){.id = i+1, .cardNum = card, .hasBeenOpened = false}; } } }
void closeAllDrawers(int prisoners){ int i; for(i=0;i<prisoners;i++) drawerSet[i].hasBeenOpened = false; }
bool libertyOrDeathAtRandom(int prisoners,int chances){ int i,j,chosenDrawer;
for(i=0;i<prisoners;i++){ for(j=0;j<chances;j++){ do{ chosenDrawer = rand()%prisoners; }while(drawerSet[chosenDrawer].hasBeenOpened==true); if(drawerSet[chosenDrawer].cardNum == prisonerGang[i].id){ prisonerGang[i].foundCard = true; break; } drawerSet[chosenDrawer].hasBeenOpened = true; } closeAllDrawers(prisoners); if(prisonerGang[i].foundCard == false) return DEATH; }
return LIBERTY; }
bool libertyOrDeathPlanned(int prisoners,int chances){ int i,j,chosenDrawer; for(i=0;i<prisoners;i++){ chosenDrawer = rand()%prisoners; for(j=1;j<chances;j++){ if(drawerSet[chosenDrawer].cardNum == prisonerGang[i].id){ prisonerGang[i].foundCard = true; break; } if(chosenDrawer+1 == drawerSet[chosenDrawer].id){ do{
chosenDrawer = rand()%prisoners;
}while(drawerSet[chosenDrawer].hasBeenOpened==true); } else{ chosenDrawer = drawerSet[chosenDrawer].cardNum - 1; } drawerSet[chosenDrawer].hasBeenOpened = true; } closeAllDrawers(prisoners); if(prisonerGang[i].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> C's random number generator, at least the one on my machine, doesn't give the prisoners any chance, even for a million trials.
C:\My Projects\networks>a 100 50 100000 Running random trials... Games Played : 100000 Games Won : 0 Chances : 0.000000% Running strategic trials... Games Played : 100000 Games Won : 0 Chances : 0.000000 C:\My Projects\networks>a 100 50 1000000 Running random trials... Games Played : 1000000 Games Won : 0 Chances : 0.000000 Running strategic trials... Games Played : 1000000 Games Won : 0 Chances : 0.000000
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%
D
<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>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%
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%
Java
<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%
Julia
<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%
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
<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%
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
alternatve 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
<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
Perl 6
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
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
<lang PowerShell>
- 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:
<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%
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
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 Perl6 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%