100 prisoners: Difference between revisions

===School example===

{{works with|JavaScript|Node.js 16.13.0 (LTS)}}

<lang 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.

const findings = new Array();

for (let prisoner = 1; prisoner <= prisonersCount; prisoner++)

findings.push(find(prisoner, drawers, strategy));

// If all 100 findings find their own numbers then they will all be pardoned. If any don't then all sentences stand.

results.push((findings.filter(p => p == true).length == 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;

}</lang>

Output:

<lang>Games count: 2000

Probability of success with "random" strategy: 0

Probability of success with "optimal" strategy: 33.2</lang>