100 prisoners

100 prisoners
You are encouraged to solve this task according to the task description, using any language you may know.

This page uses content from Wikipedia. The original article was at 100 prisoners problem. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

The Problem

• 100 prisoners are individually numbered 1 to 100
• 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.
• Prisoners start outside the room

• They can decide some strategy before any enter the room.
• Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
• A prisoner can open no more than 50 drawers.
• A prisoner tries to find his own number.
• A prisoner finding his own number is then held apart from the others.

• If all 100 prisoners find their own numbers then they will all be pardoned.

The task

1. Simulate several thousand instances of the game where the prisoners randomly open draws
2. Simulate several thousand instances of the game where the prisoners use the optimal strategy mentioned in the wikipedia article, of:

• First opening the drawer whose outside number is his prisoner number.
• If the card within has his number then he succeeds otherwise he opens the drawer with the same number as that of the revealed card. (until he opens his maximum).

Show and compare the computed probabilities of success for the two strategies, here, on this page.

References

1. The unbelievable solution to the 100 prisoner puzzle standupmaths (Video).
2. 100 Prisoners Escape Puzzle DataGenetics.

EasyLang

<lang EasyLang>for i range 100

 drawer[] &= i
 sampler[] &= i

. subr shuffle_drawer

 for i = len drawer[] downto 2
   r = random i
   swap drawer[r] drawer[i - 1]
 .

. subr play_random

 call shuffle_drawer
 found = 1
 prisoner = 0
 while prisoner < 100 and found = 1
   found = 0
   i = 0
   while i < 50 and found = 0
     r = random (100 - i)
     card = drawer[sampler[r]]
     swap sampler[r] sampler[100 - i - 1]
     if card = prisoner
       found = 1
     .
     i += 1
   .
   prisoner += 1
 .

. subr play_optimal

 call shuffle_drawer
 found = 1
 prisoner = 0
 while prisoner < 100 and found = 1
   reveal = prisoner
   found = 0
   i = 0
   while i < 50 and found = 0
     card = drawer[reveal]
     if card = prisoner
       found = 1
     .
     reveal = card
     i += 1
   .
   prisoner += 1
 .

. n = 10000 pardoned = 0 for round range n

 call play_random
 pardoned += found

. print "random: " & 100.0 * pardoned / n & "%"

pardoned = 0 for round range n

 call play_optimal
 pardoned += found

. print "optimal: " & 100.0 * pardoned / n & "%"</lang>

Output:

random: 0.000%
optimal: 30.800%

Factor

<lang factor>USING: arrays formatting fry io kernel math random sequences ;

setup ( -- seq seq ) 100 <iota> dup >array randomize ;

rand ( -- ? )

   setup [ 50 sample member? not ] curry find nip >boolean not ;

trail ( m seq -- n )

   50 pick '[ [ nth ] keep over _ = ] replicate [ t = ] any?
   2nip ;

optimal ( -- ? ) setup [ trail ] curry [ and ] map-reduce ;

simulate ( m quot -- x )

   dupd replicate [ t = ] count swap /f 100 * ; inline

"Simulation count: 10,000" print 10,000 [ rand ] simulate "Random play success: " 10,000 [ optimal ] simulate "Optimal play success: " [ write "%.2f%%\n" printf ] 2bi@</lang>

Output:

Simulation count: 10,000
Random play success: 0.00%
Optimal play success: 31.11%

Go

<lang go>package main

import (

   "fmt"
   "math/rand"
   "time"

)

// Uses 0-99 numbering rather than 1-100 numbering throughout. func doTrials(trials int, strategy string) {

   pardoned := 0

trial:

   for t := 0; t < trials; t++ {
       var drawers [100]int
       for i := 0; i < 100; i++ {
           drawers[i] = i
       }
       rand.Shuffle(100, func(i, j int) {
           drawers[i], drawers[j] = drawers[j], drawers[i]
       })
   prisoner:
       for p := 0; p < 100; p++ {
           if strategy == "optimal" {
               prev := p
               for d := 0; d < 50; d++ {
                   this := drawers[prev]
                   if this == p {
                       continue prisoner
                   }
                   prev = this
               }
           } else {
               // Assumes a prisoner remembers previous drawers (s)he opened
               // and chooses at random from the others.
               var opened [100]bool
               for d := 0; d < 50; d++ {
                   var n int
                   for {
                       n = rand.Intn(100)
                       if !opened[n] {
                           opened[n] = true
                           break
                       }
                   }
                   if drawers[n] == p {
                       continue prisoner
                   }
               }
           }
           continue trial
       }
       pardoned++
   }
   rf := float64(pardoned) / float64(trials) * 100
   fmt.Printf("strategy = %-7s  pardoned = %-6d relative frequency = %4.1f%%\n\n", strategy, pardoned, rf)

}

