How to resolve the algorithm 100 prisoners step by step in the BCPL programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm 100 prisoners step by step in the BCPL programming language
Table of Contents
Problem Statement
Show and compare the computed probabilities of success for the two strategies, here, on this page.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm 100 prisoners step by step in the BCPL programming language
Source code in the bcpl programming language
get "libhdr"
manifest $(
seed = 12345 // for pseudorandom number generator
size = 100 // amount of drawers and prisoners
tries = 50 // amount of tries each prisoner may make
simul = 2000 // amount of simulations to run
$)
let randto(n) = valof
$( static $( state = seed $)
let mask = 1
mask := (mask<<1)|1 repeatuntil mask > n
state := random(state) repeatuntil ((state >> 8) & mask) < n
resultis (state >> 8) & mask
$)
// initialize drawers
let placeCards(d, n) be
$( for i=0 to n-1 do d!i := i;
for i=0 to n-2 do
$( let j = i+randto(n-i)
let k = d!i
d!i := d!j
d!j := k
$)
$)
// random strategy (prisoner 'p' tries to find his own number)
let randoms(d, p, t) = valof
$( for n = 1 to t do
if d!randto(size) = p then resultis true
resultis false
$)
// optimal strategy
let optimal(d, p, t) = valof
$( let last = p
for n = 1 to t do
test d!last = p
then resultis true
else last := d!last
resultis false
$)
// run a simulation given a strategy
let simulate(d, strat, n, t) = valof
$( placeCards(d, n)
for p = 0 to n-1 do
if not strat(d, p, t) then resultis false
resultis true
$)
// run many simulations and count the successes
let runSimulations(d, strat, n, amt, t) = valof
$( let succ = 0
for i = 1 to amt do
if simulate(d, strat, n, t) do
succ := succ + 1
resultis succ
$)
let run(d, name, strat, n, amt, t) be
$( let s = runSimulations(d, strat, n, amt, t);
writef("%S: %I5 of %I5, %N percent.*N", name, s, amt, s*10/(amt/10))
$)
let start() be
$( let d = vec size-1
run(d, " Random", randoms, size, simul, tries)
run(d, "Optimal", optimal, size, simul, tries)
$)
You may also check:How to resolve the algorithm Catalan numbers step by step in the C programming language
You may also check:How to resolve the algorithm Fusc sequence step by step in the Mathematica / Wolfram Language programming language
You may also check:How to resolve the algorithm Jacobsthal numbers step by step in the Gambas programming language
You may also check:How to resolve the algorithm Holidays related to Easter step by step in the Factor programming language
You may also check:How to resolve the algorithm Gamma function step by step in the TXR programming language