59 lines
1.5 KiB
Text
59 lines
1.5 KiB
Text
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;
|