100Prisoners.ts

//shuffle array
function shuffle(array: number[]) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1))
    ;[array[i], array[j]] = [array[j], array[i]]
  }
  return array
}

// console.log(box, prisoners)
const mainLoop = () => {
  const box = shuffle(Array.from(Array(100), (v, i) => i + 1))

  const prisoners = Array.from(Array(100), (v, i) => i + 1)
  let failed = 0
  let success = 0
  let loop: number[] = []
  prisoners.forEach((prisoner) => {
    let found = false
    let guess = prisoner
    let trying = 0
    let guesses: Array<{ guess: number; index: number }> = []
    while (!found) {
      trying++
      const index = box[guess - 1]
      guesses.push({ guess, index })
      if (index === prisoner && trying < 51) {
        found = true
        success++
        loop.push(trying)
        break
      }

      if (index === prisoner && trying > 50) {
        failed++
        loop.push(trying)
        break
      }

      guess = index
    }

    // console.log(
    //   `\nprisoner ${prisoner} tried ${trying} times\n`,
    //   guesses.map((g) => `${g.guess}(${g.index})`).join("->")
    // )
  })

  // console.log(failed, success)
  //  filter loop with unique values
  // const uniqueLoop = [...new Set(loop)]
  // console.log(uniqueLoop)

  return !failed
}
const randomLoop = () => {
  const box = shuffle(Array.from(Array(100), (v, i) => i + 1))

  const prisoners = Array.from(Array(100), (v, i) => i + 1)
  let failed = 0
  let success = 0
  let loop: number[] = []
  prisoners.forEach((prisoner) => {
    let found = false
    let guess = Math.floor(Math.random() * 100)
    let trying = 0
    let guesses: Array<number> = [guess]
    while (!found) {
      trying++
      const index = box[guess]
      guesses.push(guess)
      if (index === prisoner && trying < 51) {
        found = true
        success++
        loop.push(trying)
        break
      }

      if (index === prisoner && trying > 50) {
        failed++
        loop.push(trying)
        break
      }

      guess = (() => {
        let newGuess = Math.floor(Math.random() * 100) // random number between 0 and 99
        while (true) {
          if (guesses.includes(newGuess)) {
            newGuess = Math.floor(Math.random() * 100)
          } else break
        }
        return newGuess
      })()
    }

    // console.log(
    //   `\nprisoner ${prisoner} tried ${trying} times\n`,
    //   guesses.join("->")
    // )
  })

  // console.log(failed, success)
  //  filter loop with unique values
  // const uniqueLoop = [...new Set(loop)]
  return !failed
}

const loop = 10000

const main = () => {
  let mainLoopSuccess = 0
  for (let i = 0; i < loop; i++) {
    const result = mainLoop()
    if (result) mainLoopSuccess++
  }

  console.log(`main loop success: ${(mainLoopSuccess / loop) * 100}%`)
  let randomLoopSuccess = 0
  for (let i = 0; i < loop; i++) {
    const result = randomLoop()
    if (result) randomLoopSuccess++
  }
  console.log(`random guess success: ${(randomLoopSuccess / loop) * 100}%`)
}

main()