Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Help with program: Monty Hall Problem

 
Philip Herzer
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm really into number theory and solving problems like this. I have covered the first six chapters of How to Program: Java, sixth edition. These chapters cover the basics of input/output, control structures (if, switch, do/while, while, for, etc), and functions. So, I want to stay within those elements to work on this problem.

The problem is based on Let's Make a Deal program that used to be shown in the seventies. First of all, there are three doors. Randomly, behind one door, there is a good prize. The other two doors contain bad prizes. The contestant, or user, is asked to choose door number 1, 2 or 3. Then,the user is shown one of the booby prize doors. Here, there are two cases. If the user selected the good door the first time, then one of the other two remaining booby prize doors are opened randomly. If the user selected a booby prize door, then the other booby prize door is opened.

Now we have two closed doors. One that was chosen by the user, and the one that was not opened. The user is then asked if he/she would like to switch doors.

Finally, the user's door is opened, either revealing a good prize or a booby prize.


Here's what I have written so far:


The part I'm stumped on is after generating the random door for the golden prize, how can I make it random for the other two doors. For example, if the golden door is 3, than all we have to do is

This situation works will if it is three, but not so good if we got a two for the golden prize door or 1. What if we were to hava n+1 doors, for example 200, 300, or more doors?

I would appreciate in helpful suggetions on how to approach this problem

Thanks,
Philip

[ October 12, 2004: Message edited by: Philip Herzer ]
[ October 12, 2004: Message edited by: Philip Herzer ]
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You could set the value for open_door in exactly the same way as for good_door, except that if you happen to get the same value, just pick another.

For example, start by setting them equal. Then, while they stay equal, keep picking a new value for open_door...

I've never used the Random class, so I'm just assuming that all of that code is okay. Another way to get an int from 1 to 3 is...
int x = 1 + (int)(Math.random()*3);

Yes, I will switch doors now, thank you.

(If you haven't read it yet, you might be interested in Paul Hoffman's book, The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for Mathematical Truth.)
[ October 12, 2004: Message edited by: marc weber ]
 
Philip Herzer
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Marc for your help. But, what happens if I get a 2 (meaning door) for the prize door? Than, we need to randomly pick a number that is either 1 or 3. I wonder if there is a way in Java to generate a random number and exclude certain values.

Lastly, after that number is generated it should be stored in open_door and remaining value will be stored in other_door.

I'm thinking a long switch statements, buried in if statements.

I'll go bury through the javadocs again.
 
Layne Lund
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think marc tried to describe one possible algorithm to do this. I think I will attempt to clarify. If I understand correctly, you need to randomly pick the door with the prize (good_door) and if the user picks this door, you need to randomly pick the door to open (open_door). This last random selection needs to be between the two doors that are left. I think marc's code above potentially solves the problem for you, but I'll restate it in pseudocode:

In other words, you continuously pick a number between 1 and 3 until it is different than the first random number.

Unfortunately, this has a pitfall: there is the likelihood that you will pick the previously chosen number each time a random number is generated. This likelihood is so small in this case, that it is probably negligible. However, in other similar situations, it can be a serious problem. (A card shuffling algorithm would be a good example.) A "better" approach may be to add the numbers to an array and randomly choose an index in the array:

(Note that I am using indentation, not braces, to indicate nesting levels.)

In this particular case, the above solution is probably overkill. However, it would definitely be a better approach to shuffling cards or other similar situations.

HTH

Layne
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Exactly, Layne. Thanks for clarifying.

When I was first learning Java, I used this approach in developing a "Concentration" type game. Consider a 6x6 grid of 36 squares. I needed to randomly assign 18 pairs of images to these 36 squares. Basically, for each square, I generated a random number between 0 and 17. But I couldn't use any of these numbers more than twice; so I kept track of how many times each number was selected, and if it had already been used twice, I just generated another. Of course, the last squares likely require several tries, since there are less and less "acceptable" numbers remaining. But this never caused a noticeable delay, so I didn't change it.

(I think I considered something like your array idea. But I was looking at making new arrays after each pick, since the "pot size" changed each time. And I questioned whether creating all those new array objects was really any more efficient than numerous loop iterations.)

With only 3 doors, it's rarely going to iterate more than a few times...

LoopTest: Okay, the good door is number 2. Now give me another door to open.
LoopBody: Let's see... 1 through 3... How 'bout 2?
LoopTest: Nope. That's my good door.
LoopBody: Oh. What about 2?
LoopTest: Nope. Still my good door. I need a different one.
LoopBody: Uh... 2 maybe?
LoopTest: Geez... What bad luck today.
LoopBody: What about 1?
LoopTest: Okay, 1 it is. We're done.
 
Michael Dunn
Ranch Hand
Posts: 4632
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's one way you might do it (it's a bit rough, and needs testing)

 
Philip Herzer
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's the way according to the first two replies to my post:



It's rather rough. Michael Doen, thanks for the suggestion. I'll try that way also and use arrays.

Any comments or suggestions on the above code would be greately appreciated.


Thanks,
Philip
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, I couldn't resist. Maybe you'll find some pieces in here worth using.

Some of the code is written to accommodate a variable number of doors (more than 3), but I didn't fully implement this feature.

 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
