Monty Hall problem
Run random simulations of the Monty Hall game. Show the effects of a strategy of the contestant always keeping his first guess so it can be contrasted with the strategy of the contestant always switching his guess.
You are encouraged to solve this task according to the task description, using any language you may know.
- Suppose you're on a game show and you're given the choice of three doors. Behind one door is a car; behind the others, goats. The car and the goats were placed randomly behind the doors before the show. The rules of the game show are as follows: After you have chosen a door, the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one randomly. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door. Imagine that you chose Door 1 and the host opens Door 3, which has a goat. He then asks you "Do you want to switch to Door Number 2?" Is it to your advantage to change your choice? (Krauss and Wang 2003:10)
Note that the player may initially choose any of the three doors (not just Door 1), that the host opens a different door revealing a goat (not necessarily Door 3), and that he gives the player a second choice between the two remaining unopened doors.
Simulate at least a thousand games using three doors for each strategy and show the results in such a way as to make it easy to compare the effects of each strategy.
ActionScript
<lang actionscript>package { import flash.display.Sprite;
public class MontyHall extends Sprite { public function MontyHall() { var iterations:int = 30000; var switchWins:int = 0; var stayWins:int = 0;
for (var i:int = 0; i < iterations; i++) { var doors:Array = [0, 0, 0]; doors[Math.floor(Math.random() * 3)] = 1; var choice:int = Math.floor(Math.random() * 3); var shown:int;
do { shown = Math.floor(Math.random() * 3); } while (doors[shown] == 1 || shown == choice);
stayWins += doors[choice]; switchWins += doors[3 - choice - shown]; }
trace("Switching wins " + switchWins + " times. (" + (switchWins / iterations) * 100 + "%)"); trace("Staying wins " + stayWins + " times. (" + (stayWins / iterations) * 100 + "%)"); } } }</lang> Output:
Switching wins 18788 times. (62.626666666666665%) Staying wins 11212 times. (37.37333333333333%)
Ada
<lang ada>-- Monty Hall Game
with Ada.Text_Io; use Ada.Text_Io; with Ada.Float_Text_Io; use Ada.Float_Text_Io; with ada.Numerics.Discrete_Random;
procedure Monty_Stats is
Num_Iterations : Positive := 100000;
type Action_Type is (Stay, Switch);
type Prize_Type is (Goat, Pig, Car);
type Door_Index is range 1..3;
package Random_Prize is new Ada.Numerics.Discrete_Random(Door_Index);
use Random_Prize;
Seed : Generator;
Doors : array(Door_Index) of Prize_Type;
procedure Set_Prizes is
Prize_Index : Door_Index;
Booby_Prize : Prize_Type := Goat;
begin
Reset(Seed);
Prize_Index := Random(Seed);
Doors(Prize_Index) := Car;
for I in Doors'range loop
if I /= Prize_Index then
Doors(I) := Booby_Prize;
Booby_Prize := Prize_Type'Succ(Booby_Prize);
end if;
end loop;
end Set_Prizes;
function Play(Action : Action_Type) return Prize_Type is
Chosen : Door_Index := Random(Seed);
Monty : Door_Index;
begin
Set_Prizes;
for I in Doors'range loop
if I /= Chosen and Doors(I) /= Car then
Monty := I;
end if;
end loop;
if Action = Switch then
for I in Doors'range loop
if I /= Monty and I /= Chosen then
Chosen := I;
exit;
end if;
end loop;
end if;
return Doors(Chosen);
end Play;
Winners : Natural;
Pct : Float;
begin
Winners := 0;
for I in 1..Num_Iterations loop
if Play(Stay) = Car then
Winners := Winners + 1;
end if;
end loop;
Put("Stay : count" & Natural'Image(Winners) & " = ");
Pct := Float(Winners * 100) / Float(Num_Iterations);
Put(Item => Pct, Aft => 2, Exp => 0);
Put_Line("%");
Winners := 0;
for I in 1..Num_Iterations loop
if Play(Switch) = Car then
Winners := Winners + 1;
end if;
end loop;
Put("Switch : count" & Natural'Image(Winners) & " = ");
Pct := Float(Winners * 100) / Float(Num_Iterations);
Put(Item => Pct, Aft => 2, Exp => 0);
Put_Line("%");
end Monty_Stats;</lang> Results
Stay : count 34308 = 34.31% Switch : count 65695 = 65.69%
ALGOL 68
<lang algol68>INT trials=100 000;
PROC brand = (INT n)INT: 1 + ENTIER (n * random);
PROC percent = (REAL x)STRING: fixed(100.0*x/trials,0,2)+"%";
main: (
INT prize, choice, show, not shown, new choice;
INT stay winning:=0, change winning:=0, random winning:=0;
INT doors = 3;
[doors-1]INT other door;
TO trials DO
# put the prize somewhere #
prize := brand(doors);
# let the user choose a door #
choice := brand(doors);
# let us take a list of unchoosen doors #
INT k := LWB other door;
FOR j TO doors DO
IF j/=choice THEN other door[k] := j; k+:=1 FI
OD;
# Monty opens one... #
IF choice = prize THEN
# staying the user will win... Monty opens a random port#
show := other door[ brand(doors - 1) ];
not shown := other door[ (show+1) MOD (doors - 1 ) + 1]
ELSE # no random, Monty can open just one door... #
IF other door[1] = prize THEN
show := other door[2];
not shown := other door[1]
ELSE
show := other door[1];
not shown := other door[2]
FI
FI;
# the user randomly choose one of the two closed doors
(one is his/her previous choice, the second is the
one not shown ) #
other door[1] := choice;
other door[2] := not shown;
new choice := other door[ brand(doors - 1) ];
# now let us count if it takes it or not #
IF choice = prize THEN stay winning+:=1 FI;
IF not shown = prize THEN change winning+:=1 FI;
IF new choice = prize THEN random winning+:=1 FI
OD;
print(("Staying: ", percent(stay winning), new line ));
print(("Changing: ", percent(change winning), new line ));
print(("New random choice: ", percent(random winning), new line ))
)</lang> Sample output:
Staying: 33.62% Changing: 66.38% New random choice: 50.17%
AutoHotkey
<lang ahk>
- NoTrayIcon
- SingleInstance, OFF
- Persistent
SetBatchLines, -1 Iterations = 1000 Loop, %Iterations% {
If Monty_Hall(1)
Correct_Change++
Else
Incorrect_Change++
If Monty_Hall(2)
Correct_Random++
Else
Incorrect_Random++
If Monty_Hall(3)
Correct_Stay++
Else
Incorrect_Stay++
} Percent_Change := floor(Correct_Change / Iterations * 100) Percent_Random := floor(Correct_Random / Iterations * 100) Percent_Stay := floor(Correct_Stay / Iterations * 100) MsgBox,, Monty Hall Problem, These are the results:`r`n`r`nWhen I changed my guess, I got %Correct_Change% of %Iterations% (that's %Incorrect_Change% incorrect). Thats %Percent_Change%`% correct.`r`nWhen I randomly changed my guess, I got %Correct_Random% of %Iterations% (that's %Incorrect_Random% incorrect). Thats %Percent_Random%`% correct.`r`nWhen I stayed with my first guess, I got %Correct_Stay% of %Iterations% (that's %Incorrect_Stay% incorrect). Thats %Percent_Stay%`% correct. ExitApp Monty_Hall(Mode) ;Mode is 1 for change, 2 for random, or 3 for stay {
Random, prize, 1, 3
Random, guess, 1, 3
If (prize = guess && Mode != 3)
While show != 0 && show != guess
Random, show, 1, 3
Else
show := 6 - prize - guess
Random, change_guess, 0, 1
If (Mode = 1 || (change_guess && Mode = 2))
Return, (6 - show - guess) = prize
Else If (Mode = 3 || (!change_guess && Mode = 2))
Return, guess = prize
Else
Return
} </lang>
Sample output:
These are the results: When I changed my guess, I got 762 of 1000 (that's 238 incorrect). Thats 76% correct. When I randomly changed my guess, I got 572 of 1000 (that's 428 incorrect). Thats 57% correct. When I stayed with my first guess, I got 329 of 1000 (that's 671 incorrect). Thats 32% correct.
AWK
<lang awk>#!/bin/gawk -f
- Monty Hall problem
BEGIN { srand() doors = 3 iterations = 10000 # Behind a door: EMPTY = "empty"; PRIZE = "prize" # Algorithm used
KEEP = "keep"; SWITCH="switch"; RAND="random"; #
} function monty_hall( choice, algorithm ) {
# Set up doors
for ( i=0; i<doors; i++ ) {
door[i] = EMPTY }
# One door with prize
door[int(rand()*doors)] = PRIZE
chosen = door[choice] del door[choice]
#if you didn't choose the prize first time around then # that will be the alternative
alternative = (chosen == PRIZE) ? EMPTY : PRIZE
if( algorithm == KEEP) { return chosen } if( algorithm == SWITCH) { return alternative } return rand() <0.5 ? chosen : alternative }
function simulate(algo){ prizecount = 0 for(j=0; j< iterations; j++){ if( monty_hall( int(rand()*doors), algo) == PRIZE) { prizecount ++ } } printf " Algorithm %7s: prize count = %i, = %6.2f%%\n", \ algo, prizecount,prizecount*100/iterations }
BEGIN { print "\nMonty Hall problem simulation:" print doors, "doors,", iterations, "iterations.\n" simulate(KEEP) simulate(SWITCH) simulate(RAND)
}</lang> Sample output: <lang awk>bash$ ./monty_hall.awk
Monty Hall problem simulation: 3 doors, 10000 iterations.
Algorithm keep: prize count = 3411, = 34.11% Algorithm switch: prize count = 6655, = 66.55% Algorithm random: prize count = 4991, = 49.91%
bash$</lang>
BASIC
<lang qbasic>RANDOMIZE TIMER DIM doors(3) '0 is a goat, 1 is a car CLS switchWins = 0 stayWins = 0 FOR plays = 0 TO 32767 winner = INT(RND * 3) + 1 doors(winner) = 1'put a winner in a random door choice = INT(RND * 3) + 1'pick a door, any door DO shown = INT(RND * 3) + 1 'don't show the winner or the choice LOOP WHILE doors(shown) = 1 OR shown = choice stayWins = stayWins + doors(choice) 'if you won by staying, count it switchWins = switchWins + doors(3 - choice - shown) 'could have switched to win doors(winner) = 0 'clear the doors for the next test NEXT plays PRINT "Switching wins"; switchWins; "times." PRINT "Staying wins"; stayWins; "times."</lang> Output:
Switching wins 21805 times. Staying wins 10963 times.
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- define TRIALS 10000
int brand(int n) {
return ( n * ((double)rand()/((double)RAND_MAX + (double)1.0 ) ) );
}
- define PERCENT(X) ( 100.0*((float)(X))/((float)TRIALS) )
int main() {
int prize, choice, show, notshown, newchoice;
int staywinning=0, changewinning=0, randomwinning=0;
int odoor[2];
int i,j,k;
for(i=0; i < TRIALS; i++)
{
/* put the prize somewhere */
prize = brand(3);
/* let the user choose a door */
choice = brand(3);
/* let us take a list of unchoosen doors */
for (j=0, k=0; j<3; j++)
{
if (j!=choice) odoor[k++] = j;
}
/* Monty opens one... */
if ( choice == prize )
{ /* staying the user will win... Monty opens a random
port*/
show = odoor[ brand(2) ];
notshown = odoor[ (show+1)%2 ];
} else { /* no random, Monty can open just one door... */
if ( odoor[0] == prize )
{
show = odoor[1];
notshown = odoor[0];
} else {
show = odoor[0];
notshown = odoor[1];
}
}
/* the user randomly choose one of the two closed doors
(one is his/her previous choice, the second is the
one notshown */
odoor[0] = choice;
odoor[1] = notshown;
newchoice = odoor[ brand(2) ];
/* now let us count if it takes it or not */
if ( choice == prize ) staywinning++;
if ( notshown == prize ) changewinning++;
if ( newchoice == prize ) randomwinning++;
}
printf("Staying: %.2f\n", PERCENT(staywinning) );
printf("Changing: %.2f\n", PERCENT(changewinning) );
printf("New random choice: %.2f\n", PERCENT(randomwinning) );
}</lang>
Output of one run:
Staying: 33.41 Changing: 66.59 New random choice: 49.67
Clojure
<lang clojure>(ns monty-hall-problem
(:use [clojure.contrib.seq :only (shuffle)]))
(defn play-game [staying]
(let [doors (shuffle [:goat :goat :car])
choice (rand-int 3)
[a b] (filter #(not= choice %) (range 3))
alternative (if (= :goat (nth doors a)) b a)]
(= :car (nth doors (if staying choice alternative)))))
(defn simulate [staying times]
(let [wins (reduce (fn [counter _] (if (play-game staying) (inc counter) counter))
0
(range times))]
(str "wins " wins " times out of " times)))
</lang> <lang clojure>monty-hall-problem> (println "staying:" (simulate true 1000)) staying: wins 337 times out of 1000 nil monty-hall-problem> (println "switching:" (simulate false 1000)) switching: wins 638 times out of 1000 nil </lang>
Common Lisp
<lang lisp>(defun make-round ()
(let ((array (make-array 3
:element-type 'bit
:initial-element 0)))
(setf (bit array (random 3)) 1)
array))
(defun show-goat (initial-choice array)
(loop for i = (random 3)
when (and (/= initial-choice i)
(zerop (bit array i)))
return i))
(defun won? (array i)
(= 1 (bit array i)))</lang>
<lang lisp>CL-USER> (progn (loop repeat #1=(expt 10 6)
for round = (make-round)
for initial = (random 3)
for goat = (show-goat initial round)
for choice = (loop for i = (random 3)
when (and (/= i initial)
(/= i goat))
return i)
when (won? round (random 3))
sum 1 into result-stay
when (won? round choice)
sum 1 into result-switch
finally (progn (format t "Stay: ~S%~%" (float (/ result-stay
#1# 1/100)))
(format t "Switch: ~S%~%" (float (/ result-switch
#1# 1/100))))))
Stay: 33.2716% Switch: 66.6593%</lang>
C++
<lang cpp>#include <iostream>
- include <cstdlib>
- include <ctime>
int randint(int n) {
return (1.0*n*std::rand())/(1.0+RAND_MAX);
}
int other(int doorA, int doorB) {
int doorC;
if (doorA == doorB)
{
doorC = randint(2);
if (doorC >= doorA)
++doorC;
}
else
{
for (doorC = 0; doorC == doorA || doorC == doorB; ++doorC)
{
// empty
}
}
return doorC;
}
int check(int games, bool change) {
int win_count = 0;
for (int game = 0; game < games; ++game)
{
int const winning_door = randint(3);
int const original_choice = randint(3);
int open_door = other(original_choice, winning_door);
int const selected_door = change?
other(open_door, original_choice)
: original_choice;
if (selected_door == winning_door)
++win_count;
}
return win_count;
}
int main() {
std::srand(std::time(0));
int games = 10000; int wins_stay = check(games, false); int wins_change = check(games, true); std::cout << "staying: " << 100.0*wins_stay/games << "%, changing: " << 100.0*wins_change/games << "%\n";
}</lang> Sample output:
staying: 33.73%, changing: 66.9%
D
<lang d>import std.stdio, std.random;
void main() {
Random gen = Random(unpredictableSeed); uint switchWins = 0, stayWins = 0;
while(switchWins + stayWins < 100_000) {
uint carPos = dice(gen, 1, 1, 1); // Which door is car behind?
uint pickPos = dice(gen, 1, 1, 1); // Contestant's initial pick.
uint openPos; // Which door is opened by Monty Hall?
// Monty can't open the door you picked or the one with the car
// behind it.
do {
openPos = dice(gen, 1, 1, 1);
} while(openPos == pickPos || openPos == carPos);
uint switchPos = 0;
// Find position that's not currently picked by contestant and was
// not opened by Monty already.
for(; pickPos == switchPos || openPos == switchPos; switchPos++) {}
if(pickPos == carPos) {
stayWins++;
} else if(switchPos == carPos) {
switchWins++;
} else {
assert(0); // Can't happen.
}
}
writefln("Switching wins: %d Staying wins: %d", switchWins, stayWins);
}</lang>
Output:
Switching wins: 66673 Staying wins: 33327
Forth
<lang forth>include random.fs
variable stay-wins variable switch-wins
- trial ( -- )
3 random 3 random ( prize choice ) = if 1 stay-wins +! else 1 switch-wins +! then ;
- trials ( n -- )
0 stay-wins ! 0 switch-wins ! dup 0 do trial loop cr stay-wins @ . [char] / emit dup . ." staying wins" cr switch-wins @ . [char] / emit . ." switching wins" ;
1000 trials</lang>
or in iForth:
<lang forth>0 value stay-wins 0 value switch-wins
- trial ( -- )
3 choose 3 choose ( -- prize choice ) = IF 1 +TO stay-wins exit ENDIF 1 +TO switch-wins ;
- trials ( n -- )
CLEAR stay-wins CLEAR switch-wins dup 0 ?DO trial LOOP CR stay-wins DEC. ." / " dup DEC. ." staying wins," CR switch-wins DEC. ." / " DEC. ." switching wins." ;</lang>
With output:
FORTH> 100000000 trials 33336877 / 100000000 staying wins, 66663123 / 100000000 switching wins. ok
Fortran
<lang fortran>PROGRAM MONTYHALL
IMPLICIT NONE
INTEGER, PARAMETER :: trials = 10000 INTEGER :: i, choice, prize, remaining, show, staycount = 0, switchcount = 0 LOGICAL :: door(3) REAL :: rnum
CALL RANDOM_SEED
DO i = 1, trials
door = .FALSE.
CALL RANDOM_NUMBER(rnum)
prize = INT(3*rnum) + 1
door(prize) = .TRUE. ! place car behind random door
CALL RANDOM_NUMBER(rnum)
choice = INT(3*rnum) + 1 ! choose a door
DO
CALL RANDOM_NUMBER(rnum)
show = INT(3*rnum) + 1
IF (show /= choice .AND. show /= prize) EXIT ! Reveal a goat
END DO
SELECT CASE(choice+show) ! Calculate remaining door index
CASE(3)
remaining = 3
CASE(4)
remaining = 2
CASE(5)
remaining = 1
END SELECT
IF (door(choice)) THEN ! You win by staying with your original choice
staycount = staycount + 1
ELSE IF (door(remaining)) THEN ! You win by switching to other door
switchcount = switchcount + 1
END IF
END DO
WRITE(*, "(A,F6.2,A)") "Chance of winning by not switching is", real(staycount)/trials*100, "%" WRITE(*, "(A,F6.2,A)") "Chance of winning by switching is", real(switchcount)/trials*100, "%"
END PROGRAM MONTYHALL</lang> Sample Output
Chance of winning by not switching is 32.82% Chance of winning by switching is 67.18%
F#
I don't bother with having Monty "pick" a door, since you only win if you initially pick a loser in the switch strategy and you only win if you initially pick a winner in the stay strategy so there doesn't seem to be much sense in playing around the background having Monty "pick" doors. Makes it pretty simple to see why it's always good to switch. <lang fsharp>open System let monty nSims =
let rnd = new Random()
let SwitchGame() =
let winner, pick = rnd.Next(0,3), rnd.Next(0,3)
if winner <> pick then 1 else 0
let StayGame() =
let winner, pick = rnd.Next(0,3), rnd.Next(0,3)
if winner = pick then 1 else 0
let Wins (f:unit -> int) = seq {for i in [1..nSims] -> f()} |> Seq.sum
printfn "Stay: %d wins out of %d - Switch: %d wins out of %d" (Wins StayGame) nSims (Wins SwitchGame) nSims</lang>
I had a very polite suggestion that I simulate Monty's "pick" so I'm putting in a version that does that. I compare the outcome with my original outcome and, unsurprisingly, show that this is essentially a noop that has no bearing on the output, but I (kind of) get where the request is coming from so here's that version... <lang fsharp>let montySlower nSims =
let rnd = new Random()
let MontyPick winner pick =
if pick = winner then
[0..2] |> Seq.filter (fun i -> i <> pick) |> Seq.nth (rnd.Next(0,2))
else
3 - pick - winner
let SwitchGame() =
let winner, pick = rnd.Next(0,3), rnd.Next(0,3)
let monty = MontyPick winner pick
let pickFinal = 3 - monty - pick
// Show that Monty's pick has no effect...
if (winner <> pick) <> (pickFinal = winner) then
printfn "Monty's selection actually had an effect!"
if pickFinal = winner then 1 else 0
let StayGame() =
let winner, pick = rnd.Next(0,3), rnd.Next(0,3)
let monty = MontyPick winner pick
// This one's even more obvious than the above since pickFinal
// is precisely the same as pick
let pickFinal = pick
if (winner = pick) <> (winner = pickFinal) then
printfn "Monty's selection actually had an effect!"
if winner = pickFinal then 1 else 0
let Wins (f:unit -> int) = seq {for i in [1..nSims] -> f()} |> Seq.sum
printfn "Stay: %d wins out of %d - Switch: %d wins out of %d" (Wins StayGame) nSims (Wins SwitchGame) nSims</lang>
Haskell
<lang haskell>import System.Random (StdGen, getStdGen, randomR)
trials :: Int trials = 10000
data Door = Car | Goat deriving Eq
play :: Bool -> StdGen -> (Door, StdGen) play switch g = (prize, new_g)
where (n, new_g) = randomR (0, 2) g
d1 = [Car, Goat, Goat] !! n
prize = case switch of
False -> d1
True -> case d1 of
Car -> Goat
Goat -> Car
cars :: Int -> Bool -> StdGen -> (Int, StdGen) cars n switch g = f n (0, g)
where f 0 (cs, g) = (cs, g)
f n (cs, g) = f (n - 1) (cs + result, new_g)
where result = case prize of Car -> 1; Goat -> 0
(prize, new_g) = play switch g
main = do
g <- getStdGen
let (switch, g2) = cars trials True g
(stay, _) = cars trials False g2
putStrLn $ msg "switch" switch
putStrLn $ msg "stay" stay
where msg strat n = "The " ++ strat ++ " strategy succeeds " ++
percent n ++ "% of the time."
percent n = show $ round $
100 * (fromIntegral n) / (fromIntegral trials)</lang>
With a State monad, we can avoid having to explicitly pass around the StdGen so often. play and cars can be rewritten as follows:
<lang haskell>import Control.Monad.State
play :: Bool -> State StdGen Door play switch = do
i <- rand
let d1 = [Car, Goat, Goat] !! i
return $ case switch of
False -> d1
True -> case d1 of
Car -> Goat
Goat -> Car
where rand = do
g <- get
let (v, new_g) = randomR (0, 2) g
put new_g
return v
cars :: Int -> Bool -> StdGen -> (Int, StdGen) cars n switch g = (numcars, new_g)
where numcars = length $ filter (== Car) prize_list
(prize_list, new_g) = runState (replicateM n (play switch)) g</lang>
Sample output (for either implementation): <lang haskell>The switch strategy succeeds 67% of the time. The stay strategy succeeds 34% of the time.</lang>
HicEst
<lang hicest>REAL :: ndoors=3, doors(ndoors), plays=1E4
DLG(NameEdit = plays, DNum=1, Button='Go')
switchWins = 0 stayWins = 0
DO play = 1, plays
doors = 0 ! clear the doors winner = 1 + INT(RAN(ndoors)) ! door that has the prize doors(winner) = 1 guess = 1 + INT(RAN(doors)) ! player chooses his door
IF( guess == winner ) THEN ! Monty decides which door to open:
show = 1 + INT(RAN(2)) ! select 1st or 2nd goat-door
checked = 0
DO check = 1, ndoors
checked = checked + (doors(check) == 0)
IF(checked == show) open = check
ENDDO
ELSE
open = (1+2+3) - winner - guess
ENDIF
new_guess_if_switch = (1+2+3) - guess - open
stayWins = stayWins + doors(guess) ! count if guess was correct switchWins = switchWins + doors(new_guess_if_switch)
ENDDO
WRITE(ClipBoard, Name) plays, switchWins, stayWins
END</lang> <lang hicest>! plays=1E3; switchWins=695; stayWins=305; ! plays=1E4; switchWins=6673; stayWins=3327; ! plays=1E5; switchWins=66811; stayWins=33189; ! plays=1E6; switchWins=667167; stayWins=332833;</lang>
J
<lang j>NB. Monty Hall Simulation (a tacit version)
'SIZE CAR STAY MONTY SWITCH DOORS ALL'=. i.7 NB. Setting mnemonics for boxes f=. &({::) NB. Fetching the contents of a box o=. @: NB. Composing verbs (functions)
pick=. (? @ #) { ] NB. Picking randomly an element from a vector freq=. +/ % # PickDoors=. (SIZE f ?@$ DOORS f) NB. Picking doors randomly
boxes=. < , a: $~ 6: NB. Appending 6 (empty) boxes to the input
doors=. < o 3: DOORS} ] NB. 3 doors car=. < o PickDoors CAR} ] NB. Randomizing car door positions stay=. < o PickDoors STAY} ] NB. Randomizing stay door selections all=. < o (i. o (DOORS f)) ALL} ] NB. All doors set Monty=. < o ((pick&>) o (ALL f (< @ -.)"1 (CAR f ,"0 STAY f))) MONTY } ]
NB. Calculating Monty's selections
switch=. < o (, o ((ALL f) -."1 (MONTY f) ,"0 (STAY f))) SWITCH } ]
NB. Calculating switching selections
StayDisplay=. 'Stay: ' , ": o (CAR f freq o = STAY f) SwitchDisplay=. 'Switch: ' , ": o (CAR f freq o = SWITCH f)
sim=. (StayDisplay ; SwitchDisplay) o switch o Monty o all o stay o car o doors o boxes f.</lang> Example: <lang j> sim 1000000 +--------------+----------------+ |Stay: 0.333143|Switch: 0.666857| +--------------+----------------+</lang>
Java
<lang java>import java.util.Random; public class Monty{ public static void main(String[] args){ int switchWins = 0; int stayWins = 0; Random gen = new Random(); for(int plays = 0;plays < 32768;plays++ ){ int[] doors = {0,0,0};//0 is a goat, 1 is a car doors[gen.nextInt(3)] = 1;//put a winner in a random door int choice = gen.nextInt(3); //pick a door, any door int shown; //the shown door do{ shown = gen.nextInt(3); //don't show the winner or the choice }while(doors[shown] == 1 || shown == choice);
stayWins += doors[choice];//if you won by staying, count it
//the switched (last remaining) door is (3 - choice - shown), because 0+1+2=3 switchWins += doors[3 - choice - shown]; } System.out.println("Switching wins " + switchWins + " times."); System.out.println("Staying wins " + stayWins + " times."); } }</lang> Output:
Switching wins 21924 times. Staying wins 10844 times.
Lua
<lang lua>function playgame(player)
local car = math.random(3)
local pchoice = player.choice()
local function neither(a, b) --slow, but it works
local el = math.random(3)
return (el ~= a and el ~= b) and el or neither(a, b)
end
local el = neither(car, pchoice)
if(player.switch) then pchoice = neither(pchoice, el) end
player.wins = player.wins + (pchoice == car and 1 or 0)
end for _, v in ipairs{true, false} do
player = {choice = function() return math.random(3) end,
wins = 0, switch = v}
for i = 1, 20000 do playgame(player) end
print(player.wins)
end</lang>
MAXScript
<lang maxscript>fn montyHall choice switch = (
doors = #(false, false, false) doors[random 1 3] = true chosen = doors[choice] if switch then chosen = not chosen chosen
)
fn iterate iterations switched = (
wins = 0
for i in 1 to iterations do
(
if (montyHall (random 1 3) switched) then
(
wins += 1
)
)
wins * 100 / iterations as float
)
iterations = 10000 format ("Stay strategy:%\%\n") (iterate iterations false) format ("Switch strategy:%\%\n") (iterate iterations true)</lang> Output: <lang maxscript>Stay strategy:33.77% Switch strategy:66.84%</lang>
OCaml
<lang ocaml>let trials = 10000
type door = Car | Goat
let play switch =
let n = Random.int 3 in
let d1 = [|Car; Goat; Goat|].(n) in
if not switch then d1
else match d1 with
Car -> Goat
| Goat -> Car
let cars n switch =
let total = ref 0 in
for i = 1 to n do
let prize = play switch in
if prize = Car then
incr total
done;
!total
let () =
let switch = cars trials true
and stay = cars trials false in
let msg strat n =
Printf.printf "The %s strategy succeeds %f%% of the time.\n"
strat (100. *. (float n /. float trials)) in
msg "switch" switch;
msg "stay" stay</lang>
Perl
<lang perl>#! /usr/bin/perl use strict; my $trials = 10000;
my $stay = 0; my $switch = 0;
foreach (1 .. $trials) {
my $prize = int(rand 3);
# let monty randomly choose a door where he puts the prize
my $chosen = int(rand 3);
# let us randomly choose a door...
my $show;
do { $show = int(rand 3) } while $show == $chosen || $show == $prize;
# ^ monty opens a door which is not the one with the
# prize, that he knows it is the one the player chosen
$stay++ if $prize == $chosen;
# ^ if player chose the correct door, player wins only if he stays
$switch++ if $prize == 3 - $chosen - $show;
# ^ if player switches, the door he picks is (3 - $chosen - $show),
# because 0+1+2=3, and he picks the only remaining door that is
# neither $chosen nor $show
}
print "Stay win ratio " . (100.0 * $stay/$trials) . "\n"; print "Switch win ratio " . (100.0 * $switch/$trials) . "\n";</lang>
Perl 6
This implementation is parametric over the number of doors. Increasing the number of doors in play makes the superiority of the switch strategy even more obvious.
<lang perl6>sub remove (@a is rw, Int $i) {
my $temp = @a[$i]; @a = @a[0 ..^ $i], @a[$i ^..^ @a]; return $temp;
}
enum Prize <Car Goat>; enum Strategy <Stay Switch>;
sub play (Strategy $strategy, Int :$doors = 3) returns Prize {
# Call the door with a car behind it door 0. Number the
# remaining doors starting from 1.
my Prize @doors = Car, Goat xx $doors - 1;
# The player chooses a door.
my Prize $initial_pick = remove @doors, @doors.keys().pick;
# Of the n doors remaining, the host chooses n - 1 that have
# goats behind them and opens them, removing them from play.
remove @doors, $_
for pick @doors.elems - 1, grep { @doors[$_] == Goat }, keys @doors;
# If the player stays, they get their initial pick. Otherwise,
# they get whatever's behind the remaining door.
return $strategy == Stay ?? $initial_pick !! @doors[0];
}
constant TRIALS = 100;
for 3, 10 -> $doors {
my %wins;
say "With $doors doors: ";
for Stay, 'Staying', Switch, 'Switching' -> $s, $name {
for ^TRIALS {
++%wins{$s} if play($s, doors => $doors) == Car;
}
say " $name wins ",
round(100*%wins{$s} / TRIALS),
'% of the time.'
}
}</lang>
Sample output:
With 3 doors: Staying wins 34% of the time. Switching wins 64% of the time. With 10 doors: Staying wins 14% of the time. Switching wins 94% of the time.
A hundred trials generally isn't enough to get good numbers, but as of release #22, Rakudo is quite slow and may segfault while executing a long-running program.
PHP
<lang php><?php function montyhall($iterations){ $switch_win = 0; $stay_win = 0;
foreach (range(1, $iterations) as $i){ $doors = array(0, 0, 0); $doors[array_rand($doors)] = 1; $choice = array_rand($doors); do { $shown = array_rand($doors); } while($shown == $choice || $doors[$shown] == 1);
$stay_win += $doors[$choice]; $switch_win += $doors[3 - $choice - $shown]; }
$stay_percentages = ($stay_win/$iterations)*100; $switch_percentages = ($switch_win/$iterations)*100;
echo "Iterations: {$iterations} - "; echo "Stayed wins: {$stay_win} ({$stay_percentages}%) - "; echo "Switched wins: {$switch_win} ({$switch_percentages}%)"; }
montyhall(10000);
?></lang> Output:
Iterations: 10000 - Stayed wins: 3331 (33.31%) - Switched wins: 6669 (66.69%)
PureBasic
<lang PureBasic>Structure wins
stay.i redecide.i
EndStructure
- goat = 0
- car = 1
Procedure MontyHall(*results.wins)
Dim Doors(2) Doors(Random(2)) = #car
player = Random(2)
Select Doors(player)
Case #car
*results\redecide + #goat
*results\stay + #car
Case #goat
*results\redecide + #car
*results\stay + #goat
EndSelect
EndProcedure
OpenConsole()
- Tries = 1000000
Define results.wins
For i = 1 To #Tries
MontyHall(@results)
Next
PrintN("Trial runs for each option: " + Str(#Tries)) PrintN("Wins when redeciding: " + Str(results\redecide) + " (" + StrD(results\redecide / #Tries * 100, 2) + "% chance)") PrintN("Wins when sticking: " + Str(results\stay) + " (" + StrD(results\stay / #Tries * 100, 2) + "% chance)") Input()</lang>
Output:
Trial runs for each option: 1000000 Wins when redeciding: 666459 (66.65% chance) Wins when sticking: 333541 (33.35% chance)
Python
<lang python> I could understand the explanation of the Monty Hall problem but needed some more evidence
References:
http://www.bbc.co.uk/dna/h2g2/A1054306 http://en.wikipedia.org/wiki/Monty_Hall_problem especially: http://en.wikipedia.org/wiki/Monty_Hall_problem#Increasing_the_number_of_doors
from random import randrange
doors, iterations = 3,100000 # could try 100,1000
def monty_hall(choice, switch=False, doorCount=doors):
# Set up doors door = [False]*doorCount # One door with prize door[randrange(doorCount)] = True
chosen = door[choice]
unpicked = door del unpicked[choice]
# Out of those unpicked, the alternative is either: # the prize door, or # an empty door if the initial choice is actually the prize. alternative = True in unpicked
if switch: return alternative else: return chosen
print "\nMonty Hall problem simulation:" print doors, "doors,", iterations, "iterations.\n"
print "Not switching allows you to win", print sum(monty_hall(randrange(3), switch=False)
for x in range(iterations)),
print "out of", iterations, "times." print "Switching allows you to win", print sum(monty_hall(randrange(3), switch=True)
for x in range(iterations)),
print "out of", iterations, "times.\n"</lang> Sample output:
Monty Hall problem simulation: 3 doors, 100000 iterations. Not switching allows you to win 33337 out of 100000 times. Switching allows you to win 66529 out of 100000 times.
R
<lang r># Since R is a vector based language that penalizes for loops, we will avoid
- for-loops, instead using "apply" statement variants (like "map" in other
- functional languages).
set.seed(19771025) # set the seed to set the same results as this code N <- 10000 # trials true_answers <- sample(1:3, N, replace=TRUE)
- We can assme that the contestant always choose door 1 without any loss of
- generality, by equivalence. That is, we can always relabel the doors
- to make the user-chosen door into door 1.
- Thus, the host opens door '2' unless door 2 has the prize, in which case
- the host opens door 3.
host_opens <- 2 + (true_answers == 2) other_door <- 2 + (true_answers != 2)
- if always switch
summary( other_door == true_answers )
- if we never switch
summary( true_answers == 1)
- if we randomly switch
random_switch <- other_door random_switch[runif(N) >= .5] <- 1 summary(random_switch == true_answers)
- To go with the exact parameters of the Rosetta challenge, complicating matters....
- Note that the player may initially choose any of the three doors (not just Door 1),
- that the host opens a different door revealing a goat (not necessarily Door 3), and
- that he gives the player a second choice between the two remaining unopened doors.
N <- 10000 #trials true_answers <- sample(1:3, N, replace=TRUE) user_choice <- sample(1:3, N, replace=TRUE)
- the host_choice is more complicated
host_chooser <- function(user_prize) {
# this could be cleaner
bad_choices <- unique(user_prize)
# in R, the x[-vector] form implies, choose the indices in x not in vector
choices <- c(1:3)[-bad_choices]
# if the first arg to sample is an int, it treats it as the number of choices
if (length(choices) == 1) { return(choices)}
else { return(sample(choices,1))}
}
host_choice <- apply( X=cbind(true_answers,user_choice), FUN=host_chooser,MARGIN=1) not_door <- function(x){ return( (1:3)[-x]) } # we could also define this
# directly at the FUN argument following
other_door <- apply( X = cbind(user_choice,host_choice), FUN=not_door, MARGIN=1)
- if always switch
summary( other_door == true_answers )
- if we never switch
summary( true_answers == user_choice)
- if we randomly switch
random_switch <- user_choice change <- runif(N) >= .5 random_switch[change] <- other_door[change] summary(random_switch == true_answers)</lang>
Results: > ## if always switch > summary( other_door == true_answers ) Mode FALSE TRUE logical 3298 6702 > ## if we never switch > summary( true_answers == 1) Mode FALSE TRUE logical 6702 3298 > ## if we randomly switch > summary(random_switch == true_answers) Mode FALSE TRUE logical 5028 4972 > ## if always switch > summary( other_door == true_answers ) Mode FALSE TRUE logical 3295 6705 > ## if we never switch > summary( true_answers == user_choice) Mode FALSE TRUE logical 6705 3295 > ## if we randomly switch > summary(random_switch == true_answers) Mode FALSE TRUE logical 4986 5014
Ruby
<lang ruby>n = 10_000 #number of times to play
stay = switch = 0 #sum of each strategy's wins
n.times do #play the game n times
#the doors reveal 2 goats and a car doors = [ :goat , :goat , :goat ] doors[rand(3)] = :car #random guess guess = rand(3) #random door shown, but it is neither the guess nor the car begin shown = rand(3) end while shown == guess || doors[shown] == :car #staying with the initial guess wins if the initial guess is the car stay += 1 if doors[guess] == :car #switching guesses wins if the unshown door is the car switch += 1 if doors[3-guess-shown] == :car
end
puts "Staying wins %.2f%% of the time." % (100.0 * stay / n) puts "Switching wins %.2f%% of the time." % (100.0 * switch / n)</lang> Sample Output:
Staying wins 33.84% of the time. Switching wins 66.16% of the time.
Scala
<lang scala>import scala.util.Random
object MontyHallSimulation {
def main(args: Array[String]) {
val samples = if (args.size == 1 && (args(0) matches "\\d+")) args(0).toInt else 1000
val doors = Set(0, 1, 2)
var stayStrategyWins = 0
var switchStrategyWins = 0
1 to samples foreach { _ =>
val prizeDoor = Random shuffle doors head;
val choosenDoor = Random shuffle doors head;
val hostDoor = Random shuffle (doors - choosenDoor - prizeDoor) head;
val switchDoor = doors - choosenDoor - hostDoor head;
(choosenDoor, switchDoor) match {
case (`prizeDoor`, _) => stayStrategyWins += 1
case (_, `prizeDoor`) => switchStrategyWins += 1
}
}
def percent(n: Int) = n * 100 / samples
val report = """|%d simulations were ran.
|Staying won %d times (%d %%)
|Switching won %d times (%d %%)""".stripMargin
println(report
format (samples,
stayStrategyWins, percent(stayStrategyWins),
switchStrategyWins, percent(switchStrategyWins)))
}
}</lang>
Sample:
1000 simulations were ran. Staying won 333 times (33 %) Switching won 667 times (66 %)
Scheme
<lang scheme>(define (random-from-list list) (list-ref list (random (length list)))) (define (random-permutation list)
(if (null? list)
'()
(let* ((car (random-from-list list))
(cdr (random-permutation (remove car list))))
(cons car cdr))))
(define (random-configuration) (random-permutation '(goat goat car))) (define (random-door) (random-from-list '(0 1 2)))
(define (trial strategy)
(define (door-with-goat-other-than door strategy)
(cond ((and (not (= 0 door)) (equal? (list-ref strategy 0) 'goat)) 0)
((and (not (= 1 door)) (equal? (list-ref strategy 1) 'goat)) 1)
((and (not (= 2 door)) (equal? (list-ref strategy 2) 'goat)) 2)))
(let* ((configuration (random-configuration))
(players-first-guess (strategy `(would-you-please-pick-a-door?)))
(door-to-show-player (door-with-goat-other-than players-first-guess
configuration))
(players-final-guess (strategy `(there-is-a-goat-at/would-you-like-to-move?
,players-first-guess
,door-to-show-player))))
(if (equal? (list-ref configuration players-final-guess) 'car)
'you-win!
'you-lost)))
(define (stay-strategy message)
(case (car message)
((would-you-please-pick-a-door?) (random-door))
((there-is-a-goat-at/would-you-like-to-move?)
(let ((first-choice (cadr message)))
first-choice))))
(define (switch-strategy message)
(case (car message)
((would-you-please-pick-a-door?) (random-door))
((there-is-a-goat-at/would-you-like-to-move?)
(let ((first-choice (cadr message))
(shown-goat (caddr message)))
(car (remove first-choice (remove shown-goat '(0 1 2))))))))
(define-syntax repeat
(syntax-rules ()
((repeat <n> <body> ...)
(let loop ((i <n>))
(if (zero? i)
'()
(cons ((lambda () <body> ...))
(loop (- i 1))))))))
(define (count element list)
(if (null? list)
0
(if (equal? element (car list))
(+ 1 (count element (cdr list)))
(count element (cdr list)))))
(define (prepare-result strategy results)
`(,strategy won with probability
,(exact->inexact (* 100 (/ (count 'you-win! results) (length results)))) %))
(define (compare-strategies times)
(append (prepare-result 'stay-strategy (repeat times (trial stay-strategy))) '(and) (prepare-result 'switch-strategy (repeat times (trial switch-strategy)))))
- > (compare-strategies 1000000)
- (stay-strategy won with probability 33.3638 %
- and switch-strategy won with probability 66.716 %)</lang>
Tcl
A simple way of dealing with this one, based on knowledge of the underlying probabilistic system, is to use code like this: <lang tcl>set stay 0; set change 0; set total 10000 for {set i 0} {$i<$total} {incr i} {
if {int(rand()*3) == int(rand()*3)} {
incr stay
} else {
incr change
}
} puts "Estimate: $stay/$total wins for staying strategy" puts "Estimate: $change/$total wins for changing strategy"</lang> But that's not really the point of this challenge; it should add the concealing factors too so that we're simulating not just the solution to the game, but also the game itself. (Note that we are using Tcl's lists here to simulate sets.)
We include a third strategy that is proposed by some people (who haven't thought much about it) for this game: just picking at random between all the doors offered by Monty the second time round. <lang tcl>package require Tcl 8.5
- Utility: pick a random item from a list
proc pick list {
lindex $list [expr {int(rand()*[llength $list])}]
}
- Utility: remove an item from a list if it is there
proc remove {list item} {
set idx [lsearch -exact $list $item] return [lreplace $list $idx $idx]
}
- Codify how Monty will present the new set of doors to choose between
proc MontyHallAction {doors car picked} {
set unpicked [remove $doors $picked]
if {$car in $unpicked} {
# Remove a random unpicked door without the car behind it
set carless [remove $unpicked $car]
return [list {*}[remove $carless [pick $carless]] $car]
# Expressed this way so Monty Hall isn't theoretically
# restricted to using 3 doors, though that could be written
# as just: return [list $car]
} else {
# Monty has a real choice now...
return [remove $unpicked [pick $unpicked]]
}
}
- The different strategies you might choose
proc Strategy:Stay {originalPick otherChoices} {
return $originalPick
} proc Strategy:Change {originalPick otherChoices} {
return [pick $otherChoices]
} proc Strategy:PickAnew {originalPick otherChoices} {
return [pick [list $originalPick {*}$otherChoices]]
}
- Codify one round of the game
proc MontyHallGameRound {doors strategy winCounter} {
upvar 1 $winCounter wins
set car [pick $doors]
set picked [pick $doors]
set newDoors [MontyHallAction $doors $car $picked]
set picked [$strategy $picked $newDoors]
# Check for win...
if {$car eq $picked} {
incr wins
}
}
- We're always using three doors
set threeDoors {a b c} set stay 0; set change 0; set anew 0 set total 10000
- Simulate each of the different strategies
for {set i 0} {$i<$total} {incr i} {
MontyHallGameRound $threeDoors Strategy:Stay stay MontyHallGameRound $threeDoors Strategy:Change change MontyHallGameRound $threeDoors Strategy:PickAnew anew
}
- Print the results
puts "Estimate: $stay/$total wins for 'staying' strategy" puts "Estimate: $change/$total wins for 'changing' strategy" puts "Estimate: $anew/$total wins for 'picking anew' strategy"</lang> This might then produce output like
Estimate: 3340/10000 wins for 'staying' strategy Estimate: 6733/10000 wins for 'changing' strategy Estimate: 4960/10000 wins for 'picking anew' strategy
Of course, this challenge could also be tackled by putting up a GUI and letting the user be the source of the randomness. But that's moving away from the letter of the challenge and takes a lot of effort anyway...
Ursala
This is the same algorithm as the Perl solution. Generate two lists of 10000 uniformly distributed samples from {1,2,3}, count each match as a win for the staying strategy, and count each non-match as a win for the switching strategy.
<lang Ursala>#import std
- import nat
- import flo
rounds = 10000
car_locations = arc{1,2,3}* iota rounds initial_choices = arc{1,2,3}* iota rounds
staying_wins = length (filter ==) zip(car_locations,initial_choices) switching_wins = length (filter ~=) zip(car_locations,initial_choices)
format = printf/'%0.2f'+ (times\100.+ div+ float~~)\rounds
- show+
main = ~&plrTS/<'stay: ','switch: '> format* <staying_wins,switching_wins></lang> Output will vary slightly for each run due to randomness.
stay: 33.95 switch: 66.05
Vedit macro language
Vedit macro language does not have random number generator, so one is implemented in subroutine RANDOM (the algorithm was taken from ANSI C library). <lang vedit>#90 = Time_Tick // seed for random number generator
- 91 = 3 // random numbers in range 0 to 2
- 1 = 0 // wins for "always stay" strategy
- 2 = 0 // wins for "always switch" strategy
for (#10 = 0; #10 < 10000; #10++) { // 10,000 iterations
Call("RANDOM")
#3 = Return_Value // #3 = winning door
Call("RANDOM")
#4 = Return_Value // #4 = players choice
do {
Call("RANDOM") #5 = Return_Value // #5 = door to open
} while (#5 == #3 || #5 == #4)
if (#3 == #4) { // original choice was correct
#1++
}
if (#3 == 3 - #4 - #5) { // switched choice was correct
#2++
}
} Ins_Text("Staying wins: ") Num_Ins(#1) Ins_Text("Switching wins: ") Num_Ins(#2) return
//-------------------------------------------------------------- // Generate random numbers in range 0 <= Return_Value < #91 // #90 = Seed (0 to 0x7fffffff) // #91 = Scaling (0 to 0xffff)
- RANDOM:
- 92 = 0x7fffffff / 48271
- 93 = 0x7fffffff % 48271
- 90 = (48271 * (#90 % #92) - #93 * (#90 / #92)) & 0x7fffffff
return ((#90 & 0xffff) * #91 / 0x10000)</lang>
Sample output:
Staying winns: 3354 Switching winns: 6646
C#
<lang C sharp> using System;
namespace MontyHallProblem {
class Program
{
static void Main(string[] args)
{
int switchWins = 0;
int stayWins = 0;
Random gen = new Random();
for(int plays = 0; plays < 1000000; plays++ )
{
int[] doors = {0,0,0};//0 is a goat, 1 is a car
var winner = gen.Next(3);
doors[winner] = 1; //put a winner in a random door
int choice = gen.Next(3); //pick a door, any door int shown; //the shown door do
{
shown = gen.Next(3); }
while(doors[shown] == 1 || shown == choice); //don't show the winner or the choice
stayWins += doors[choice];//if you won by staying, count it
//the switched (last remaining) door is (3 - choice - shown), because 0+1+2=3 switchWins += doors[3 - choice - shown]; }
System.Console.Out.Write("Switching wins " + switchWins + " times.");
System.Console.Out.Write("Staying wins " + stayWins + " times.");
}
}
} </lang>
Sample output:
Staying winns: 333830 Switching winns: 666170