JavaScript: 100 prisoners

17 Aug, 2022

Again?

Yes again! I first did this in PowerShell, then in Power Query, and in C# to learn the basics of the language, but I had to go back and do this in JavaScript just to make sure I know how.

Things I learned

After all this time in amateur-level dabbling in JavaScript, there are still things that caught me off guard.

Reference types

There is a point in the script where I do something like this:

const hundred = sequence(1, 100) // this is an array
const prisonerNumbers = hundred // pay attention to this line

... // much later on...

prisonerNumbers.splice(randomNumber, 1) // I take out an element from the array prisonerNumbers

It turns out, that last line was also mutating the array hundred, and as a consequence, one of the loops I was running was behaving unexpectedly (instead of running 100 times as I expected, it was running only 50 times).

It turns out, arrays in JavaScript are reference types, which is why I had to do something like this:

const prisonerNumbers = Array.from(hundred) // copy the array to a new array

Sequence of numbers

Apparently JavaScript doesn't have a native way of easily making an array of numbers (e.g. you can go @(1..5) to make the numbers 1 to 5 in PowerShell).

So, I packaged up a one-lined I found on Stack Overflow into a function:

function sequence(start, end) {
    // e.g. given (1, 10), will return [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    return Array.from({ length: (end - start + 1) }, (_, i) => i + start)
}

Code

function sequence(start, end) {
    // e.g. given (1, 10), will return [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    return Array.from({ length: (end - start + 1) }, (_, i) => i + start)
}

function makeCabinet() {
    const hundred = sequence(1, 100)
    let cabinet = []

    // need to copy the array hundred, otherwise they will be treated as the same (reference type)
    const prisonerNumbers = Array.from(hundred)

    // set up a cabinet of 100 boxes with random prisoner number assignments

    hundred.forEach((_) => {

        const randomNumber = Math.floor(Math.random() * prisonerNumbers.length)

        const prisonerNumber = prisonerNumbers[randomNumber]

        const box = {
            number: _,
            prisonerNumber: prisonerNumber
        }

        prisonerNumbers.splice(randomNumber, 1)
        cabinet.push(box)
    })

    return cabinet
}

// look into a box and see which prisoner number is in it
function checkBoxContents(boxNumber) {
    return cabinet[boxNumber - 1].prisonerNumber
}

// get one prisoner to search through their allowed 50 attempts

function searchThroughBoxes(prisonerNumber) {
    let found = false
    let count = 0
    const startingNumber = prisonerNumber
    let nextNumber
    let out = ''

    while (!found && count < 50) {
        if (count == 0) {
            nextNumber = checkBoxContents(startingNumber)
        } else {
            nextNumber = checkBoxContents(nextNumber)
        }

        count++

        if (nextNumber == prisonerNumber) {
            found = true
            out = `Prisoner #${prisonerNumber} found in ${count} attempts!`
        }
    }

    if (!found) {
        out = `Prisoner #${prisonerNumber} search failed, everybody dies.`
    }

    return found
}

function trialGroupOfPrisoners() {
    let alive = true
    let found = false

    // start with prisoner #1
    let prisonerNumber = 1

    // get all the prisoners to go through and search
    while (alive && prisonerNumber < 100) {
        found = searchThroughBoxes(prisonerNumber)
        
        if (!found) {
            alive = false
            console.log('Search failed, everybody dies')
        } else {
            prisonerNumber++
        }
    }
    
    return alive
}

const lifetimes = 1000

let successes = 0

for (let i = 0; i < lifetimes; i++) {
    cabinet = makeCabinet()

    if (trialGroupOfPrisoners()) {
        console.log('Everybody lives and goes free!')
        successes++
    }
}

console.log({rate: successes/lifetimes})

#javascript #montecarlo