106 lines
3.6 KiB
JavaScript
106 lines
3.6 KiB
JavaScript
"use strict";
|
|
|
|
// Simulate several thousand instances of the game:
|
|
const gamesCount = 2000;
|
|
|
|
// ...where the prisoners randomly open drawers.
|
|
const randomResults = playGame(gamesCount, randomStrategy);
|
|
|
|
// ...where the prisoners use the optimal strategy mentioned in the Wikipedia article.
|
|
const optimalResults = playGame(gamesCount, optimalStrategy);
|
|
|
|
// Show and compare the computed probabilities of success for the two strategies.
|
|
console.log(`Games count: ${gamesCount}`);
|
|
console.log(`Probability of success with "random" strategy: ${computeProbability(randomResults, gamesCount)}`);
|
|
console.log(`Probability of success with "optimal" strategy: ${computeProbability(optimalResults, gamesCount)}`);
|
|
|
|
function playGame(gamesCount, strategy, prisonersCount = 100) {
|
|
const results = new Array();
|
|
|
|
for (let game = 1; game <= gamesCount; game++) {
|
|
// A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
|
|
// Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
|
|
const drawers = initDrawers(prisonersCount);
|
|
|
|
// A prisoner tries to find his own number.
|
|
// Prisoners start outside the room.
|
|
// They can decide some strategy before any enter the room.
|
|
let found = 0;
|
|
for (let prisoner = 1; prisoner <= prisonersCount; prisoner++, found++)
|
|
if (!find(prisoner, drawers, strategy)) break;
|
|
|
|
// If all 100 findings find their own numbers then they will all be pardoned. If any don't then all sentences stand.
|
|
results.push(found == prisonersCount);
|
|
}
|
|
|
|
return results;
|
|
}
|
|
|
|
function find(prisoner, drawers, strategy) {
|
|
// A prisoner can open no more than 50 drawers.
|
|
const openMax = Math.floor(drawers.length / 2);
|
|
|
|
// Prisoners start outside the room.
|
|
let card;
|
|
for (let open = 0; open < openMax; open++) {
|
|
// A prisoner tries to find his own number.
|
|
card = strategy(prisoner, drawers, card);
|
|
|
|
// A prisoner finding his own number is then held apart from the others.
|
|
if (card == prisoner)
|
|
break;
|
|
}
|
|
|
|
return (card == prisoner);
|
|
}
|
|
|
|
function randomStrategy(prisoner, drawers, card) {
|
|
// Simulate the game where the prisoners randomly open drawers.
|
|
|
|
const min = 0;
|
|
const max = drawers.length - 1;
|
|
|
|
return drawers[draw(min, max)];
|
|
}
|
|
|
|
function optimalStrategy(prisoner, drawers, card) {
|
|
// Simulate the game where the prisoners use the optimal strategy mentioned in the Wikipedia article.
|
|
|
|
// First opening the drawer whose outside number is his prisoner number.
|
|
// If the card within has his number then he succeeds...
|
|
if (typeof card === "undefined")
|
|
return drawers[prisoner - 1];
|
|
|
|
// ...otherwise he opens the drawer with the same number as that of the revealed card.
|
|
return drawers[card - 1];
|
|
}
|
|
|
|
function initDrawers(prisonersCount) {
|
|
const drawers = new Array();
|
|
for (let card = 1; card <= prisonersCount; card++)
|
|
drawers.push(card);
|
|
|
|
return shuffle(drawers);
|
|
}
|
|
|
|
function shuffle(drawers) {
|
|
const min = 0;
|
|
const max = drawers.length - 1;
|
|
for (let i = min, j; i < max; i++) {
|
|
j = draw(min, max);
|
|
if (i != j)
|
|
[drawers[i], drawers[j]] = [drawers[j], drawers[i]];
|
|
}
|
|
|
|
return drawers;
|
|
}
|
|
|
|
function draw(min, max) {
|
|
// See: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random
|
|
return Math.floor(Math.random() * (max - min + 1)) + min;
|
|
}
|
|
|
|
function computeProbability(results, gamesCount) {
|
|
return Math.round(results.filter(x => x == true).length * 10000 / gamesCount) / 100;
|
|
}
|