100 prisoners: Difference between revisions
Add Ecstasy example
(Add Ecstasy example) |
|||
| (21 intermediate revisions by 15 users not shown) | |||
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">
Line 533 ⟶ 577:
Random Strategy = 0.00%
</pre>
=={{header|APL}}==
{{works with|GNU APL|1.8}}
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 880 ⟶ 938:
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}}==
<syntaxhighlight lang="autohotkey">NumOfTrials := 20000
Line 942 ⟶ 1,028:
Random Trials : 0.000000 % success rate</pre>
=={{header|
==={{header|BASIC256}}===
{{works with|BASIC256|2.0.0.11}}
<syntaxhighlight lang="basic256">
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}}==
Line 2,004 ⟶ 2,134:
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>
Line 2,611 ⟶ 2,883:
sTime += 0.001
cls
printf @"
timerend
Line 2,627 ⟶ 2,899:
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
Line 2,648 ⟶ 2,922:
{{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>
Line 2,838 ⟶ 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}}==
Line 3,619 ⟶ 3,970:
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>
Line 4,557 ⟶ 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 6,069 ⟶ 6,524:
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}}==
Line 6,463 ⟶ 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}}==
Line 6,760 ⟶ 7,326:
</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.
Line 6,845 ⟶ 7,411:
{{trans|Go}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
var rand = Random.new()
Line 6,887 ⟶ 7,453:
}
if (!nextPrisoner) {
nextTrial = true
break
}
}
Line 7,025 ⟶ 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}}==
| |||