100 prisoners: Difference between revisions
Add Ecstasy example
(Add Ecstasy example) |
|||
| (12 intermediate revisions by 7 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 1,074 ⟶ 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,046 ⟶ 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
for prisoner = 1 to 100
found = 0
for i = 1 to 50
r =
card = drawer[sampler[r]]
swap sampler[r] sampler[100 - i - 1]
if card = prisoner
found = 1
break 1
.
.
.
subr play_optimal
for prisoner = 1 to 100
reveal = prisoner
found = 0
for i = 1 to 50
card = drawer[reveal]
if card = prisoner
found = 1
break 1
.
reveal = card
.
.
n = 10000
win = 0
for _ = 1 to n
win += found
.
print "random: " & 100.0 * win / n & "%"
#
win = 0
for _ = 1 to n
win += found
.
print "optimal: " & 100.0 * win / n & "%"
</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 4,779 ⟶ 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,291 ⟶ 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 7,114 ⟶ 7,411:
{{trans|Go}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
var rand = Random.new()
Line 7,156 ⟶ 7,453:
}
if (!nextPrisoner) {
nextTrial = true
break
}
}
Line 7,294 ⟶ 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}}==
| |||