user
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. If *any* don't then *all* sentences stand.

The task

1. Simulate several thousand instances of the game where the prisoners randomly open drawers
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. wp:100 prisoners problem
3. 100 Prisoners Escape Puzzle DataGenetics.
4. Random permutation statistics#One hundred prisoners on Wikipedia.
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2019.07.1

Accepts command line parameters to modify the number of prisoners and the number of simulations to run.

Also test with 10 prisoners to verify that the logic is correct for random selection. Random selection should succeed with 10 prisoners at a probability of (1/2)\*\*10, so in 100\_000 simulations, should get pardons about .0977 percent of the time.

```
unit sub MAIN (:$prisoners = 100, :$simulations = 10000);
my @prisoners = ^$prisoners;
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
}

say "Testing $simulations simulations with $prisoners prisoners.";
printf " Random play wins: %.3f%% of simulations\n", random $simulations;
printf "Optimal play wins: %.3f%% of simulations\n", optimal $simulations;

```

Output:

**With defaults**

```
Testing 10000 simulations with 100 prisoners.
 Random play wins: 0.000% of simulations
Optimal play wins: 30.510% of simulations
```

**With passed parameters: --prisoners=10, --simulations=100000**

```
Testing 100000 simulations with 10 prisoners.
 Random play wins: 0.099% of simulations
Optimal play wins: 35.461% of simulations

```