100 prisoners: Difference between revisions

{{trans|Python}}

 

V pardoned = 0

V in_drawer = Array(0.<100)

print(‘ Simulation count: ’n)

print(‘ Random play wins: #2.1% of simulations’.format(play_random(n)))

 

{{out}}

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program prisonniex64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

<pre>

Random strategie : 0 sur 1000

</pre>

 

=={{header|Ada}}==

package Prisoners is

 

 

end Prisoners;

pragma Ada_2012;

with Ada.Numerics.Discrete_Random;

 

end Prisoners;

with Prisoners; use Prisoners;

with Ada.Text_IO; use Ada.Text_IO;

Put ("%");

end Main;

{{out}}

<pre>

Random Strategy = 0.00%

</pre>

=={{header|APL}}==

{{works with|GNU APL|1.8}}

 

∇ R ← random Nnc; N; n; c

(N n c) ← Nnc

∇

 

 

 

=={{header|Applesoft BASIC}}==

Actual test of 4000 trials for each method were run on the KEGSMAC emulator with MHz set to No Limit.

 

 

1 FOR X = 0 TO N:J(X) = X: NEXT: FOR I = 0 TO N:FOR X = 0 TO N:T = J(X):NP = INT ( RND (1) * H):J(X) = J(NP):J(NP) = T: NEXT :FOR G = 1 TO W:IF D(J(G)) = I THEN IP = IP + 1: NEXT I: RETURN

1110 GET K$

1120 Q = K$ <> "Y" AND K$ <> CHR$(ASC("Y") + 32) : NEXT Q

 

{{out}}

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program prisonniers.s */

/***************************************************/

.include "../affichage.inc"

<pre>

Random strategie : 0 sur 1000

Optimal strategie : 303 sur 1000

</pre>

=={{header|AutoHotkey}}==

randomFailTotal := 0, strategyFailTotal := 0

prisoners := [], drawers := [], Cards := []

MsgBox % "Number Of Trials = " NumOfTrials

. "`nOptimal Strategy:`t" (1 - strategyFailTotal/NumOfTrials) *100 " % success rate"

Outputs:<pre>Number Of Trials = 20000

Optimal Strategy: 33.275000 % success rate

Random Trials : 0.000000 % success rate</pre>

 

{{works with|BASIC256|2.0.0.11}}

O = 50

N = 2*O

print "Smart choices: "; total;" out of ";iterations

print "Observed ratio: "; total/iterations; ", expected ratio with N=2*O: greater than about 0.30685": REM for N=100, O=50 particularly, about 0.3118

{{out}}

<pre>

Observed ratio: 0.3052, expected ratio with N=2*O: greater than about 0.30685

</pre>

 

=={{header|BCPL}}==

 

manifest $(

run(d, " Random", randoms, size, simul, tries)

run(d, "Optimal", optimal, size, simul, tries)

{{out}}

<pre>

 

=={{header|C}}==

#include<stdbool.h>

#include<stdlib.h>

}

 

<pre>

$ gcc 100prisoners.c && ./a.out 100 50 10000

=={{header|C sharp|C#}}==

{{trans|D}}

using System.Linq;

 

}

}

{{out}}

<pre># of executions: 1000000

 

=={{header|C++}}==

#include <algorithm> // for random_shuffle

#include <iostream> // for output

system("PAUSE"); // for Windows

return 0;

{{out}}

<pre>Random strategy: 0 %

 

=={{header|Clojure}}==

 

(defn random-drawers []

(let [{:keys [random-successes optimal-successes run-count]} (simulate-n-runs 5000)]

(println (str "Probability of survival with random search: " (float (/ random-successes run-count))))

 

{{out}}

 

=={{header|CLU}}==

% to use the random number generator.

%

show(" Random", simulations, prisoners, tries, rand_strat)

show("Optimal", simulations, prisoners, tries, opt_strat)

{{out}}

<pre> Random: 0 out of 50000, 0.00%

The key here is avoiding the use of GOTO as a means of exiting a loop early.

 

10 rem 100 prisoners

20 rem set arrays

4030 r=int(rnd(1)*100)+1:t=dr(i):dr(i)=dr(r):dr(r)=t:next

4040 return

 

{{out}}

{{trans|Racket}}

 

(defparameter *samples* 10000)

(defparameter *prisoners* 100)

(format t "Using a random strategy in ~4,2F % of the cases the prisoners are free.~%" (* (/ (sampling #'strategy-1) *samples*) 100))

(format t "Using an optimal strategy in ~4,2F % of the cases the prisoners are free.~%" (* (/ (sampling #'strategy-2) *samples*) 100)))

 

{{out}}

=={{header|Cowgol}}==

 

include "argv.coh";

 

 

RunAndPrint("Stupid", Stupid);

{{out}}

<pre>Stupid strategy: 0 out of 2000 - 0%

Based on the Ruby implementation

 

N = 100_000

generate_rooms = ->{ (1..100).to_a.shuffle }

end

end

{{out}}

<pre>Random strategy : 0.0000 %

=={{header|D}}==

{{trans|Kotlin}}

import std.random;

import std.range;

writefln("Optimal play success rate: %11.8f%%", exec(N, &playOptimal));

writefln(" Random play success rate: %11.8f%%", exec(N, &playRandom));

{{out}}

<pre># of executions: 1000000

Optimal play success rate: 31.16100000%

Random play success rate: 0.00000000%</pre>

=={{header|Delphi}}==

See [[#Pascal]].

=={{header|EasyLang}}==

.

subr shuffle_drawer

.

subr play_random

.

.

subr play_optimal

.

.

n = 10000

.

.

{{out}}

<pre>

random: 0.000%

optimal: 30.800%

</pre>

 

=={{header|Elixir}}==

{{trans|Ruby}}

def optimal_room(_, _, _, []), do: []

def optimal_room(prisoner, current_room, rooms, [_ | tail]) do

end)

 

{{out}}

<pre>

 

=={{header|F sharp|F#}}==

let shuffled min max =

[|min..max|] |> Array.sortBy (fun _ -> rnd.Next(min,max+1))

printfn $"Using Random Strategy: {(outcomeOfRandom 20000):p2}"

printfn $"Using Optimum Strategy: {(outcomeOfOptimize 20000):p2}"

{{out}}

<pre>Using Random Strategy: 0.00%

 

=={{header|Factor}}==

 

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

10,000 [ rand ] simulate "Random play success: "

10,000 [ optimal ] simulate "Optimal play success: "

{{out}}

<pre>

=={{header|FOCAL}}==

 

01.20 F Z=1,2000;D 5;S CU=CU+SU

01.30 T CU/20,!,"OPTIMAL";S CU=0

06.20 I (X-101)6.3,6.4

06.30 D 4;S X=X+1;I (SU),6.4,6.2

 

{{out}}

Run the two strategies (random and follow the card number) 10,000 times each, and show number or successes.

 

 

100 CONSTANT #drawers

 

0 trie . CR \ random strategy

 

output:

 

=={{header|Fortran}}==

! Takes an input array and shuffles the elements by swapping them

! in pairs in turn 10 times

CALL RUN_RANDOM(N_ROUNDS)

CALL RUN_OPTIMAL(N_ROUNDS)

 

output:

 

=={{header|FreeBASIC}}==

 

function gus( i as long, strat as boolean ) as long

trials( c_success, c_fail, true )

 

 

=={{header|Gambas}}==

Implementation of the '100 Prisoners' program written in VBA. Tested in Gambas 3.15.2

 

Public DrawerArray As Long[]

Return FoundOwnNumber

 

{{out}}

Trials/sec: 114.9</pre>

 

 

=={{header|Go}}==

 

import (

}

}

 

{{out}}

=={{header|Groovy}}==

{{trans|Java}}

import java.util.stream.Collectors

import java.util.stream.IntStream

System.out.printf("Random play success rate: %f%%\n", exec(n, p, Prisoners.&playRandom))

}

{{out}}

<pre># of executions: 100000

 

=={{header|Haskell}}==

import Control.Monad.State

 

allM func [] = return True

allM func (x:xs) = func x >>= \res -> if res then allM func xs else return False

{{out}}

<pre>Chance of winning when choosing randomly: 0.0

 

=={{header|J}}==

NB. game is solvable by optimal strategy when the length (#) of the

NB. longest (>./) cycle (C.) is at most 50.

'o r'=. y %~ 100 * +/ ((rand,opt)@?~)"0 y # 100

('strategy';'win rate'),('random';(":o),'%'),:'optimal';(":r),'%'

{{out}}

<pre> simulate 10000000

 

=={{header|Janet}}==

(math/seedrandom (os/cryptorand 8))

 

(printf "Optimal play wins: %.1f%%" (* (/ optimal-success sims) 100))

(printf "Random play wins: %.1f%%" (* (/ random-success sims) 100)))

 

Output:

=={{header|Java}}==

{{trans|Kotlin}}

import java.util.List;

import java.util.Objects;

System.out.printf("Random play success rate: %f%%\n", exec(n, p, Main::playRandom));

}

{{out}}

<pre># of executions: 100000

{{trans|C#}}

{{Works with|Node.js}}

const _ = require('lodash');

 

console.log("Optimal Play Success Rate: " + execOptimal());

console.log("Random Play Success Rate: " + execRandom());

 

===School example===

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

 

 

// Simulate several thousand instances of the game:

function computeProbability(results, gamesCount) {

return Math.round(results.filter(x => x == true).length * 10000 / gamesCount) / 100;

 

Output:

 

jq does not have a built-in PRNG and so the jq program used here presupposes an external source of entropy such as /dev/urandom. The output shown below was obtained by invoking jq as follows:

 

In the following jq program:

 

'''Preliminaries'''

 

# Output: a PRN in range(0;$n) where $n is .

| .a[$j] = $t)

| .a

 

'''np Prisoners'''

def optimalStrategy($drawers; np):

# Does prisoner $p succeed?

;

 

{{out}}

<pre>

=={{header|Julia}}==

{{trans|Python}}

 

function randomplay(n, numprisoners=100)

println("Random play wins: ", format(randomplay(N), precision=8), "% of simulations.")

println("Optimal play wins: ", format(optimalplay(N), precision=8), "% of simulations.")

<pre>

Simulation count: 100000

Random play wins: 0.00000000% of simulations.

Optimal play wins: 31.18100000% of simulations.

</pre>

 

=={{header|Kotlin}}==

val secrets = (0..99).toMutableList()

var ret = true

println("Optimal play success rate: ${exec(N, playOptimal)}%")

println("Random play success rate: ${exec(N, playRandom)}%")

 

{{out}}

=={{header|Lua}}==

{{trans|lang}}

for i = #tbl, 2, -1 do

local j = math.random(i)

end

 

{{out}}

<pre># of executions: 1000000

 

Don"t bother to simulate the random method: each prisoner has a probability p to win with:

 

Since all prisoners' attempts are independent, the probability that they all win is:

 

evalf(%);

 

# 1/1267650600228229401496703205376

 

Even with billions of simulations, chances are we won't find even one successful escape.

Here is a simulation based on this, assuming that the permutation of numbers in boxes is random:

 

nops(select(n->n<=50,a))/nops(a);

evalf(%);

# 31239/100000

 

The probability of success is now better than 30%, which is far better than the random approach.

It can be [https://en.wikipedia.org/wiki/Random_permutation_statistics#One_hundred_prisoners proved] that the probability with the second strategy is in fact:

 

evalf(%);

 

# 21740752665556690246055199895649405434183/69720375229712477164533808935312303556800

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

PlayRandom[n_] :=

Module[{pardoned = 0, sampler, indrawer, found, reveal},

];

PlayRandom[1000]

 

{{out}}

 

=={{header|MATLAB}}==

%numP is the number of prisoners

%numG is the number of guesses

disp(['Probability of success with random strategy: ' num2str(randSuccess*100) '%']);

disp(['Probability of success with ideal strategy: ' num2str(idealSuccess*100) '%']);

{{out}}

<pre>

=={{header|MiniScript}}==

{{trans|Python}}

// using 0-99 instead of 1-100

pardoned = 0

 

print "Random: " + playRandom(10000) + "%"

{{out}}

<pre>Random: 0%

=={{header|Nim}}==

Imperative style.

 

type

randomize()

echo $massDrawings(prisonersWillBeReleasedSmart)

{{out}}

<pre>Succs: 312225 Fails: 687775 Total: 1000000 Success Rate: 31.2225%.

{{works with|Free Pascal}}

searching the longest cycle length as stated on talk page and increment an counter for that cycle length.

 

const

OneCompareRun(20);

OneCompareRun(100);

<pre>

Checking 20 prisoners

Randomly 0.00% get pardoned out of 100000 checking max 0</pre>

=== Alternative for optimized ===

{$IFDEF FPC}

{$MODE DELPHI}{$OPTIMIZATION ON,ALL}

OneCompareRun(100);

OneCompareRun(1000);

{{out}}

<pre "style height=35ex">

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

use feature 'say';

say " Simulation count: $trials\n" .

(sprintf " Random strategy pardons: %6.3f%% of simulations\n", simulation $population, $trials, 'random' ) .

{{out}}

<pre> Simulation count: 10000

Built so you could easily build and test your own strategies.

 

(by '(NIL (rand)) sort Lst) )

 

(inc 'Successes) ) )

(prinl "We have a " (/ (* 100 Successes) N) "% success rate with " N " trials.")

 

Then run

 

{{out}}

 

=={{header|Phix}}==

{{out}}

<pre>

=={{header|Phixmonti}}==

{{trans|Yabasic}}

by Galileo, 05/2022 #/

 

( "Optimal: " 100 10000 true play

" Random: " 100 10000 false play

{{out}}

<pre>Please, be patient ...

 

=={{header|PL/M}}==

/* PARAMETERS */

DECLARE N$DRAWERS LITERALLY '100'; /* AMOUNT OF DRAWERS */

CALL RUN$AND$PRINT(.'OPTIMAL$', OPTIMAL, N$SIMS);

CALL EXIT;

{{out}}

<pre>RANDOM STRATEGY: 0 OUT OF 2000 - 0%

 

=={{header|Pointless}}==

iterate(ind => drawers[ind - 1], n)

|> takeUntil(ind => drawers[ind - 1] == n)

randomCount, numTrials, randomCount / numTrials,

])

 

{{out}}

=={{header|PowerShell}}==

{{trans|Chris}}

### Clear Screen from old Output

Clear-Host

 

Main

 

{{out}}

 

=={{header|Processing}}==

int trials = 100000;

int succes_count;

println(" Succeses: " + succes_count);

print(" Succes rate: " + 100.0 * succes_count / trials + "%");

 

{{out}}

 

=={{header|PureBasic}}==

#DRAWERS =100

#LOOPS = 50

PrintN(~"\tFIN =q.") : inp$=Input()

w1=0 : w2=0

{{out}}

<pre>TRIALS: 10000 RANDOM= 0.00% STATEGY= 30.83% FIN =q.

=={{header|Python}}==

===Procedural===

 

def play_random(n):

print(" Simulation count:", n)

print(f" Random play wins: {play_random(n):4.1f}% of simulations")

 

{{out}}

 

Or, an alternative procedural approach:

 

import random

 

if __name__ == '__main__':

{{Out}}

<pre>With 10 drawers (100k runs)

 

{{Works with|Python|3.7}}

 

from random import randint, sample

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>10000 tests of optimal vs random drawer-sampling with 10 boxes:

 

=={{header|R}}==

success.r = rep(0,t) #this will keep track of how many prisoners find their ticket on each trial for the random method

success.o = rep(0,t) #this will keep track of how many prisoners find their ticket on each trial for the optimal method

 

cat("Random method resulted in a success rate of ",100*mean(success.r==100),

{{Out}}

<pre>Random method resulted in a success rate of 0%.

 

=={{header|QB64}}==

Const Found = -1, Searching = 0, Status = 1, Tries = 2

Const Attempt = 1, Victories = 2, RandomW = 1, ChainW = 2

End Sub

 

 

=={{header|Quackery}}==

 

[ dup size 2 / split ] is halve ( [ --> [ [ )

say "100 smart prisoners were pardoned "

0 10000 times [ 100 prisoners smart + ] echo

 

'''Output:'''

... simulate

...

100 smart prisoners were pardoned 3158 times out of 10000 simulations.

 

 

=={{header|Racket}}==

(require srfi/1)

 

(module+ main

(print-sample-percentage "random" (evaluate-strategy 100-prisoners-problem strategy-1))

 

{{out}}

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.

 

my @prisoners = ^$prisoners;

my $half = floor +@prisoners / 2;

say "Testing $simulations simulations with $prisoners prisoners.";

printf " Random play wins: %.3f%% of simulations\n", random $simulations;

{{out}}

'''With defaults'''

</pre>

=={{header|Red}}==

Red []

 

print ["runs" k_runs newline "Percent saved opt.strategy:" saved * 100.0 / k_runs ]

print ["Percent saved random strategy:" saved_rand * 100.0 / k_runs ]

{{out}}<pre>

runs 100000

 

=={{header|REXX}}==

parse arg men trials seed . /*obtain optional arguments from the CL*/

if men=='' | men=="," then men= 100 /*number of prisoners for this run.*/

end /* [↑] indicate success for prisoner. */

?= @.? /*choose next drawer from current card.*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ruby}}==

N = 10_000

generate_rooms = ->{ [nil]+[*1..100].shuffle }

end

puts "Optimal strategy: %11.4f %%" % (res.fdiv(N) * 100)

{{out}}

<pre>Random strategy : 0.0000 %

 

Cargo.toml

 

src/main.rs

 

use rand::prelude::*;

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

 

 

{{out}}

 

=={{header|Sather}}==

shuffle (a: ARRAY{INT}) is

ARR_PERMUTE_ALG{INT, ARRAY{INT}}::shuffle(a);

try("optimal", 100000, 10, 10, 5, bind(try_optimal(_, _, _)));

end;

{{out}}

<pre>100 prisoners, 100 drawers, 50 tries:

=={{header|Scala}}==

{{trans|Java}}

import scala.util.control.Breaks._

 

printf("Random play success rate: %f%%\n", exec(n, p, playRandom))

}

{{out}}

<pre># of executions: 100,000

Optimal play success rate: 31.201000%

Random play success rate: 0.000000%</pre>

 

=={{header|Swift}}==

 

 

struct PrisonersGame {

}

 

 

{{out}}

=={{header|Tcl}}==

{{trans|Common Lisp}}

set Prisoners 100

set MaxGuesses 50

}

 

 

{{Out}}

{{works with|Transact-SQL|SQL Server 2017}}

 

GO

 

DROP TABLE dbo.drawers;

DROP TABLE dbo.numbers;

 

Output:

Probability of success with "random" strategy: 0.00

Probability of success with "optimal" strategy: 31.00</pre>

 

=={{header|VBA}}/{{header|Visual Basic}}==

 

 

NumberOfPrisoners = Int(InputBox("Number of Prisoners", "Prisoners", 100))

Next Counter

 

{{out}}

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Function PlayOptimal() As Boolean

End Sub

 

{{out}}

<pre># of executions: 1000000

 

=={{header|VBScript}}==

option explicit

const npris=100

next

trystrat=false

Output:

<pre>

</pre>

 

{{trans|Wren}}

import rand.seed

// Uses 0-based numbering rather than 1-based numbering throughout.

}

}

 

{{out}}

{{trans|Go}}

{{libheader|Wren-fmt}}

 

var rand = Random.new()

}

if (!nextPrisoner) {

}

}

Fmt.print("Results from $,d trials with $d prisoners:\n", trials, np)

for (strategy in ["random", "optimal"]) doTrials.call(trials, np, strategy)

 

{{out}}

 

=={{header|XPL0}}==

 

proc KShuffle; \Randomly rearrange the cards in the drawers

Text(0, "Optimal strategy success rate: ");

Strategy(2);

 

{{out}}

=={{header|Yabasic}}==

{{trans|Phix}}

// by Galileo, 05/2022

 

optimal = play(prisoners, iterations, true)

print "Prisoners: ", prisoners, ", random: ", random, ", optimal: ", optimal

{{out}}

<pre>Simulation count: 10000

Prisoners: 100, random: 0, optimal: 31.2

---Program done, press RETURN---</pre>

 

=={{header|zkl}}==

fcn oneHundredJDI{ // just do it strategy

cupboard,picks := [0..SLOTS-1].walk().shuffle(), cupboard.copy();

}

True // all found their number

println("Just do it strategy (%,d simulatations): %.2f%%".fmt(N,s));

 

s:=N.pump(Ref(0).incN,oneHundredO).value.toFloat()/N*100;

{{out}}

<pre>

</pre>

And a sanity check (from the Raku entry):

{{out}}

<pre>