func main() {

   rand.Seed(time.Now().UnixNano())
   const trials = 100_000
   fmt.Printf("Results from %d trials:\n\n", trials)
   for _, strategy := range [2]string{"random", "optimal"} {
       doTrials(trials, strategy)
   }

}</lang>

Output:

Results from 100000 trials:

strategy = random   pardoned = 0      relative frequency =  0.0%

strategy = optimal  pardoned = 31060  relative frequency = 31.1%

Perl 6

Works with: Rakudo version 2019.07.1

Translation of: Python

<lang perl6>my @prisoners = ^100; my $half = floor +@prisoners / 2;

sub random ($n) {

   ^$n .race.map( {
       my @drawers = @prisoners.pick: *;
       @prisoners.map( -> $prisoner {
           my $found = 0;
           for @drawers.pick($half) -> $card {
               $found = 1 and last if $card == $prisoner
           }
           last unless $found;
           $found
       }
       ).sum == @prisoners
   }
   ).grep( *.so ).elems / $n * 100

}

sub optimal ($n) {

   ^$n .race.map( {
       my @drawers = @prisoners.pick: *;
       @prisoners.map( -> $prisoner {
           my $found = 0;
           my $card = @drawers[$prisoner];
           if $card == $prisoner {
               $found = 1
           } else {
               for ^($half - 1) {
                   $card = @drawers[$card];
                   $found = 1 and last if $card == $prisoner
               }
           }
           last unless $found;
           $found
       }
       ).sum == @prisoners
   }
   ).grep( *.so ).elems / $n * 100

}

my $n = 10_000; say " Simulation count: $n\n" ~ sprintf(" Random play wins: %4.1f%% of simulations\n", random $n) ~ sprintf("Optimal play wins: %4.1f%% of simulations\n", optimal $n);</lang>

Output:

 Simulation count: 10000
 Random play wins:  0.0% of simulations
Optimal play wins: 31.9% of simulations

Python

<lang python>import random

def play_random(n):

   # using 0-99 instead of ranges 1-100
   pardoned = 0
   in_drawer = list(range(100))
   sampler = list(range(100))
   for _round in range(n):
       random.shuffle(in_drawer)
       found = False
       for prisoner in range(100):
           found = False
           for reveal in random.sample(sampler, 50):
               card = in_drawer[reveal]
               if card == prisoner:
                   found = True
                   break
           if not found:
               break
       if found:
           pardoned += 1
   return pardoned / n * 100   # %

def play_optimal(n):

   # using 0-99 instead of ranges 1-100
   pardoned = 0
   in_drawer = list(range(100))
   for _round in range(n):
       random.shuffle(in_drawer)
       for prisoner in range(100):
           reveal = prisoner
           found = False
           for go in range(50):
               card = in_drawer[reveal]
               if card == prisoner:
                   found = True
                   break
               reveal = card
           if not found:
               break
       if found:
           pardoned += 1
   return pardoned / n * 100   # %

if __name__ == '__main__':

   n = 100_000
   print(" Simulation count:", n)
   print(f" Random play wins: {play_random(n):4.1f}% of simulations")
   print(f"Optimal play wins: {play_optimal(n):4.1f}% of simulations")</lang>

Output:

 Simulation count: 100000
 Random play wins:  0.0% of simulations
Optimal play wins: 31.1% of simulations

REXX

