59 lines
1.8 KiB
Text
59 lines
1.8 KiB
Text
class MAIN is
|
|
shuffle (a: ARRAY{INT}) is
|
|
ARR_PERMUTE_ALG{INT, ARRAY{INT}}::shuffle(a);
|
|
end;
|
|
|
|
try_random (n: INT, drawers: ARRAY{INT}, tries: INT): BOOL is
|
|
my_tries ::= drawers.inds; shuffle(my_tries);
|
|
loop tries.times!;
|
|
if drawers[my_tries.elt!] = n then return true; end;
|
|
end;
|
|
return false;
|
|
end;
|
|
|
|
try_optimal (n: INT, drawers: ARRAY{INT}, tries: INT): BOOL is
|
|
num ::= n;
|
|
loop tries.times!;
|
|
num := drawers[num];
|
|
if num = n then return true; end;
|
|
end;
|
|
return false;
|
|
end;
|
|
|
|
stats (label: STR, rounds, successes: INT): STR is
|
|
return #FMT("<^###########>: <#######> rounds. Successes: <#######> (<##.###>%%)\n",
|
|
label, rounds, successes, (successes.flt / rounds.flt)*100.0).str;
|
|
end;
|
|
|
|
try (name: STR, nrounds, ndrawers, npris, ntries: INT,
|
|
strategy: ROUT{INT,ARRAY{INT},INT}:BOOL)
|
|
is
|
|
drawers: ARRAY{INT} := #(ndrawers);
|
|
loop drawers.set!(drawers.ind!); end;
|
|
successes ::= 0;
|
|
loop nrounds.times!;
|
|
shuffle(drawers);
|
|
success ::= true;
|
|
loop
|
|
n ::= npris.times!;
|
|
if ~strategy.call(n, drawers, ntries) then
|
|
success := false;
|
|
break!;
|
|
end;
|
|
end;
|
|
if success then successes := successes + 1; end;
|
|
end;
|
|
#OUT + stats(name, nrounds, successes);
|
|
end;
|
|
|
|
main is
|
|
RND::seed := #TIMES.wall_time;
|
|
#OUT +"100 prisoners, 100 drawers, 50 tries:\n";
|
|
try("random", 100000, 100, 100, 50, bind(try_random(_, _, _)));
|
|
try("optimal", 100000, 100, 100, 50, bind(try_optimal(_, _, _)));
|
|
|
|
#OUT +"\n10 prisoners, 10 drawers, 5 tries:\n";
|
|
try("random", 100000, 10, 10, 5, bind(try_random(_, _, _)));
|
|
try("optimal", 100000, 10, 10, 5, bind(try_optimal(_, _, _)));
|
|
end;
|
|
end;
|