Jump to content

Algorithm Implementation/Simulation/Monty Hall problem

From Wikibooks, open books for an open world
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);
}
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");
    }
}
#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;
	}
}
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!")
 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]

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}%"
 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.


References

[edit | edit source]