From a mathematical perspective, the question is whether switching doors after being shown a so-called "booby prize" has any impact on the outcome. In other words, is a player any better or worse off by switching? Or doesn't it make a difference? A program can't "answer" this question, but it can provide a model to simulate numerous trials.

The program below simulates 100,000 trials as follows:
  • A grand prize door is randomly selected from the 3 options.
  • A player's choice is randomly selected from the 3 options. (This might be the grand prize door.)
  • A booby prize door is randomly selected, excluding the player's choice and the prize door. (Thus, if the player has unknowingly selected a booby prize, then the other booby prize is selected. But if the player has unknowingly selected the grand prize, then the booby prize is randomly selected from the 2.)
  • The player randomly decides whether to keep the door already selected, or switch to the remaining door.
  • The outcome of the trial is determined, and results are added to running totals.

  • The output from this program is consistent what we would expect mathematically.


    [ October 14, 2004: Message edited by: marc weber ]
     
    marc weber
    Sheriff
    Posts: 11343
    Java Mac Safari
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Philip:

    I've worked through the code you posted on October 12. Everything seems to work fine as is!

    The main thing I suggest is that you re-structure the logic around Monty's dialogue so that you don't have to duplicate his output under 3 scenarios. This way, the code would be easier to maintain if you decide to change his wording.
     
    Layne Lund
    Ranch Hand
    Posts: 3061
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Originally posted by marc weber:
    Exactly, Layne. Thanks for clarifying.

    [ snip ]

    (I think I considered something like your array idea. But I was looking at making new arrays after each pick, since the "pot size" changed each time. And I questioned whether creating all those new array objects was really any more efficient than numerous loop iterations.)


    The question isn't efficiency, really. It's whether or not the algorithm even completes at all. As mentioned already, it's not likely to keep picking the same door several times, but when the original "pot size" is large, it is much more difficult to randomly pick the last number.

    There are some variations on the array idea I gave. If you are randomly choosing from a list of object instead, an ArrayList would probably be ideal. In fact, an ArrayList can be used for ints as well, except that you have the overhead of wrapper classes. (Even if you use autoboxing in J2SE 5.0, there is still the overhead of creating wrapper classes, afaik. You just don't write the code for it explicitly.) With an ArrayList, you can remove the object that is chosen on each iteration, rather than creating a whole new list.

    Anyway, I'm glad to see that things are working out in the OP's program. I look forward to seeing you around more often, Philip.

    Regards,

    Layne
     
    Philip Herzer
    Greenhorn
    Posts: 21
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks everyone for your help and suggestions. I rewrote the program to incorporate functions, and cut down the the repetive code.

    I was wondering if anyone has any good suggestions on books that I could that would cover algorithims dealing with commnon computer algorithims used in programming for Java. I'm looking for something more thorough and deep than a cookbook.


    Many Thanks,
    Philip
     
    Philip Herzer
    Greenhorn
    Posts: 21
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    two questions arose while trying to simplify my work above and divide the program into functions. I've seperated my functions into these: 1) calcuate the prize_door, and the two booby prize doors; 2) ask for users input; 3) decide which door to offer to open for user and ask him if he'd like to stay or switch; 4) decide if he won or lost.

    My dilema is how to pass more than one variable if, for example, function one is like this:


    I tried to test whether this thing works in theory by having System.out.println(prize_door + " " + door2 + " " + door3);

    I kept getting the error that the variables were not initialized.

    My second question doesn't have to do with functions.

    If I don't set the variable to 0 for door2 or door 3, I will get the message that the variables may have not been initialized. In theory, they would have been initialized after running the while loop, since I had originally set my boolean variable num_check (it controls the while loop) to false.

    Why is this so? IN my function above, will I also need to instantiate the variables and set them to 0 like I did in the second code branch?

    Thanks again, for everyone's help. This concept of these local variables and making them aviable outside of the function is a little bit different from what I've learned while using python for several years.

    Many Thanks,
    Philip
    [ October 15, 2004: Message edited by: Philip Herzer ]
     
    marc weber
    Sheriff
    Posts: 11343
    Java Mac Safari
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Philip,

    To return "multiple values" from a method, you'll probably want to return a single array containing the values. This might simply be an int[] or it might even be a Door[] if you choose to define the doors as objects (like I did in my code above).

    Unlike member variables, local variables are not automatically initialized. Yes, you've set your boolean flag so that the while loop will value these; but the compiler doesn't know that this flag will always be set this way, so it sees potential for these to remain uninitialzed.

    Depending on the context of this method (whether you're intending to define multiple classes), you might declare the doors as member variables -- perhaps even static -- and have the method modify these directly rather than returning locally derived values.

    As a side note, you might re-consider your assignment method. The odds of picking random numbers 1, 2, and 3 without any duplicates is only 2/9 (on each trial), so there could be a lot of iterations before getting an acceptable result.

    Consider this: You can pick the first one easily enough because there are no restrictions. Then you can pick the second in a way that just doesn't match the first (with good odds of success). Now... Note that these three ints will always sum to 6 (1+2+3). So after picking the first two, the third is just 6 minus the first two. No more iterations needed!

    (I used this idea in my code above, although mine summed to 3 because I was using 0, 1, and 2 as options.)
    [ October 15, 2004: Message edited by: marc weber ]
     
    • Post Reply
    • Bookmark Topic Watch Topic
    • New Topic