Let’s Make A Deal!

July 24, 2009

Let’s Make A Deal! was a television game show that originated in the United States in the 1960s and has since been produced throughout the world. In one of the games, prizes were placed behind three doors, and the contestant was asked to pick a door; one door hid an automobile, the other two doors hid goats. Then the host, who knows what is behind the doors, opened one of the doors that the contestant did not pick, revealing in every case a goat, and asks if you want to switch doors. Is it to your advantage to switch your choice of doors?

Your task is to write a program that simulates a large number of games and determines whether or not it is to your advantage to switch doors. What are the odds that you will win the automobile by switching? When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
8 Comments »

8 Responses to “Let’s Make A Deal!”

  1. cwbowron said
    July 24, 2009 at 1:25 PM 
    #lang scheme

(define DOOR-COUNT 3)

(define (car? n lst) (eq? (list-ref lst n) 'car))

(define (get-door-layout n)
  (let loop ([n n] [doors (list)])
    (cond
      [(= 0 n) doors]
      [(or (member 'car doors)
           (not (= 0 (random n))))
       (loop (sub1 n) (cons 'goat doors))]
      [else
       (loop (sub1 n) (cons 'car doors))])))

(define (get-random-door door-count criteria-function)
  (let ([door (random door-count)])
    (if (criteria-function door)
        door
        (get-random-door door-count criteria-function))))

(define (get-revealed-door doors contestant-selection)
  (get-random-door (length doors)
                   (lambda (n)
                     (and (not (= n contestant-selection))
                          (eq? (list-ref doors n) 'goat)))))

(define (get-switch-door door-count unavailable-doors)
  (get-random-door door-count (lambda (n) (not (member n unavailable-doors)))))

(define (make-a-deal n (show-debug-info #f))
  (let ([success-count-stick 0]
        [success-count-switch 0])
    (for ((trial (in-range n)))
      (let ([doors (get-door-layout DOOR-COUNT)]
            [selected-door (random DOOR-COUNT)])
        (let ([revealed-door (get-revealed-door doors selected-door)])
          (let ([selected-door-switch (get-switch-door DOOR-COUNT (list selected-door revealed-door))])
            (when show-debug-info
              (printf "DOORS: ~A~%" doors)
              (printf "SELECTED DOOR: ~A~%" selected-door)
              (printf "REVEALED DOOR: ~A~%" revealed-door)
              (printf "SWITCH DOOR: ~A~%" selected-door-switch))
            (cond [(car? selected-door doors)
                   (set! success-count-stick (add1 success-count-stick))]
                  [(car? selected-door-switch doors)
                   (set! success-count-switch (add1 success-count-switch))])))))
    (printf "Success Rate of Sticking:  ~A%~%" (exact->inexact (* 100 (/ success-count-stick n))))
    (printf "Success Rate of Switching: ~A%~%" (exact->inexact (* 100 (/ success-count-switch n))))
    (if (> success-count-switch success-count-stick)
        (printf "Better off Switching~%")
        (printf "Better off Sticking~%"))))

(make-a-deal 100000)
  2. Jamie Hope said
    July 24, 2009 at 1:57 PM

    I already knew that the correct answer is the probability of winning by switching is 2/3, but:

    #!r6rs

(import (rnrs)
        (srfi :27))

(define (create-game) ; false = goat, true = car
  (let ((v (make-vector 3 #f)))
    (vector-set! v (random-integer 3) #t)
    v))

(define (player-choice) (random-integer 3))

(define (host-choice g p) ; host always chooses a goat
  (case p
    ((0) (if (vector-ref g 1) 2 1))
    ((1) (if (vector-ref g 0) 2 0))
    ((2) (if (vector-ref g 0) 1 0))))

(define (switch p h)
  (case (+ p h)
    ((1) 2)
    ((2) 1)
    ((3) 0)))

(define (run-test n)
  (let loop ((wins 0) (total 0))
    (if (= total n) (/ wins total)
        (let* ((g (create-game))
               (p (player-choice))
               (h (host-choice g p))
               (s (switch p h)))
          (if (vector-ref g s)
              (loop (+ wins 1) (+ total 1))
              (loop wins (+ total 1)))))))

(display (inexact (run-test 1000000)))

    => 0.66756

  3. Mark VandeWettering KF6KYI said
    July 24, 2009 at 10:13 PM

    Ugly, but it works.

    #!/usr/bin/env python

# code for the monty hall problem
# written by Mark VandeWettering as a challenge on
# the programming praxis website.

import random

NTRIALS=10000

def trial(switch=False):
        # pick a random door...
        door = random.randint(1, 3)
        guess = random.randint(1, 3)
        if not switch:
            return door == guess
        else:
            # slightly clever, but the only way that you
            # lose is if you were lucky enough (or unlucky
            # enough) to guess the right door in the first
            # place.   This gives away the entire problem.
            return door != guess

cnt_noswitch = 0
cnt_switch = 0

for x in range(NTRIALS):
    if trial():
        cnt_noswitch = cnt_noswitch + 1
    if trial(switch=True):
        cnt_switch = cnt_switch + 1

print "By not switching, you won %d/%d rounds." % (cnt_noswitch, NTRIALS)
print "By switching, you won %d/%d rounds." % (cnt_switch, NTRIALS)
if cnt_switch > cnt_noswitch:
        print "It appears you should switch."
else:
        print "It appears you should not switch."
  5. Paulo Jorge Matos said
    July 27, 2009 at 10:37 AM

    I suggest also reading a nice treatment of this exact problem in “The man who loved only numbers” by Paul Hoffman.

  6. Brian Everett said
    July 30, 2009 at 7:19 PM

    I’m just now learning Python and figured I’d play around with its list capabilities for this one…

    Originally I was using list comprehension to generate a list of random numbers (to indicate which door the car is behind) and keeping the contestant’s choice constant (always picking door number 1), but I realized it might be slightly faster to randomize the contestant’s choice and assume the car is always located behind door number 1 – simply using the list as a looping mechanism.

    import random
trials = 100000
print "Switching will win: %2.2f%% of the time" % (len(filter(lambda trial: random.randint(1, 3) != 1, xrange(trials))) / float(trials) * 100)
  7. Let’s Make A Deal! « Programming Praxis | what a gloomy day.. said
    August 4, 2009 at 4:46 PM

    [...] Let’s Make A Deal! « Programming Praxis. [...]

  8. Greg R said
    August 13, 2009 at 12:51 PM

    I made an attempt in PL/SQL (Oracle). I made the number of doors configurable (assuming that the host opens all doors except yours or the prize, or a random single door if you have chosen the prize door initially).

    declare
  Runs  integer := 10000;
  Doors integer := 3;

  function RunMonteHaul
  (
  Runs    in  integer,
  MaxDoor in  integer,
  Swap    in  boolean
  )
  return integer
  is
    Prize     integer;
    OtherDoor integer;
    MyDoor    integer;
    Wins      integer := 0;
    i integer;
    j integer;
  begin

    for i in 1 .. Runs loop
      Prize := dbms_random.value(1,MaxDoor);
      MyDoor := dbms_random.value(1,MaxDoor);
      if Prize = MyDoor then
        if Prize = MaxDoor then
          OtherDoor := 1;
        else
          OtherDoor := MaxDoor;
        end if;
      else
        OtherDoor := Prize;
      end if;
      if Swap then
        MyDoor := OtherDoor;
      end if;
      if MyDoor = Prize then
        Wins := Wins + 1;
      end if;
    end loop;
    return Wins;
  end RunMonteHaul;
begin
    dbms_output.put_line('Runs  ' || Runs);
    dbms_output.put_line('Doors ' || Doors);
    dbms_output.put_line('Swap Wins    ' || RunMonteHaul(Runs,Doors,true));
    dbms_output.put_line('No Swap Wins ' || RunMonteHaul(Runs,Doors,false));
end;

    This produces the output

    Runs  10000
Doors 3
Swap Wins    6290
No Swap Wins 3725

Runs  10000
Doors 10000
Swap Wins    9999
No Swap Wins 1

Leave a Reply