Algorithm Implementation/Simulation/Monty Hall problem
PHP
[edit | edit source]class MontyHall {
private $rounds = 10;
private $doors = 3;
private $wins = array( "changing" => 0, "keeping" => 0 );
public function setDoors( $doors )
{
$this->doors = $doors;
return $this;
}
public function play( $rounds = false )
{
if ( $rounds ) $this->rounds = $rounds;
for ( $i = 0; $i < $this->rounds; $i++ ) {
$prizeDoor = $this->randomDoor();
$playerChoiseDoor = $this->randomDoor();
$hostOpenDoor = $this->chooseDoor( $prizeDoor, $playerChoiseDoor );
$playerChangeDoor = $this->chooseDoor( $playerChoiseDoor, $hostOpenDoor );
if( $playerChoiseDoor == $prizeDoor ) $this->wins["keeping"]++;
if( $playerChangeDoor == $prizeDoor ) $this->wins["changing"]++;
}
return $this;
}
public function getResults()
{
echo " Winnings: " . "<br>" .
" - Changing the door: " . ( $this->wins["changing"] * 100 ) / $this->rounds . "%<br>" .
" - Not Changing the door: " . ( $this->wins["keeping"] * 100 ) / $this->rounds . "%<br>" .
" Simulation Statistics: " . "<br>" .
" - Games played: " . $this->rounds . "<br>" .
" - Doors used: " . $this->doors . "<br>" ;
}
private function randomDoor()
{
return rand( 1, $this->doors );
}
private function chooseDoor( $number1 = null, $number2 = null )
{
do $result = $this->randomDoor();
while ( $result == $number1 OR $result == $number2 );
return $result;
}
}
// Use the MontyHall Simulation
$montyhall = new MontyHall();
$montyhall->setDoors(3)->play(10000)->getResults();
Javascript
[edit | edit source]Array.prototype.remove = function(i) {
this.splice(i, 1);
};
SimulationEngine = function(){
}
SimulationEngine.prototype = {
simulate: function(maxSim){
if(!maxSim || maxSim < 0)
maxSim = 1000;
var winSwitching = 0;
var loseSwitching = 0;
var carCard = 0;
var goat = 1;
function userPickOne(cards){
var index = Math.floor(Math.random()*11)%3;
cards.remove(index);
}
function hostDiscardOne(cards){
if(cards[0] === goat)
cards.remove(0);
else
cards.remove(1);
}
function updateStatus(cards){
if(cards[0] === carCard)
winSwitching++;
else
loseSwitching++;
}
for(var sim = 0; sim < maxSim; sim++){
var cards = [carCard,goat,goat];
userPickOne(cards);
hostDiscardOne(cards);
updateStatus(cards);
}
return {
winSwitching: winSwitching,
loseSwitching: loseSwitching
}
}
}
function simulate(){
var maxSim = 10000;
var engine = new SimulationEngine();
var result = engine.simulate(maxSim);
var strResult = "Total simulations are " + maxSim +
", WIN by switching = " + result.winSwitching * 100 / maxSim +
", LOST by switching = " + result.loseSwitching * 100 / maxSim;
alert(strResult);
}
Java
[edit | edit source]import java.util.Random;
public class MontyHall {
public static final Random gen = new Random();
public static final int ROUNDS = 10000;
/** chooses a random door other than door1 or door2 */
private static int chooseAnotherDoor(int door1, int door2) {
int result;
do
result = gen.nextInt(3);
while (result == door1 || result == door2);
return result;
}
public static void main(String[] args) {
System.out.println("begin playing " + ROUNDS + " rounds");
int wins = 0;
for (int i = 0; i < ROUNDS; i++) {
int prize = gen.nextInt(3);
int userChoice1 = gen.nextInt(3);
// host opens door other than user's choice without prize
int hostChoice = chooseAnotherDoor(prize, userChoice1);
// user always switches
int userChoice2 = chooseAnotherDoor(userChoice1, hostChoice);
if (userChoice2 == prize)
wins++;
}
System.out.println(wins + " wins by switching");
}
}
C++
[edit | edit source]#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
srand(time(NULL));
random_device rd;
mt19937 gen{ rd() };
unsigned long long stay = 0;
unsigned long long change = 0;
while(true)
{
vector<bool> boxes(3, false);
boxes[0] = true; // Place a car
shuffle(boxes.begin(), boxes.end(), gen);
if(boxes[rand() % 3])
{
stay++;
cout << "STAY wins\n";
}
else
{
change++;
cout << "CHANGE wins\n";
}
cout << "STAY: " << int((double)stay/(stay + change) * 100 + 0.5) << "%; "
<< "CHANGE: " << int((double)change/(stay + change) * 100 + 0.5) << "%\n" << endl;
}
}
Phix
[edit | edit source]integer swapWins = 0, stayWins = 0, winner, choice, reveal, other
atom t0 = time()
for game=1 to 1_000_000 do
winner = rand(3)
choice = rand(3)
while 1 do
reveal = rand(3)
if reveal!=winner and reveal!=choice then exit end if
end while
stayWins += (choice==winner)
other = 6-choice-reveal -- (as 1+2+3=6, and reveal!=choice)
swapWins += (other==winner)
end for
printf(1, "Stay: %,d\nSwap: %,d\nTime: %3.2fs\n",{stayWins,swapWins,time()-t0})
#!/usr/bin/python
import sys,random
rounds = 10000
wins = 0
random.seed()
# The "-n" commandline option makes us run without ever switching.
if len(sys.argv) > 1 and sys.argv[1] == "-n":
swap = False
else:
swap = True
for i in range(rounds) :
# Generate random door contents
doors = ["goat", "goat", "car"]
random.shuffle(doors)
# Pick a door
door_choice = random.randrange(3)
print("Selecting door", door_choice)
# Show a door with a goat
for j, contents in enumerate(doors):
if j != door_choice and contents == "goat":
goat_door = j
print("The host reveals a goat behind door", goat_door)
break
if swap:
# Swap to the other door
for j, contents in enumerate(doors):
if j != door_choice and j != goat_door:
swap_to = j
print("Swapping to door", swap_to)
else:
swap_to = door_choice
if doors[swap_to] == "car":
wins += 1
print("You won the car!!")
else:
print("Sorry, but you're stuck with a goat")
print("You played", rounds, "rounds, and won", wins, "of them!")
R
[edit | edit source] numsim = 100000
doors = 1:3
opendoor = function(x) {
if (x[1]==x[2])
return(sample(doors[-c(x[1])], 1))
else return(doors[-c(x[1],x[2])])
}
swapdoor = function(x) { return(doors[-c(x[1], x[2])]) }
winner = sample(doors, numsim, replace=TRUE)
choice = sample(doors, numsim, replace=TRUE)
open = apply(cbind(winner, choice), 1, opendoor)
newchoice = apply(cbind(open, choice), 1, swapdoor)
#
cat("without switching, won ",
round(sum(winner==choice)/numsim*100,1),"
percent of the time.\n", sep="")
cat("with switching, won ",
round(sum(winner==newchoice)/numsim*100,1),"
percent of the time.\n", sep="")
[from http://sas-and-r.blogspot.com/search?q=7.23]
Ruby
[edit | edit source]def createDoors
doors = [false, false, false]
doors[rand(3)] = true
doors
end
def openADoorThatHasADonkey(doors, userChoice)
([0, 1, 2] - [userChoice, doors.index(true)]).first
end
def changeUserChoice(choices)
([0, 1, 2] - choices).first
end
def play
doors = createDoors()
userChoice1 = rand(3)
hostChoice = openADoorThatHasADonkey(doors, userChoice1)
userChoice2 = changeUserChoice([userChoice1, hostChoice]) # note: to change
# script so that user DOESN'T change her choice and demonstrate the fallacy
# of that approach, comment the userChoice2 line above and uncomment the
# line below:
# userChoice2 = userChoice1
doors.index(true) == userChoice2
end
games, wins = 10000, 0
games.times { wins += 1 if play() }
print 100*wins/games, " %"
Another implementation
car = wins = 0
many = 100000
many.times do
choice1 = rand(3)
host_opts = [0, 1, 2] - [choice1, car]
choice2 = [0, 1, 2] - [choice1, host_opts.first]
wins += 1 if choice2 == [car]
end
puts "#{(wins * 100) / many}%"
SAS
[edit | edit source] data mh;
do i = 1 to 100000;
prize = rand("TABLE",.333,.333);
* Monty puts the prize behind a random door;
initial_guess = rand("TABLE",.333,.333);
* We make a random initial guess;
* if the initial guess is right, Monte can open either of the others;
* which means that player can switch to either
of the other doors;
if initial_guess eq prize then do;
new_guess = initial_guess;
* choose a door until it's different from the initial guess—that's the door we switch to;
do until (new_guess ne initial_guess);
new_guess = rand("TABLE",.333,.333);
end;
end;
* If the initial guess was wrong, Monte can rule out only one of the other doors;
* which means that we must switch to the right door;
if initial_guess ne prize then new_guess = prize;
output;
end;
run;
*;
data mh2;
set mh;
win_by_keep = (initial_guess eq prize);
win_by_switch = (new_guess eq prize);
run;
*;
proc means data = mh2 mean;
var win_by_keep win_by_switch;
run;
[from http://sas-and-r.blogspot.com/search?q=7.23]
Option Explicit
Option Base 1
Sub simulate()
Dim iCount As Long
Dim wins As Long
Dim games As Long
games = 10000000
For iCount = 1 To games
If Play Then wins = wins + 1
Next
MsgBox Round(((wins / games) * 100), 1) & "%"
End Sub
Function Play()
Dim doors() As Boolean
Dim userChoice1 As Integer
Dim hostchoice As Integer
Dim userChoice2 As Integer
doors = createDoors()
userChoice1 = Int(3 * Rnd() + 1)
hostchoice = openADoorThatHasADonkey(doors(), userChoice1)
userChoice2 = changeUserChoice(userChoice1, hostchoice)
Play = doors(userChoice2)
End Function
Function createDoors() As Boolean()
Dim temp(3) As Boolean
temp(1) = False
temp(2) = False
temp(3) = False
temp(Int(3 * Rnd() + 1)) = True
createDoors = temp
End Function
Function openADoorThatHasADonkey(doors() As Boolean, userChoice)
Dim iCount As Integer
Dim temp As Integer
For iCount = 1 To 3
If Not doors(iCount) And userChoice <> iCount Then
temp = iCount
Exit For
End If
Next iCount
openADoorThatHasADonkey = temp
End Function
Function changeUserChoice(userChoice1 As Integer, hostchoice As Integer)
Dim iCount As Integer
Dim temp As Integer
For iCount = 1 To 3
If userChoice1 <> iCount And hostchoice <> iCount Then temp = iCount
Next iCount
changeUserChoice = temp
End Function
Progress 4GL
[edit | edit source]DEF TEMP-TABLE deur NO-UNDO
FIELD deurnr AS INT
FIELD prijsdeur AS LOG.
DEF VAR iprijsDeur AS INT NO-UNDO.
CREATE deur.
ASSIGN deur.deurnr = 1
deur.prijsdeur = FALSE.
CREATE deur.
ASSIGN deur.deurnr = 2
deur.prijsdeur = FALSE.
CREATE deur.
ASSIGN deur.deurnr = 3
deur.prijsdeur = FALSE.
iPrijsdeur = RANDOM(1,3).
FIND deur WHERE deurnr = iPrijsdeur.
ASSIGN prijsdeur = TRUE.
DEF VAR mijnkeuze AS INT NO-UNDO.
DEF VAR gamehostKeuze AS INT NO-UNDO.
DEF VAR mijnkeuze2 AS INT NO-UNDO.
DEF VAR i AS INT NO-UNDO.
DEF VAR g AS INT NO-UNDO.
DEF VAR v AS INT NO-UNDO.
DO i = 1 TO 100:
mijnkeuze = RANDOM(1,3).
gamehostkeuze = DYNAMIC-FUNCTION("openDeurZonderPrijs").
mijnkeuze2 = DYNAMIC-FUNCTION("wisselDeur").
/*mijnkeuze2 = mijnkeuze.*/
IF mijnkeuze2 = iPrijsdeur
THEN g = g + 1.
ELSE v = v + 1.
END.
MESSAGE "van" i "ronden won je er" g "en verloor je" v "keer".
FUNCTION openDeurZonderPrijs RETURNS INT:
FIND FIRST deur WHERE NOT deurnr EQ iPrijsdeur AND
NOT deurnr EQ mijnkeuze.
RETURN deur.deurnr.
END FUNCTION.
FUNCTION WisselDeur RETURN INT:
FIND deur WHERE NOT deurnr EQ mijnkeuze AND
NOT deurnr EQ gamehostkeuze.
RETURN deur.deurnr.
END FUNCTION.