100 prisoners: Difference between revisions
Add Ecstasy example
No edit summary |
(Add Ecstasy example) |
||
(31 intermediate revisions by 18 users not shown) | |||
Line 34:
{{trans|Python}}
<
V pardoned = 0
V in_drawer = Array(0.<100)
Line 78:
print(‘ Simulation count: ’n)
print(‘ Random play wins: #2.1% of simulations’.format(play_random(n)))
print(‘Optimal play wins: #2.1% of simulations’.format(play_optimal(n)))</
{{out}}
Line 89:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program prisonniex64.s */
Line 347:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
Random strategie : 0 sur 1000
Line 353:
</pre>
=={{header|ABC}}==
<syntaxhighlight lang="ABC">HOW TO FILL drawers:
PUT {} IN drawers
FOR i IN {1..100}: PUT i IN drawers[i]
FOR i IN {1..100}:
PUT choice {i..100} IN j
PUT drawers[i], drawers[j] IN drawers[j], drawers[i]
HOW TO REPORT prisoner random.strat drawers:
PUT {1..100} IN available
FOR turn IN {1..50}:
PUT choice available IN drawer
IF drawers[drawer] = prisoner: SUCCEED
REMOVE drawer FROM available
FAIL
HOW TO REPORT prisoner optimal.strat drawers:
PUT prisoner IN drawer
FOR turn IN {1..50}:
IF drawers[drawer] = prisoner: SUCCEED
PUT drawers[drawer] IN drawer
FAIL
HOW TO REPORT simulate strategy:
FILL drawers
FOR prisoner IN {1..100}:
SELECT:
strategy = "Random":
IF NOT prisoner random.strat drawers: FAIL
strategy = "Optimal":
IF NOT prisoner optimal.strat drawers: FAIL
SUCCEED
HOW TO RETURN n.sim chance.of.success strategy:
PUT 0 IN success
FOR n IN {1..n.sim}:
IF simulate strategy: PUT success+1 IN success
RETURN success * 100 / n.sim
FOR strategy IN {"Random"; "Optimal"}:
WRITE strategy, ": ", 10000 chance.of.success strategy, '%'/</syntaxhighlight>
{{out}}
<pre>Optimal: 32.01 %
Random: 0 %</pre>
=={{header|Ada}}==
<syntaxhighlight lang="ada">
package Prisoners is
Line 378 ⟶ 422:
end Prisoners;
</syntaxhighlight>
<syntaxhighlight lang="ada">
pragma Ada_2012;
with Ada.Numerics.Discrete_Random;
Line 508 ⟶ 552:
end Prisoners;
</syntaxhighlight>
<syntaxhighlight lang="ada">
with Prisoners; use Prisoners;
with Ada.Text_IO; use Ada.Text_IO;
Line 527 ⟶ 571:
Put ("%");
end Main;
</syntaxhighlight>
{{out}}
<pre>
Line 533 ⟶ 577:
Random Strategy = 0.00%
</pre>
=={{header|APL}}==
{{works with|GNU APL|1.8}}
<syntaxhighlight lang="ada">
∇ R ← random Nnc; N; n; c
(N n c) ← Nnc
Line 560 ⟶ 605:
∇
⎕TS
'>>>>>'
1000 timesSimPrisoners 100 50
'>>>>>'
⎕TS
</syntaxhighlight>
{{out}}
<pre>
2023 3 26 17 43 32 983
>>>>>
0 0.307
>>>>>
2023 3 26 17 53 48 531
</pre>
=={{header|Applesoft BASIC}}==
Line 588 ⟶ 646:
Actual test of 4000 trials for each method were run on the KEGSMAC emulator with MHz set to No Limit.
<
1 FOR X = 0 TO N:J(X) = X: NEXT: FOR I = 0 TO N:FOR X = 0 TO N:T = J(X):NP = INT ( RND (1) * H):J(X) = J(NP):J(NP) = T: NEXT :FOR G = 1 TO W:IF D(J(G)) = I THEN IP = IP + 1: NEXT I: RETURN
Line 616 ⟶ 674:
1110 GET K$
1120 Q = K$ <> "Y" AND K$ <> CHR$(ASC("Y") + 32) : NEXT Q
</syntaxhighlight>
{{out}}
Line 640 ⟶ 698:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program prisonniers.s */
Line 875 ⟶ 933:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
<pre>
Random strategie : 0 sur 1000
Optimal strategie : 303 sur 1000
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">unplanned: function [][
drawers: shuffle @1..100
every? 1..100 'x -> some? 1..50 => [x = sample drawers]
]
planned: function [][
drawers: shuffle @1..100
every? 1..100 'x [
next: x
some? 1..50 => [x = next: <= drawers\[next-1]]
]
]
test: function [f][
count: enumerate 10000 => [call f []]
print [f ~"|mul fdiv count 10000 100|%"]
]
test 'unplanned
test 'planned</syntaxhighlight>
{{out}}
<pre>unplanned 0.0%
planned 31.43%</pre>
=={{header|AutoHotkey}}==
<
randomFailTotal := 0, strategyFailTotal := 0
prisoners := [], drawers := [], Cards := []
Line 937 ⟶ 1,023:
MsgBox % "Number Of Trials = " NumOfTrials
. "`nOptimal Strategy:`t" (1 - strategyFailTotal/NumOfTrials) *100 " % success rate"
. "`nRandom Trials:`t" (1 - randomFailTotal/NumOfTrials) *100 " % success rate"</
Outputs:<pre>Number Of Trials = 20000
Optimal Strategy: 33.275000 % success rate
Random Trials : 0.000000 % success rate</pre>
=={{header|
==={{header|BASIC256}}===
{{works with|BASIC256|2.0.0.11}}
<syntaxhighlight lang="basic256">
O = 50
N = 2*O
Line 1,023 ⟶ 1,110:
print "Smart choices: "; total;" out of ";iterations
print "Observed ratio: "; total/iterations; ", expected ratio with N=2*O: greater than about 0.30685": REM for N=100, O=50 particularly, about 0.3118
</syntaxhighlight>
{{out}}
<pre>
Line 1,032 ⟶ 1,119:
Observed ratio: 0.3052, expected ratio with N=2*O: greater than about 0.30685
</pre>
==={{header|True BASIC}}===
{{trans|Yabasic}}
<syntaxhighlight lang="qbasic">FUNCTION trials(prisoners, iterations, optimal)
DIM drawers(100)
FOR i = 1 TO prisoners
LET drawers(i) = i
NEXT i
FOR i = 1 TO iterations
FOR k = 1 TO prisoners
LET x = RND+1
LET p = drawers(x)
LET drawers(x) = drawers(k)
LET drawers(k) = p
NEXT k
FOR prisoner = 1 TO prisoners
LET found = false
IF optimal<>0 THEN LET drawer = prisoner ELSE LET drawer = RND+1
FOR j = 1 TO prisoners/2
LET drawer = drawers(drawer)
IF drawer = prisoner THEN
LET found = true
EXIT FOR
END IF
IF (NOT optimal<>0) THEN LET drawer = RND+1
NEXT j
IF (NOT found<>0) THEN EXIT FOR
NEXT prisoner
LET pardoned = pardoned+found
NEXT i
LET trials = (100*pardoned/iterations)
END FUNCTION
LET false = 0
LET true = 1
LET iterations = 10000
PRINT "Simulation count: "; iterations
FOR prisoners = 10 TO 100 STEP 90
LET randon = trials(prisoners,iterations,false)
LET optimal = trials(prisoners,iterations,true)
PRINT "Prisoners: "; prisoners; ", random: "; randon; ", optimal: "; optimal
NEXT prisoners
END</syntaxhighlight>
=={{header|BCPL}}==
<
manifest $(
Line 1,105 ⟶ 1,235:
run(d, " Random", randoms, size, simul, tries)
run(d, "Optimal", optimal, size, simul, tries)
$)</
{{out}}
<pre>
Line 1,112 ⟶ 1,242:
=={{header|C}}==
<syntaxhighlight lang="c">
#include<stdbool.h>
#include<stdlib.h>
Line 1,252 ⟶ 1,382:
}
</syntaxhighlight>
<pre>
$ gcc 100prisoners.c && ./a.out 100 50 10000
Line 1,270 ⟶ 1,400:
=={{header|C sharp|C#}}==
{{trans|D}}
<
using System.Linq;
Line 1,337 ⟶ 1,467:
}
}
}</
{{out}}
<pre># of executions: 1000000
Line 1,344 ⟶ 1,474:
=={{header|C++}}==
<
#include <algorithm> // for random_shuffle
#include <iostream> // for output
Line 1,419 ⟶ 1,549:
system("PAUSE"); // for Windows
return 0;
}</
{{out}}
<pre>Random strategy: 0 %
Line 1,425 ⟶ 1,555:
=={{header|Clojure}}==
<
(defn random-drawers []
Line 1,489 ⟶ 1,619:
(let [{:keys [random-successes optimal-successes run-count]} (simulate-n-runs 5000)]
(println (str "Probability of survival with random search: " (float (/ random-successes run-count))))
(println (str "Probability of survival with ordered search: " (float (/ optimal-successes run-count))))))</
{{out}}
Line 1,498 ⟶ 1,628:
=={{header|CLU}}==
<
% to use the random number generator.
%
Line 1,598 ⟶ 1,728:
show(" Random", simulations, prisoners, tries, rand_strat)
show("Optimal", simulations, prisoners, tries, opt_strat)
end start_up</
{{out}}
<pre> Random: 0 out of 50000, 0.00%
Line 1,618 ⟶ 1,748:
The key here is avoiding the use of GOTO as a means of exiting a loop early.
<
10 rem 100 prisoners
20 rem set arrays
Line 1,678 ⟶ 1,808:
4030 r=int(rnd(1)*100)+1:t=dr(i):dr(i)=dr(r):dr(r)=t:next
4040 return
</syntaxhighlight>
{{out}}
Line 1,701 ⟶ 1,831:
{{trans|Racket}}
<
(defparameter *samples* 10000)
(defparameter *prisoners* 100)
Line 1,751 ⟶ 1,881:
(format t "Using a random strategy in ~4,2F % of the cases the prisoners are free.~%" (* (/ (sampling #'strategy-1) *samples*) 100))
(format t "Using an optimal strategy in ~4,2F % of the cases the prisoners are free.~%" (* (/ (sampling #'strategy-2) *samples*) 100)))
</syntaxhighlight>
{{out}}
Line 1,760 ⟶ 1,890:
=={{header|Cowgol}}==
<
include "argv.coh";
Line 1,911 ⟶ 2,041:
RunAndPrint("Stupid", Stupid);
RunAndPrint("Optimal", Optimal);</
{{out}}
<pre>Stupid strategy: 0 out of 2000 - 0%
Line 1,919 ⟶ 2,049:
Based on the Ruby implementation
<
N = 100_000
generate_rooms = ->{ (1..100).to_a.shuffle }
Line 1,940 ⟶ 2,070:
end
end
puts "Optimal strategy: %11.4f %%" % (res.fdiv(N) * 100)</
{{out}}
<pre>Random strategy : 0.0000 %
Line 1,947 ⟶ 2,077:
=={{header|D}}==
{{trans|Kotlin}}
<
import std.random;
import std.range;
Line 1,999 ⟶ 2,129:
writefln("Optimal play success rate: %11.8f%%", exec(N, &playOptimal));
writefln(" Random play success rate: %11.8f%%", exec(N, &playRandom));
}</
{{out}}
<pre># of executions: 1000000
Optimal play success rate: 31.16100000%
Random play success rate: 0.00000000%</pre>
=={{header|Dart}}==
{{trans|Python}}
<syntaxhighlight lang="Dart">
import 'dart:math';
int playRandom(int n) {
var rnd = Random();
int pardoned = 0;
List<int> inDrawer = List<int>.generate(100, (i) => i);
List<int> sampler = List<int>.generate(100, (i) => i);
for (int round = 0; round < n; round++) {
inDrawer.shuffle();
bool found = false;
for (int prisoner = 0; prisoner < 100; prisoner++) {
found = false;
sampler.shuffle(rnd);
for (int i = 0; i < 50; i++) {
int reveal = sampler[i];
int card = inDrawer[reveal];
if (card == prisoner) {
found = true;
break;
}
}
if (!found) {
break;
}
}
if (found) {
pardoned++;
}
}
return (pardoned / n * 100).round();
}
int playOptimal(int n) {
var rnd = Random();
int pardoned = 0;
bool found = false;
List<int> inDrawer = List<int>.generate(100, (i) => i);
for (int round = 0; round < n; round++) {
inDrawer.shuffle(rnd);
for (int prisoner = 0; prisoner < 100; prisoner++) {
int reveal = prisoner;
found = false;
for (int go = 0; go < 50; go++) {
int card = inDrawer[reveal];
if (card == prisoner) {
found = true;
break;
}
reveal = card;
}
if (!found) {
break;
}
}
if (found) {
pardoned++;
}
}
return (pardoned / n * 100).round();
}
void main() {
int n = 100000;
print(" Simulation count: $n");
print(" Random play wins: ${playRandom(n).toStringAsFixed(2)}% of simulations");
print("Optimal play wins: ${playOptimal(n).toStringAsFixed(2)}% of simulations");
}
</syntaxhighlight>
{{out}}
<pre>
Simulation count: 100000
Random play wins: 0.00% of simulations
Optimal play wins: 31.00% of simulations
</pre>
=={{header|Delphi}}==
See [[#Pascal]].
=={{header|EasyLang}}==
<syntaxhighlight>
for i = 1 to 100
sampler[] &= i
.
subr shuffle_drawer
for i = len drawer[] downto 2
r =
swap drawer[r] drawer[i
.
.
subr play_random
swap sampler[r] sampler[100 - i - 1]
.
.
.
subr play_optimal
.
.
.
.
n = 10000
for
.
print "random: " & 100.0 *
#
for
.
print "optimal: " & 100.0 *
</syntaxhighlight>
{{out}}
<pre>
random: 0.000%
optimal: 30.800%
</pre>
=={{header|Ecstasy}}==
<syntaxhighlight lang="ecstasy">
module OneHundredPrisoners {
@Inject Console console;
void run() {
console.print($"# of executions: {attempts}");
console.print($"Optimal play success rate: {simulate(tryOpt)}%");
console.print($" Random play success rate: {simulate(tryRnd)}%");
}
Int attempts = 10000;
Dec simulate(function Boolean(Int[]) allFoundNumber) {
Int[] drawers = new Int[100](i->i);
Int pardoned = 0;
for (Int i : 1..attempts) {
if (allFoundNumber(drawers.shuffled())) {
++pardoned;
}
}
return (pardoned * 1000000 / attempts).toDec() / 10000;
}
Boolean tryRnd(Int[] drawers) {
Inmates: for (Int inmate : 0..<100) {
Int[] choices = drawers.shuffled();
for (Int attempt : 0..<50) {
if (drawers[choices[attempt]] == inmate) {
continue Inmates;
}
}
return False;
}
return True;
}
Boolean tryOpt(Int[] drawers) {
Inmates: for (Int inmate : 0..<100) {
Int choice = inmate;
for (Int attempt : 0..<50) {
if (drawers[choice] == inmate) {
continue Inmates;
}
choice = drawers[choice];
}
return False;
}
return True;
}
}
</syntaxhighlight>
{{out}}
<pre>
# of executions: 10000
Optimal play success rate: 30.1%
Random play success rate: 0%
</pre>
=={{header|Elixir}}==
{{trans|Ruby}}
<
def optimal_room(_, _, _, []), do: []
def optimal_room(prisoner, current_room, rooms, [_ | tail]) do
Line 2,109 ⟶ 2,381:
end)
IO.puts "Optimal strategy: #{optimal_strategy} / #{n |> Range.size}"</
{{out}}
<pre>
Line 2,117 ⟶ 2,389:
=={{header|F sharp|F#}}==
<
let shuffled min max =
[|min..max|] |> Array.sortBy (fun _ -> rnd.Next(min,max+1))
Line 2,154 ⟶ 2,426:
printfn $"Using Random Strategy: {(outcomeOfRandom 20000):p2}"
printfn $"Using Optimum Strategy: {(outcomeOfOptimize 20000):p2}"
</syntaxhighlight>
{{out}}
<pre>Using Random Strategy: 0.00%
Line 2,161 ⟶ 2,433:
=={{header|Factor}}==
<
: setup ( -- seq seq ) 100 <iota> dup >array randomize ;
Line 2,180 ⟶ 2,452:
10,000 [ rand ] simulate "Random play success: "
10,000 [ optimal ] simulate "Optimal play success: "
[ write "%.2f%%\n" printf ] 2bi@</
{{out}}
<pre>
Line 2,190 ⟶ 2,462:
=={{header|FOCAL}}==
<
01.20 F Z=1,2000;D 5;S CU=CU+SU
01.30 T CU/20,!,"OPTIMAL";S CU=0
Line 2,227 ⟶ 2,499:
06.20 I (X-101)6.3,6.4
06.30 D 4;S X=X+1;I (SU),6.4,6.2
06.40 R</
{{out}}
Line 2,246 ⟶ 2,518:
Run the two strategies (random and follow the card number) 10,000 times each, and show number or successes.
<
100 CONSTANT #drawers
Line 2,333 ⟶ 2,605:
0 trie . CR \ random strategy
1 trie . CR \ follow the card number strategy</
output:
Line 2,343 ⟶ 2,615:
=={{header|Fortran}}==
<
! Takes an input array and shuffles the elements by swapping them
! in pairs in turn 10 times
Line 2,496 ⟶ 2,768:
CALL RUN_RANDOM(N_ROUNDS)
CALL RUN_OPTIMAL(N_ROUNDS)
END PROGRAM HUNDRED_PRISONERS</
output:
Line 2,507 ⟶ 2,779:
=={{header|FreeBASIC}}==
<
function gus( i as long, strat as boolean ) as long
Line 2,548 ⟶ 2,820:
trials( c_success, c_fail, true )
print using "For prisoners using the strategy we had ####### successes and ####### failures.";c_success;c_fail</
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
include "Tlbx GameplayKit.incl"
_prisoners = 100
_instances = 10000
local fn DrawersArray as CFArrayRef
long index
CFMutableArrayRef temp = fn MutableArrayWithCapacity(100)
for index = 0 to 99
MutableArrayAddObject( temp, @(index) )
next
end fn = fn ArrayShuffledArray( temp )
local fn RandomResult( drawers as CFArrayRef ) as BOOL
long prisoner, i, drawer, total = 0
MutableIndexSetRef set
for prisoner = 0 to _prisoners - 1
set = fn MutableIndexSetInit
for i = 1 to _prisoners/2
drawer = rnd(_prisoners)-1
while ( fn IndexSetContainsIndex( set, intVal( drawers[drawer] ) ) )
drawer = rnd(_prisoners)-1
wend
MutableIndexSetAddIndex( set, intVal( drawers[drawer] ) )
if ( fn IndexSetContainsIndex( set, prisoner ) )
total++
break
end if
next
next
end fn = ( total == _prisoners )
local fn OptimalResult( drawers as CFArrayRef ) as BOOL
long prisoner, drawer, i, card, total = 0
for prisoner = 0 to _prisoners - 1
drawer = prisoner
for i = 1 to _prisoners/2
card = intVal( drawers[drawer] )
if ( card == prisoner )
total++
break
end if
drawer = card
next
next
end fn = ( total == _prisoners )
void local fn DoIt
static double sTime = 0.0
block TimerRef timer = timerbegin , 0.001, YES
sTime += 0.001
cls
printf @"Compute time: %.3f\n",sTime
timerend
dispatchglobal
long instance, randomTotal = 0, optimalTotal = 0
CFArrayRef drawers
for instance = 1 to _instances
drawers = fn DrawersArray
if ( fn RandomResult( drawers ) ) then randomTotal++
if ( fn OptimalResult( drawers ) ) then optimalTotal++
next
dispatchmain
TimerInvalidate( timer )
cls
print @"Prisoners: "_prisoners
print @"Instances: "_instances
printf @"Random - fail: %ld, success: %ld (%.2f%%)",_instances-randomTotal,randomTotal,(double)randomTotal/(double)_instances*100.0
printf @"Optimal - fail: %ld, success: %ld (%.2f%%)\n",_instances-optimalTotal,optimalTotal,(double)optimalTotal/(double)_instances*100.0
printf @"Compute time: %.3f\n",sTime
dispatchend
dispatchend
end fn
random
window 1, @"100 Prisoners"
fn DoIt
HandleEvents
</syntaxhighlight>
{{out}}
<pre>
Prisoners: 100
Instances: 10000
Random - fail: 10000, success: 0 (0.00%)
Optimal - fail: 6896, success: 3104 (31.04%)
Compute time: 7.856
</pre>
=={{header|Gambas}}==
Implementation of the '100 Prisoners' program written in VBA. Tested in Gambas 3.15.2
<
Public DrawerArray As Long[]
Line 2,712 ⟶ 3,092:
Return FoundOwnNumber
End</
{{out}}
Line 2,732 ⟶ 3,112:
Trials/sec: 114.9</pre>
=={{header|GDScript}}==
{{works with|Godot|4.0}}
<syntaxhighlight lang="gdscript">
extends MainLoop
enum Strategy {Random, Optimal}
const prisoner_count := 100
func get_random_drawers() -> Array[int]:
var drawers: Array[int] = []
drawers.resize(prisoner_count)
for i in range(0, prisoner_count):
drawers[i] = i + 1
drawers.shuffle()
return drawers
var random_strategy = func(drawers: Array[int], prisoner: int) -> bool:
# Randomly selecting 50 drawers is equivalent to shuffling and picking the first 50
var drawerCopy: Array[int] = drawers.duplicate()
drawerCopy.shuffle()
for i in range(50):
if drawers[drawerCopy[i]-1] == prisoner:
return true
return false
var optimal_strategy = func(drawers: Array[int], prisoner: int) -> bool:
var choice: int = prisoner
for _i in range(50):
var drawer_value: int = drawers[choice-1]
if drawer_value == prisoner:
return true
choice = drawer_value
return false
func play_all(drawers: Array[int], strategy: Callable) -> bool:
for prisoner in range(1, prisoner_count+1):
if not strategy.call(drawers, prisoner):
return false
return true
func _process(_delta: float) -> bool:
# Constant seed for reproducibility, call randomize() in real use
seed(1234)
const SAMPLE_SIZE: int = 10_000
var random_successes: int = 0
for i in range(SAMPLE_SIZE):
if play_all(get_random_drawers(), random_strategy):
random_successes += 1
var optimal_successes: int = 0
for i in range(SAMPLE_SIZE):
if play_all(get_random_drawers(), optimal_strategy):
optimal_successes += 1
print("Random play: %%%f" % (100.0 * random_successes/SAMPLE_SIZE))
print("Optimal play: %%%f" % (100.0 * optimal_successes/SAMPLE_SIZE))
return true # Exit
</syntaxhighlight>
{{out}}
<pre>
Random play: %0.000000
Optimal play: %31.700000
</pre>
=={{header|Go}}==
<
import (
Line 2,800 ⟶ 3,257:
}
}
}</
{{out}}
Line 2,819 ⟶ 3,276:
=={{header|Groovy}}==
{{trans|Java}}
<
import java.util.stream.Collectors
import java.util.stream.IntStream
Line 2,879 ⟶ 3,336:
System.out.printf("Random play success rate: %f%%\n", exec(n, p, Prisoners.&playRandom))
}
}</
{{out}}
<pre># of executions: 100000
Line 2,886 ⟶ 3,343:
=={{header|Haskell}}==
<
import Control.Monad.State
Line 2,961 ⟶ 3,418:
allM func [] = return True
allM func (x:xs) = func x >>= \res -> if res then allM func xs else return False
</syntaxhighlight>
{{out}}
<pre>Chance of winning when choosing randomly: 0.0
Line 2,967 ⟶ 3,424:
=={{header|J}}==
<syntaxhighlight lang="j">
NB. game is solvable by optimal strategy when the length (#) of the
NB. longest (>./) cycle (C.) is at most 50.
Line 2,983 ⟶ 3,440:
'o r'=. y %~ 100 * +/ ((rand,opt)@?~)"0 y # 100
('strategy';'win rate'),('random';(":o),'%'),:'optimal';(":r),'%'
)</
{{out}}
<pre> simulate 10000000
Line 2,996 ⟶ 3,453:
=={{header|Janet}}==
<
(math/seedrandom (os/cryptorand 8))
Line 3,051 ⟶ 3,508:
(printf "Optimal play wins: %.1f%%" (* (/ optimal-success sims) 100))
(printf "Random play wins: %.1f%%" (* (/ random-success sims) 100)))
</syntaxhighlight>
Output:
Line 3,062 ⟶ 3,519:
=={{header|Java}}==
{{trans|Kotlin}}
<
import java.util.List;
import java.util.Objects;
Line 3,126 ⟶ 3,583:
System.out.printf("Random play success rate: %f%%\n", exec(n, p, Main::playRandom));
}
}</
{{out}}
<pre># of executions: 100000
Line 3,135 ⟶ 3,592:
{{trans|C#}}
{{Works with|Node.js}}
<
const _ = require('lodash');
Line 3,244 ⟶ 3,701:
console.log("Optimal Play Success Rate: " + execOptimal());
console.log("Random Play Success Rate: " + execRandom());
</syntaxhighlight>
===School example===
Line 3,250 ⟶ 3,707:
{{works with|JavaScript|Node.js 16.13.0 (LTS)}}
<
// Simulate several thousand instances of the game:
Line 3,354 ⟶ 3,811:
function computeProbability(results, gamesCount) {
return Math.round(results.filter(x => x == true).length * 10000 / gamesCount) / 100;
}</
Output:
Line 3,366 ⟶ 3,823:
jq does not have a built-in PRNG and so the jq program used here presupposes an external source of entropy such as /dev/urandom. The output shown below was obtained by invoking jq as follows:
<
< /dev/urandom tr -cd '0-9' | fold -w 1 | jq -MRcnr -f 100-prisoners.jq</
In the following jq program:
Line 3,374 ⟶ 3,831:
'''Preliminaries'''
<
# Output: a PRN in range(0;$n) where $n is .
Line 3,396 ⟶ 3,853:
| .a[$j] = $t)
| .a
end;</
'''np Prisoners'''
<
def optimalStrategy($drawers; np):
# Does prisoner $p succeed?
Line 3,453 ⟶ 3,910:
;
task(100000)</
{{out}}
<pre>
Line 3,467 ⟶ 3,924:
=={{header|Julia}}==
{{trans|Python}}
<
function randomplay(n, numprisoners=100)
Line 3,508 ⟶ 3,965:
println("Random play wins: ", format(randomplay(N), precision=8), "% of simulations.")
println("Optimal play wins: ", format(optimalplay(N), precision=8), "% of simulations.")
</
<pre>
Simulation count: 100000
Random play wins: 0.00000000% of simulations.
Optimal play wins: 31.18100000% of simulations.
</pre>
=={{header|Koka}}==
Imperative equivalent (using mutable vectors, but also with exceptional control flow)
<syntaxhighlight lang="koka">
import std/num/random
value struct drawer
num: int
open: bool = False
inline extern unsafe-assign : forall<a> ( v : vector<a>, i : ssize_t, x : a ) -> total ()
c "kk_vector_unsafe_assign"
fun createDrawers()
val drawers = vector(100, Drawer(0,open=True))
for(0, 99) fn(i)
var found := False
while {!found}
val r = random-int() % 100
if drawers[r].open then
drawers.unsafe-assign(r.ssize_t, Drawer(i))
found := True
else
()
drawers
fun closeAll(d:vector<drawer>)
for(0,99) fn(i)
d.unsafe-assign(i.ssize_t, d[i](open=False))
effect fail
final ctl failed(): a
fun open-random(drawers: vector<drawer>)
val r = random-int() % 100
val opened = drawers[r]
if opened.open then
open-random(drawers)
else
drawers.unsafe-assign(r.ssize_t, opened(open=True))
opened.num
fun random-approach(drawers: vector<drawer>)
for(0, 99) fn(i)
var found := False
for(0, 49) fn(j)
val opened = open-random(drawers)
if opened == i then
found := True
else
()
if !found then
failed()
else
drawers.closeAll()
fun optimal-approach(drawers: vector<drawer>)
for(0, 99) fn(i)
var found := False
var drawer := i;
for(0, 49) fn(j)
val opened = drawers[drawer]
if opened.open then
failed()
if opened.num == i then
found := True
else
drawers.unsafe-assign(drawer.ssize_t, opened(open=True))
drawer := opened.num
if !found then
failed()
else
drawers.closeAll()
()
fun run-trials(f, num-trials)
var num_success := 0
for(0,num-trials - 1) fn(i)
val drawers = createDrawers()
with handler
return(x) ->
num_success := num_success + 1
final ctl failed() ->
()
f(drawers)
num_success
fun main()
val num_trials = 1000
val num_success_random = run-trials(random-approach, num_trials)
val num_success_optimal = run-trials(optimal-approach, num_trials)
println("Number of trials: " ++ num_trials.show)
println("Random approach: wins " ++ num_success_random.show ++ " (" ++ (num_success_random.float64 * 100.0 / num_trials.float64).show(2) ++ "%)")
println("Optimal approach: wins " ++ num_success_optimal.show ++ " (" ++ (num_success_optimal.float64 * 100.0 / num_trials.float64).show(2) ++ "%)")
</syntaxhighlight>
{{out}}
<pre>
Number of trials: 1000
Random approach: wins 0 (0.00%)
Optimal approach: wins 319 (31.90%)
</pre>
=={{header|Kotlin}}==
<
val secrets = (0..99).toMutableList()
var ret = true
Line 3,569 ⟶ 4,129:
println("Optimal play success rate: ${exec(N, playOptimal)}%")
println("Random play success rate: ${exec(N, playRandom)}%")
}</
{{out}}
Line 3,580 ⟶ 4,140:
=={{header|Lua}}==
{{trans|lang}}
<
for i = #tbl, 2, -1 do
local j = math.random(i)
Line 3,662 ⟶ 4,222:
end
main()</
{{out}}
<pre># of executions: 1000000
Line 3,671 ⟶ 4,231:
Don"t bother to simulate the random method: each prisoner has a probability p to win with:
<
# p=1/2</
Since all prisoners' attempts are independent, the probability that they all win is:
<
evalf(%);
# 1/1267650600228229401496703205376
# 7.888609052e-31</
Even with billions of simulations, chances are we won't find even one successful escape.
Line 3,688 ⟶ 4,248:
Here is a simulation based on this, assuming that the permutation of numbers in boxes is random:
<
nops(select(n->n<=50,a))/nops(a);
evalf(%);
# 31239/100000
# 0.3123900000</
The probability of success is now better than 30%, which is far better than the random approach.
Line 3,698 ⟶ 4,258:
It can be [https://en.wikipedia.org/wiki/Random_permutation_statistics#One_hundred_prisoners proved] that the probability with the second strategy is in fact:
<
evalf(%);
# 21740752665556690246055199895649405434183/69720375229712477164533808935312303556800
# 0.3118278207</
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
PlayRandom[n_] :=
Module[{pardoned = 0, sampler, indrawer, found, reveal},
Line 3,755 ⟶ 4,315:
];
PlayRandom[1000]
PlayOptimal[10000]</
{{out}}
Line 3,762 ⟶ 4,322:
=={{header|MATLAB}}==
<
%numP is the number of prisoners
%numG is the number of guesses
Line 3,819 ⟶ 4,379:
disp(['Probability of success with random strategy: ' num2str(randSuccess*100) '%']);
disp(['Probability of success with ideal strategy: ' num2str(idealSuccess*100) '%']);
end</
{{out}}
<pre>
Line 3,828 ⟶ 4,388:
=={{header|MiniScript}}==
{{trans|Python}}
<
// using 0-99 instead of 1-100
pardoned = 0
Line 3,876 ⟶ 4,436:
print "Random: " + playRandom(10000) + "%"
print "Optimal: " + playOptimal(10000) + "%"</
{{out}}
<pre>Random: 0%
Line 3,883 ⟶ 4,443:
=={{header|Nim}}==
Imperative style.
<
type
Line 3,931 ⟶ 4,491:
randomize()
echo $massDrawings(prisonersWillBeReleasedSmart)
echo $massDrawings(prisonersWillBeReleasedRandom)</
{{out}}
<pre>Succs: 312225 Fails: 687775 Total: 1000000 Success Rate: 31.2225%.
Line 3,939 ⟶ 4,499:
{{works with|Free Pascal}}
searching the longest cycle length as stated on talk page and increment an counter for that cycle length.
<
const
Line 4,097 ⟶ 4,657:
OneCompareRun(20);
OneCompareRun(100);
end.</
<pre>
Checking 20 prisoners
Line 4,150 ⟶ 4,710:
Randomly 0.00% get pardoned out of 100000 checking max 0</pre>
=== Alternative for optimized ===
<
{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
Line 4,287 ⟶ 4,847:
OneCompareRun(100);
OneCompareRun(1000);
end.</
{{out}}
<pre "style height=35ex">
Line 4,332 ⟶ 4,892:
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use feature 'say';
Line 4,382 ⟶ 4,942:
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');</
{{out}}
<pre> Simulation count: 10000
Line 4,395 ⟶ 4,955:
Built so you could easily build and test your own strategies.
<
(by '(NIL (rand)) sort Lst) )
Line 4,438 ⟶ 4,998:
(inc 'Successes) ) )
(prinl "We have a " (/ (* 100 Successes) N) "% success rate with " N " trials.")
(prinl "This is using the " (str> Strategy) " strategy.") ) )</
Then run
<
(test-strategy-n-times '+Optimal 10000)</
{{out}}
Line 4,451 ⟶ 5,011:
=={{header|Phix}}==
<!--
<syntaxhighlight 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 in {10,100} 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
</syntaxhighlight>
{{out}}
<pre>
Line 4,487 ⟶ 5,048:
Prisoners:100, random:0, optimal:31.098
</pre>
=={{header|Phixmonti}}==
{{trans|Yabasic}}
<syntaxhighlight lang="phixmonti">/# Rosetta Code problem: http://rosettacode.org/wiki/100_prisoners
by Galileo, 05/2022 #/
include ..\Utilitys.pmt
def random rand * 1 + int enddef
def shuffle
len var l
l for var a
l random var b
b get var p
a get b set
p a set
endfor
enddef
def play var optimal var iterations var prisoners
0 var pardoned
( prisoners for endfor )
iterations for drop
shuffle
prisoners for var prisoner
false var found
optimal if prisoner else prisoners random endif
prisoners 2 / int for drop
get dup prisoner == if true var found exitfor
else
optimal not if drop prisoners random endif
endif
endfor
found not if exitfor endif
drop
endfor
pardoned found + var pardoned
endfor
drop
pardoned 100 * iterations /
enddef
"Please, be patient ..." ?
( "Optimal: " 100 10000 true play
" Random: " 100 10000 false play
" Prisoners: " prisoners ) lprint</syntaxhighlight>
{{out}}
<pre>Please, be patient ...
Optimal: 31.65 Random: 0 Prisoners: 100
=== Press any key to exit ===</pre>
=={{header|PL/M}}==
<
/* PARAMETERS */
DECLARE N$DRAWERS LITERALLY '100'; /* AMOUNT OF DRAWERS */
Line 4,643 ⟶ 5,258:
CALL RUN$AND$PRINT(.'OPTIMAL$', OPTIMAL, N$SIMS);
CALL EXIT;
EOF</
{{out}}
<pre>RANDOM STRATEGY: 0 OUT OF 2000 - 0%
Line 4,649 ⟶ 5,264:
=={{header|Pointless}}==
<
iterate(ind => drawers[ind - 1], n)
|> takeUntil(ind => drawers[ind - 1] == n)
Line 4,693 ⟶ 5,308:
randomCount, numTrials, randomCount / numTrials,
])
|> println</
{{out}}
Line 4,701 ⟶ 5,316:
=={{header|PowerShell}}==
{{trans|Chris}}
<syntaxhighlight lang="powershell">
### Clear Screen from old Output
Clear-Host
Line 4,823 ⟶ 5,438:
Main
</syntaxhighlight>
{{out}}
Line 4,832 ⟶ 5,447:
=={{header|Processing}}==
<
int trials = 100000;
int succes_count;
Line 4,887 ⟶ 5,502:
println(" Succeses: " + succes_count);
print(" Succes rate: " + 100.0 * succes_count / trials + "%");
}</
{{out}}
Line 4,901 ⟶ 5,516:
=={{header|PureBasic}}==
<
#DRAWERS =100
#LOOPS = 50
Line 4,937 ⟶ 5,552:
PrintN(~"\tFIN =q.") : inp$=Input()
w1=0 : w2=0
If inp$<>"q" : Goto Start : EndIf</
{{out}}
<pre>TRIALS: 10000 RANDOM= 0.00% STATEGY= 30.83% FIN =q.
Line 4,947 ⟶ 5,562:
=={{header|Python}}==
===Procedural===
<
def play_random(n):
Line 4,995 ⟶ 5,610:
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")</
{{out}}
Line 5,004 ⟶ 5,619:
Or, an alternative procedural approach:
<
import random
Line 5,082 ⟶ 5,697:
if __name__ == '__main__':
main()</
{{Out}}
<pre>With 10 drawers (100k runs)
Line 5,106 ⟶ 5,721:
{{Works with|Python|3.7}}
<
from random import randint, sample
Line 5,282 ⟶ 5,897:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>10000 tests of optimal vs random drawer-sampling with 10 boxes:
Line 5,300 ⟶ 5,915:
=={{header|R}}==
<
success.r = rep(0,t) #this will keep track of how many prisoners find their ticket on each trial for the random method
success.o = rep(0,t) #this will keep track of how many prisoners find their ticket on each trial for the optimal method
Line 5,331 ⟶ 5,946:
cat("Random method resulted in a success rate of ",100*mean(success.r==100),
"%.\nOptimal method resulted in a success rate of ",100*mean(success.o==100),"%.",sep="")</
{{Out}}
<pre>Random method resulted in a success rate of 0%.
Line 5,337 ⟶ 5,952:
=={{header|QB64}}==
<syntaxhighlight lang="qb64">
Const Found = -1, Searching = 0, Status = 1, Tries = 2
Const Attempt = 1, Victories = 2, RandomW = 1, ChainW = 2
Line 5,418 ⟶ 6,033:
End Sub
</syntaxhighlight>
=={{header|Quackery}}==
<
[ dup size 2 / split ] is halve ( [ --> [ [ )
Line 5,466 ⟶ 6,081:
say "100 smart prisoners were pardoned "
0 10000 times [ 100 prisoners smart + ] echo
say " times out of 10000 simulations." cr ] is simulate ( --> )</
'''Output:'''
<
... simulate
...
Line 5,475 ⟶ 6,090:
100 smart prisoners were pardoned 3158 times out of 10000 simulations.
Stack empty.</
=={{header|Racket}}==
<
(require srfi/1)
Line 5,508 ⟶ 6,123:
(module+ main
(print-sample-percentage "random" (evaluate-strategy 100-prisoners-problem strategy-1))
(print-sample-percentage "optimal" (evaluate-strategy 100-prisoners-problem strategy-2)))</
{{out}}
Line 5,522 ⟶ 6,137:
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.
<syntaxhighlight lang="raku"
my @prisoners = ^$prisoners;
my $half = floor +@prisoners / 2;
Line 5,566 ⟶ 6,181:
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;</
{{out}}
'''With defaults'''
Line 5,579 ⟶ 6,194:
</pre>
=={{header|Red}}==
<syntaxhighlight lang="rebol">
Red []
Line 5,622 ⟶ 6,237:
print ["runs" k_runs newline "Percent saved opt.strategy:" saved * 100.0 / k_runs ]
print ["Percent saved random strategy:" saved_rand * 100.0 / k_runs ]
</syntaxhighlight>
{{out}}<pre>
runs 100000
Line 5,630 ⟶ 6,245:
=={{header|REXX}}==
<
parse arg men trials seed . /*obtain optional arguments from the CL*/
if men=='' | men=="," then men= 100 /*number of prisoners for this run.*/
Line 5,673 ⟶ 6,288:
end /* [↑] indicate success for prisoner. */
?= @.? /*choose next drawer from current card.*/
end /*try*/; return 1 /*choose half of the number of drawers.*/</
{{out|output|text= when using the default inputs:}}
<pre>
Line 5,690 ⟶ 6,305:
=={{header|Ruby}}==
<
N = 10_000
generate_rooms = ->{ [nil]+[*1..100].shuffle }
Line 5,712 ⟶ 6,327:
end
puts "Optimal strategy: %11.4f %%" % (res.fdiv(N) * 100)
</syntaxhighlight>
{{out}}
<pre>Random strategy : 0.0000 %
Line 5,723 ⟶ 6,338:
Cargo.toml
<
rand = '0.7.2'</
src/main.rs
<
use rand::prelude::*;
Line 5,768 ⟶ 6,383:
println!("{} / {} ({:.02}%) successes in random", random_successes, trials, random_successes as f64 * 100.0 / trials as f64);
}</
{{out}}
Line 5,775 ⟶ 6,390:
=={{header|Sather}}==
<
shuffle (a: ARRAY{INT}) is
ARR_PERMUTE_ALG{INT, ARRAY{INT}}::shuffle(a);
Line 5,833 ⟶ 6,448:
try("optimal", 100000, 10, 10, 5, bind(try_optimal(_, _, _)));
end;
end;</
{{out}}
<pre>100 prisoners, 100 drawers, 50 tries:
Line 5,845 ⟶ 6,460:
=={{header|Scala}}==
{{trans|Java}}
<
import scala.util.control.Breaks._
Line 5,904 ⟶ 6,519:
printf("Random play success rate: %f%%\n", exec(n, p, playRandom))
}
}</
{{out}}
<pre># of executions: 100,000
Optimal play success rate: 31.201000%
Random play success rate: 0.000000%</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program prisoners;
setrandom(0);
strategies := {
["Optimal", routine optimal_strategy],
["Random", routine random_strategy]
};
runs := 10000;
loop for strategy = strategies(name) do
successes := run_simulations(strategy, runs);
print(rpad(name + ":", 10), successes * 100 / runs, "%");
end loop;
proc run_simulations(strategy, amount);
loop for i in [1..amount] do
successes +:= if simulate(strategy) then 1 else 0 end;
end loop;
return successes;
end proc;
proc simulate(strategy);
drawers := [1..100];
shuffle(drawers);
loop for prisoner in [1..100] do
if not call(strategy, drawers, prisoner) then
return false;
end if;
end loop;
return true;
end proc;
proc optimal_strategy(drawers, prisoner);
d := prisoner;
loop for s in [1..50] do
if (d := drawers(d)) = prisoner then
return true;
end if;
end loop;
return false;
end proc;
proc random_strategy(drawers, prisoner);
loop for s in [1..50] do
if drawers(1+random(#drawers-1)) = prisoner then
return true;
end if;
end loop;
return false;
end proc;
proc shuffle(rw drawers);
loop for i in [1..#drawers] do
j := i+random(#drawers-i);
[drawers(i), drawers(j)] := [drawers(j), drawers(i)];
end loop;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>Optimal: 31.26 %
Random: 0 %</pre>
=={{header|Swift}}==
<
struct PrisonersGame {
Line 5,992 ⟶ 6,671:
}
dispatchMain()</
{{out}}
Line 6,002 ⟶ 6,681:
=={{header|Tcl}}==
{{trans|Common Lisp}}
<
set Prisoners 100
set MaxGuesses 50
Line 6,108 ⟶ 6,787:
}
compareStrategies $Strategies</
{{Out}}
Line 6,120 ⟶ 6,799:
{{works with|Transact-SQL|SQL Server 2017}}
<
GO
Line 6,296 ⟶ 6,975:
DROP TABLE dbo.drawers;
DROP TABLE dbo.numbers;
GO</
Output:
Line 6,303 ⟶ 6,982:
Probability of success with "random" strategy: 0.00
Probability of success with "optimal" strategy: 31.00</pre>
=={{header|Transd}}==
For checking the correctness of simulation of random selection, we can decrease the number of prisoners and increase the number of runs. Then, for 10 prisoners and 100,000 runs we should get 0.5^10 * 100,000 = about 0.1% of wins.
<syntaxhighlight lang="Scheme">#lang transd
MainModule: {
simRandom: (λ numPris Int() nRuns Int()
locals: nSucc 0.0
(for n in Range(nRuns) do
(with draws (for i in Range(numPris) project i) succ 1
(for prisN in Range(numPris) do
(shuffle draws)
(if (not (is-el Range(in: draws 0 (/ numPris 2)) prisN))
(= succ 0) break))
(+= nSucc succ)
) )
(ret (* (/ nSucc nRuns) 100))
),
simOptimal: (λ numPris Int() nRuns Int()
locals: nSucc 0.0
(for n in Range(nRuns) do
(with draws (for i in Range(numPris) project i) succ 0 nextDraw 0
(shuffle draws)
(for prisN in Range(numPris) do (= nextDraw prisN) (= succ 0)
(for i in Range( (/ numPris 2)) do
(= nextDraw (get draws nextDraw))
(if (== nextDraw prisN) (= succ 1) break))
(if (not succ) break))
(+= nSucc succ)
) )
(ret (* (/ nSucc nRuns) 100))
),
_start: (λ
(lout prec: 4 :fixed "Random play: " (simRandom 100 10000) "% of wins")
(lout "Strategic play: " (simOptimal 100 10000) "% of wins")
(lout "Check random play: " (simRandom 10 100000) "% of wins")
)
}</syntaxhighlight>
{{out}}
<pre>
Random play: 0.0000% of wins
Strategic play: 31.4500% of wins
Check random play: 0.1040% of wins
</pre>
=={{header|VBA}}/{{header|Visual Basic}}==
<
NumberOfPrisoners = Int(InputBox("Number of Prisoners", "Prisoners", 100))
Line 6,450 ⟶ 7,176:
Next Counter
End Sub</
{{out}}
Line 6,460 ⟶ 7,186:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Function PlayOptimal() As Boolean
Line 6,524 ⟶ 7,250:
End Sub
End Module</
{{out}}
<pre># of executions: 1000000
Line 6,531 ⟶ 7,257:
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
option explicit
const npris=100
Line 6,593 ⟶ 7,319:
next
trystrat=false
end function </
Output:
<pre>
0 % success for random
32.9 % success for optimal strategy
</pre>
=={{header|V (Vlang)}}==
{{trans|Wren}}
<syntaxhighlight lang="v (vlang)">import rand
import rand.seed
// Uses 0-based numbering rather than 1-based numbering throughout.
fn do_trials(trials int, np int, strategy string) {
mut pardoned := 0
for _ in 0..trials {
mut drawers := []int{len: 100, init: it}
rand.shuffle<int>(mut drawers) or {panic('shuffle failed')}
mut next_trial := false
for p in 0..np {
mut next_prisoner := false
if strategy == "optimal" {
mut prev := p
for _ in 0..50 {
this := drawers[prev]
if this == p {
next_prisoner = true
break
}
prev = this
}
} else {
// Assumes a prisoner remembers previous drawers (s)he opened
// and chooses at random from the others.
mut opened := [100]bool{}
for _ in 0..50 {
mut n := 0
for {
n = rand.intn(100) or {0}
if !opened[n] {
opened[n] = true
break
}
}
if drawers[n] == p {
next_prisoner = true
break
}
}
}
if !next_prisoner {
next_trial = true
break
}
}
if !next_trial {
pardoned++
}
}
rf := f64(pardoned) / f64(trials) * 100
println(" strategy = ${strategy:-7} pardoned = ${pardoned:-6} relative frequency = ${rf:-5.2f}%\n")
}
fn main() {
rand.seed(seed.time_seed_array(2))
trials := 100000
for np in [10, 100] {
println("Results from $trials trials with $np prisoners:\n")
for strategy in ["random", "optimal"] {
do_trials(trials, np, strategy)
}
}
}</syntaxhighlight>
{{out}}
Sample run:
<pre>
Results from 100000 trials with 10 prisoners:
strategy = random pardoned = 91 relative frequency = 0.09 %
strategy = optimal pardoned = 31321 relative frequency = 31.32%
Results from 100000 trials with 100 prisoners:
strategy = random pardoned = 0 relative frequency = 0.00 %
strategy = optimal pardoned = 31318 relative frequency = 31.32%
</pre>
Line 6,603 ⟶ 7,411:
{{trans|Go}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var rand = Random.new()
Line 6,645 ⟶ 7,453:
}
if (!nextPrisoner) {
nextTrial = true
break
}
}
Line 6,659 ⟶ 7,467:
Fmt.print("Results from $,d trials with $d prisoners:\n", trials, np)
for (strategy in ["random", "optimal"]) doTrials.call(trials, np, strategy)
}</
{{out}}
Line 6,678 ⟶ 7,486:
=={{header|XPL0}}==
<
proc KShuffle; \Randomly rearrange the cards in the drawers
Line 6,735 ⟶ 7,543:
Text(0, "Optimal strategy success rate: ");
Strategy(2);
]</
{{out}}
Line 6,745 ⟶ 7,553:
=={{header|Yabasic}}==
{{trans|Phix}}
<
// by Galileo, 05/2022
Line 6,777 ⟶ 7,585:
optimal = play(prisoners, iterations, true)
print "Prisoners: ", prisoners, ", random: ", random, ", optimal: ", optimal
next</
{{out}}
<pre>Simulation count: 10000
Line 6,783 ⟶ 7,591:
Prisoners: 100, random: 0, optimal: 31.2
---Program done, press RETURN---</pre>
=={{header|Zig}}==
{{Works with|Zig|0.11.x}}
{{Works with|Zig|0.12.0-dev.1604+caae40c21}}
<syntaxhighlight lang="zig">const std = @import("std");
pub const Cupboard = struct {
comptime {
std.debug.assert(u7 == std.math.IntFittingRange(0, 100));
}
pub const Drawer = packed struct(u8) {
already_visited: bool,
card: u7,
};
drawers: [100]Drawer,
randomizer: std.rand.Random,
/// Cupboard is not shuffled after initialization,
/// it is shuffled during `play` execution.
pub fn init(random: std.rand.Random) Cupboard {
var drawers: [100]Drawer = undefined;
for (&drawers, 0..) |*drawer, i| {
drawer.* = .{
.already_visited = false,
.card = @intCast(i),
};
}
return .{
.drawers = drawers,
.randomizer = random,
};
}
pub const Decision = enum {
pardoned,
sentenced,
};
pub const Strategy = enum {
follow_card,
random,
pub fn decisionOfPrisoner(strategy: Strategy, cupboard: *Cupboard, prisoner_id: u7) Decision {
switch (strategy) {
.random => {
return for (0..50) |_| {
// If randomly chosen drawer was already opened,
// throw dice again.
const drawer = try_throw_random: while (true) {
const random_i = cupboard.randomizer.uintLessThan(u7, 100);
const drawer = &cupboard.drawers[random_i];
if (!drawer.already_visited)
break :try_throw_random drawer;
};
std.debug.assert(!drawer.already_visited);
defer drawer.already_visited = true;
if (drawer.card == prisoner_id)
break .pardoned;
} else .sentenced;
},
.follow_card => {
var drawer_i = prisoner_id;
return for (0..50) |_| {
const drawer = &cupboard.drawers[drawer_i];
std.debug.assert(!drawer.already_visited);
defer drawer.already_visited = true;
if (drawer.card == prisoner_id)
break .pardoned
else
drawer_i = drawer.card;
} else .sentenced;
},
}
}
};
pub fn play(cupboard: *Cupboard, strategy: Strategy) Decision {
cupboard.randomizer.shuffleWithIndex(Drawer, &cupboard.drawers, u7);
// Decisions for all 100 prisoners.
var all_decisions: [100]Decision = undefined;
for (&all_decisions, 0..) |*current_decision, prisoner_id| {
// Make decision for current prisoner
current_decision.* = strategy.decisionOfPrisoner(cupboard, @intCast(prisoner_id));
// Close all drawers after one step.
for (&cupboard.drawers) |*drawer|
drawer.already_visited = false;
}
// If there is at least one sentenced person, everyone are sentenced.
return for (all_decisions) |decision| {
if (decision == .sentenced)
break .sentenced;
} else .pardoned;
}
pub fn runSimulation(cupboard: *Cupboard, strategy: Cupboard.Strategy, total: u32) void {
var success: u32 = 0;
for (0..total) |_| {
const result = cupboard.play(strategy);
if (result == .pardoned) success += 1;
}
const ratio = @as(f32, @floatFromInt(success)) / @as(f32, @floatFromInt(total));
const stdout = std.io.getStdOut();
const stdout_w = stdout.writer();
stdout_w.print(
\\
\\Strategy: {s}
\\Total runs: {d}
\\Successful runs: {d}
\\Failed runs: {d}
\\Success rate: {d:.4}%.
\\
, .{
@tagName(strategy),
total,
success,
total - success,
ratio * 100.0,
}) catch {}; // Do nothing on error
}
};</syntaxhighlight>
<syntaxhighlight lang="zig">const std = @import("std");
pub fn main() std.os.GetRandomError!void {
var prnd = std.rand.DefaultPrng.init(seed: {
var init_seed: u64 = undefined;
try std.os.getrandom(std.mem.asBytes(&init_seed));
break :seed init_seed;
});
const random = prnd.random();
var cupboard = Cupboard.init(random);
cupboard.runSimulation(.follow_card, 10_000);
cupboard.runSimulation(.random, 10_000);
}</syntaxhighlight>
{{out}}
<pre>
Strategy: follow_card
Total runs: 10000
Successful runs: 3049
Failed runs: 6951
Success rate: 30.4900%.
Strategy: random
Total runs: 10000
Successful runs: 0
Failed runs: 10000
Success rate: 0.0000%.
</pre>
=={{header|zkl}}==
<
fcn oneHundredJDI{ // just do it strategy
cupboard,picks := [0..SLOTS-1].walk().shuffle(), cupboard.copy();
Line 6,800 ⟶ 7,775:
}
True // all found their number
}</
<
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));</
{{out}}
<pre>
Line 6,812 ⟶ 7,787:
</pre>
And a sanity check (from the Raku entry):
<
{{out}}
<pre>
|