<lang rexx>/*REXX program to simulate the problem of 100 prisoners: random, and optimal strategy.*/ parse arg men trials seed . /*obtain optional arguments from the CL*/ if men== | men=="," then men= 100 /*number of prisoners for this run.*/ if trials== | trials=="," then trials= 100000 /* " " simulations " " " */ if datatype(seed, 'W') then call random ,,seed /*seed for the random number generator.*/ $.1= ' a simple '; $.2= "an optimal" /*literals used for the SAY instruction*/ try= men % 2 /*number tries for searching for a card*/

   do strategy=1  for 2;    pardons= 0          /*perform the two types of strategies. */
     do trials;             call gCards         /*do trials for a strategy;  gen cards.*/
       do p=1  for men                          /*have each prisoner go through trial. */
       if strategy==1  then call simple         /*perform the  simple  strategy.       */
                       else call pick           /*   "     "  optimal      "           */
       end   /*p*/
     if #==men  then pardons= pardons + 1       /*was there a pardon of all prisoners? */
     end     /*trials*/
   say commas(men)   'prisoners in'   commas(trials)    "trials, complete pardons using",
       $.strategy  "strategy: "    left(, pardons==0)format(pardons/trials*100, , 1)"%"
   end       /*strategy*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do c=length(_)-3 to 1 by -3; _= insert(',', _, c); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ gCards: #=0; cards=; m=men; do j=1 for m; cards= cards j /*define seq. of cards*/

                                end   /*j*/                      /*same as seq. of men.*/
         do r=1  for men-1;  x= random(1,m);  @.r= word(cards,x) /*pick a random card. */
         cards= delword(cards, x, 1);         m= m - 1           /*del a card; new cnt.*/
         end   /*r*/                                             /*only one card left. */
       @.men= strip(cards);        return                        /*it has extra blank. */

/*──────────────────────────────────────────────────────────────────────────────────────*/ simple: do try;  ?= random(1, men); if @.?==p then do; #= #+1; return; end

           end   /*try*/;          return       /* [↑] has the prisoner found his card?*/

/*──────────────────────────────────────────────────────────────────────────────────────*/ pick: ?=p; do try; if @.?==p then do; #= #+1; return; end /*Found his own card?*/

           ?= @.?                               /*choose next drawer from previous card*/
           end   /*try*/;          return       /*only choose 1/2 of the num of drawers*/</lang>

output   when using the default inputs:

100 prisoners in 100,000 trials, complete pardons using  a simple  strategy:   0.0%
100 prisoners in 100,000 trials, complete pardons using an optimal strategy:  31.2%

Rust

Fairly naive implementation. Could probably be made more idiomatic. Depends on extern rand crate.

Cargo.toml <lang toml>[dependencies] rand = '0.7.2'</lang>

src/main.rs <lang rust>extern crate rand;

use rand::prelude::*;

// Do a full run of checking boxes in a random order for a single prisoner fn check_random_boxes(prisoner: u8, boxes: &[u8]) -> bool {

   let checks = {
       let mut b: Vec<u8> = (1u8..=100u8).collect();
       b.shuffle(&mut rand::thread_rng());
       b
   };
   checks.into_iter().take(50).any(|check| boxes[check as usize - 1] == prisoner)

}

// Do a full run of checking boxes in the optimized order for a single prisoner fn check_ordered_boxes(prisoner: u8, boxes: &[u8]) -> bool {

   let mut next_check = prisoner;
   (0..50).any(|_| {
       next_check = boxes[next_check as usize - 1];
       next_check == prisoner
   })

}

fn main() {

   let mut boxes: Vec<u8> = (1u8..=100u8).collect();

   let trials = 100000;

   let ordered_successes = (0..trials).filter(|_| {
       boxes.shuffle(&mut rand::thread_rng());
       (1u8..=100u8).all(|prisoner| check_ordered_boxes(prisoner, &boxes))
   }).count();

   let random_successes = (0..trials).filter(|_| {
       boxes.shuffle(&mut rand::thread_rng());
       (1u8..=100u8).all(|prisoner| check_random_boxes(prisoner, &boxes))
   }).count();

   println!("{} / {} ({:.02}%) successes in ordered", ordered_successes, trials, ordered_successes as f64 * 100.0 / trials as f64);
   println!("{} / {} ({:.02}%) successes in random", random_successes, trials, random_successes as f64 * 100.0 / trials as f64);

}</lang>

Output:

31106 / 100000 (31.11%) successes in ordered
0 / 100000 (0.00%) successes in random