A Rebol Challenge. The Monty Hall Puzzle

We Reboler have been challenged. I was posing some puzzles with some friends on another mailing list I belong to, the enjoyment of which is provided here first should you want to try and solve this for yourself. However, one of the people responding was a programmer, and he wrote a program to try to solve the problem. First he wrote this in Pearl (183 characters), then in Matlab (136 characters). I put it to you--smarter people than I--to put this man to shame! Give me your best Rebolette, and I will make him see the error of his ways :-) OK, no looking this up on the web. This is a real fun one if you have not seen it before, or better stated, worked through it. The scenario is such: you are given the opportunity to select one closed door of three, behind one of which there is a prize. The other two doors hide "goats" (or some other such "non-prize"), or nothing at all. Once you have made your selection, Monty Hall will open one of the remaining doors, revealing that it does not contain the prize. He then asks you if you would like to switch your selection to the other unopened door, or stay with your original choice. Here is the problem: Does it matter if you switch? P.S. this problem was presented to two of my engineers and myself many many years ago. We were told that the "staff" scientist at the company of the presenter all got it wrong. So the three of us worked on it together for about 25 minutes. Came to our conclusion, then wrote a computer program to prove it. I then wrote a layman's description of "why." Which I found was needed because SO MANY PEOPLE CAN NOT ACCEPT THE ANSWER. Especially statisticians! Too funny. If anyone wants a copy, I will dig it up. Now for the Email from my friend: He writes... Nah, matlab is the way to go for this: b=sum(floor(3*rand(100,100))==0);y=floor(3*rand(100,100)); o=(floor(2*rand(100,100))+1).*(y==0)+(3-y).*(y>0);c=sum(y.*o>0); d=sum(c>b-c<b); [b;c] if (d>90) fprintf(1,"Switching is better (95%%+ confidence)\n"); end But maybe you can do better in Rebol. I don't see a way to off the top of my head. Note that if we're just comparing the core computation, the matlab is barely three lines. (The "o" variable is not strictly needed, but I am including it anyway to explicitly construct the door-picked-by-Monty.) Perl is 183 characters, not counting invocation from the command line or comments. Matlab is 136. /usr/bin/perl -e 'print "St Sw (%win)\n";$d=0;for($i=0;$i<100;$i++){ $b=0;$c=0;for($a=0;$a<100;$a++){$b+=int(rand(3))==0}; for($a=0;$a<100;$a++){$y=int(rand(3));$o=$y?(3-$y):(int(rand(2))+1); $c+=$o*$y>0;};$d+=($c>=$b)-($c<=$b);print "$b $c\n"};print "St Sw (%win)"; if ($d>90) { print "\nSwitching is better (95%+ confidence)" };print "\n"' Reichart... [Reichart--Prolific--com] Be useful.

On 16-Dec-01, Reichart wrote:

> We Reboler have been challenged. > I was posing some puzzles with some friends on another mailing list > (%win)"; if ($d>90) { print "\nSwitching is better (95%+ > confidence)" };print "\n"'

Hi Reichart.

> But maybe you can do better in Rebol. I don't see a way to off the top of > my head. Note that if we're just comparing the core computation, the

> is barely three lines. (The "o" variable is not strictly needed, but I am > including it anyway to explicitly construct the > door-picked-by-Monty.)

----- Original Message ----- From: <[SunandaDH--aol--com]> To: <[rebol-list--rebol--com]> Sent: Sunday, December 16, 2001 12:52 PM Subject: [REBOL] Re: A Rebol Challenge. The Monty Hall Puzzle

> Hi Reichart. > > > > But maybe you can do better in Rebol. I don't see a way to off the top

> > my head. Note that if we're just comparing the core computation, the > matlab > > is barely three lines. (The "o" variable is not strictly needed, but I

> > including it anyway to explicitly construct the > > door-picked-by-Monty.) > ] > Print ["Win%" win * 100 / n]

Hi Reichart, The one is not as wonderous as Sunanda's solution but is interesting because you can use whatever symbols you like to represent the boxes :) The code below simulates the always switch strategy - returns rough probability of winning: REBOL[] d: {123}w: 0 loop n: 500 [ p: func[s][copy/part random s 1] b: p d c: p d if b = p union b c [w: w + 1]] w / n d: represents the choices - could have been any series of 3 elements e.g [box1 box2 box3] p: makes a random selection from a series b: the winning box c: the first choice (union b c) is equivalent to the two closed boxes after monty has opened one empty box That is it is equivalent too box-to-remove: exclude d union b c choices: exclude d box-to-remove An anxious person would probably figure out they'd more than likely goofed first go :) Cheers Brett.

> REBOL[] > d: {123}w: 0 loop n: 500 [ > [box1 box2 box3] > p: makes a random selection from a series

16 Dec 2001, 08:47:34, Reichart wrote:

> P.S. this problem was presented to two of my engineers and myself > many many years ago. We were told that the "staff" scientist at the > PEOPLE CAN NOT ACCEPT THE ANSWER. Especially statisticians! Too > funny. If anyone wants a copy, I will dig it up.

Hi Romano,

> Beautiful! You can remove the n + 1: > > Win: 0 n: 500 print ["Win%" 100 / n * loop n [win: win + last sort next > random > [0 0 1]]] >

On 16-Dec-01, Andreas Bolka wrote:

> 16 Dec 2001, 08:47:34, Reichart wrote: >> P.S. this problem was presented to two of my engineers and myself >> funny. If anyone wants a copy, I will dig it up. > I'd like to have a copy ;)

Hi Sunanda,

> Thanks. I thought I'd minimised it completely, but it's amazing what

> can do.

Hi Romano and Sunanda, Your work is brilliant ! It helps me to get to the problem, and finally my 17 years'old son explained it to me. If you consider that each time I loose I did not win, the answer can be shorten a bit. rebol[] win: 100 print ["Win% = " loop win [ win: win - first random [0 0 1]]] It is a beat cheatting considering that your version iterate 500 times so I give also my 1000 iterations version. rebol[] win: 1000 print ["Win% = " (loop win [ win: win - first random [0 0 1]]) / 10] These are respectively 43 and 51 bytes long. Patrick

Hello Reichart! On 16-Dic-01, you wrote: R> Does it matter if you switch? Readable version: random/seed now no-switch-wins: 0 switch-wins: 0 loop 1000 [ winning: random 3 your-choice: random 3 either your-choice = winning [ no-switch-wins: no-switch-wins + 1 ] [ switch-wins: switch-wins + 1 ] ] print [ "If you switch, you win" switch-wins "times" newline "If you don't switch, you win" no-switch-wins "times" ] Compact version: r: does[random 3]n: s: 0 loop 1000[either r = r[n: n + 1][s: s + 1]] print [ "If you switch, you win" s "times" newline "If you don't switch, you win" n "times" ] I presume the code you show is doing something different, but I don't speak perl or matlab... :) Regards, Gabriele. -- Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/

Hi Patrick,

> Your work is brilliant ! It helps me to get to the problem, and finally my > 17 years'old son explained it to me. If you consider that each time I loose > I did not win, the answer can be shorten a bit.

> rebol[] > win: 100 print ["Win% = " loop win [ win: win - first random [0 0 1]]] > 10] > These are respectively 43 and 51 bytes long.

Hi Romano, P.S.

> Are you from India?

Hi, Sunanda Print ["Win% " 200 / 3] I came to the same conclusion thanks to your "slow motion" explanation but I did not dare to put that. Indeed the 2/3 emerges from your explanation.

>so if MySwappedDoor is a 1, I'm a winner!

>The problem being that not everyone does accept that logic at first view.

Hi Allen, You're right. I didn't know about that refinement. I would have used "first random s" instead of "random/only". But here though, I used copy/part because I needed a series to work in the union operation. Otherwise I'll need to add "to-string" before the "random/only" and d will need to be restricted to being a string only. Doing this yields, REBOL[] d: {123}w: 0 loop n: 500 [ p: func[s][to-string random/only s] b: p d c: p d if b = p union b c [w: w + 1]] w / n Which is about 3 characters longer than the original :) Cheers Brett.

Hi, Sunanda, et al, It seems to me that the problem in the original post was persuasion and not just computation. That being the case, the text of the program itself (or its derivation) should be a compelling argument for the right answer. IOW, if I had trouble understanding/accepting an answer, I would not be very persuaded simply by the output of a highly compact program that seemed to contain assumptions about the very answer I was having trouble with. That said, let me offer two lines of reasoning (starting with the same assumptions -- one argument based on verbal reasoning and one based on code refactoring) which might be of some persuasive value (but YMMV). **************** * ASSUMPTIONS: * **************** 0) There are three doors. 1) The prize door is chosen at random. 2) The contestant chooses a door at random. 3) Monty chooses and opens a door at random that is neither the prize door nor the contestant's door. ******************** * VERBAL ARGUMENT: * ******************** Imagine that there are two contestants playing as a team. They agree on an initial guess (randomly chosen, remember), but then one (A) always keeps the initial guess, while the other (B) always switches after Monty opens a door. Since Monty always opens a non-prize door (leaving two doors unopened) exactly one of them must win on every round. Since Monty opens the non-prize door after the initial guess is chosen, his choice of which door to open changes neither the initial guess nor the door behind which the prize has already been placed. Therefore, A's chances of winning are unaffected by what Monty does. Since A is choosing randomly to find the winning one door out of three, his odds of winning are 1/3, and his odds of losing are 2/3. Therefore, B's odds of winning are 2/3 (B wins whenever A loses). ************************* * REFACTORING ARGUMENT: * ************************* Implementing the assumptions (using RANDOM) and trying a bunch of rounds, we get something like this (in my best commented-to-death style -- remember that we're explaining to a skeptic ;-) : 8<------------------------------------------------------------ pickadoor: function [ rounds [integer!] ][ prizedoor guessdoor montydoor keepwins switchwins ][ ; ; neither strategy has won anything before we start ; keepwins: switchwins: 0 ; ; simulate the specified number of rounds ; loop rounds [ ; ; prize is behind a randomly-chosen door ; prizedoor: random 3 ; ; contestant (or team) randomly guesses a door ; guessdoor: random 3 ; ; Monty opens a non-prize, non-guessed door ; until [ montydoor: random 3 all [montydoor <> prizedoor montydoor <> guessdoor] ] ; ; which strategy won on this round? ; either guessdoor = prizedoor [ keepwins: keepwins + 1 ][ switchwins: switchwins + 1 ] ] print [ "Keep won" keepwins "rounds," "switch won" switchwins "rounds" ] ] 8<------------------------------------------------------------ Having started with a painfully explicit (but obviously valid -- I hope!) function, let't start compacting and refactoring. I'll save my typing time and your bandwidth and reading time by omitting the comments from here on... Step 1: Since KEEPWINS + SWITCHWINS is always equal to rounds played thus far, we don't need both variables. Let's eliminate SWITCHWINS throughout the code. 8<------------------------------------------------------------ pickadoor: function [ rounds [integer!] ][ prizedoor guessdoor montydoor keepwins ][ keepwins: 0 loop rounds [ prizedoor: random 3 guessdoor: random 3 until [ montydoor: random 3 all [montydoor <> prizedoor montydoor <> guessdoor] ] if guessdoor = prizedoor [ keepwins: keepwins + 1 ] ] print [ "Keep won" keepwins "rounds," "switch won" rounds - keepwins "rounds" ] ] 8<------------------------------------------------------------ Step 2: Since KEEPWINS only depends on the values of GUESSDOOR and PRIZEDOOR (but *not* on MONTYDOOR), we can eliminate MONTYDOOR from the code. 8<------------------------------------------------------------ pickadoor: function [ rounds [integer!] ][ prizedoor guessdoor keepwins ][ keepwins: 0 loop rounds [ prizedoor: random 3 guessdoor: random 3 if guessdoor = prizedoor [ keepwins: keepwins + 1 ] ] print [ "Keep won" keepwins "rounds," "switch won" rounds - keepwins "rounds" ] ] 8<------------------------------------------------------------ Step 3: The variables PRIZEDOOR and GUESSDOOR are set to a new value once per loop, and then examined exactly once per loop; therefore, we can eliminate the variables by using their defining expressions instead of their (single) usage. 8<------------------------------------------------------------ pickadoor: function [ rounds [integer!] ][ keepwins ][ keepwins: 0 loop rounds [ if (random 3) = random 3 [ keepwins: keepwins + 1 ] ] print [ "Keep won" keepwins "rounds," "switch won" rounds - keepwins "rounds" ] ] 8<------------------------------------------------------------ At this point, a symmetry argument should suffice to persuade that the output converges to 1/3 and 2/3 (assuming that the PRNG is valid). Step 4: Apply symmetry; the choice of 3 is irrelevant. 8<------------------------------------------------------------ pickadoor: function [ rounds [integer!] ][ keepwins ][ keepwins: 0 loop rounds [ if 3 = random 3 [ keepwins: keepwins + 1 ] ] print [ "Keep won" keepwins "rounds," "switch won" rounds - keepwins "rounds" ] ] 8<------------------------------------------------------------ Step 5: Just for fun, let's get dense! Compacting words to one-letter names, pruning constant output strings, and eschewing layout whitespace... 8<------------------------------------------------------------ REBOL []p: function [n][k r][k: 0 loop n[if 3 = r 3[k: k + 1]]print[k n - k]] 8<------------------------------------------------------------ Step 6: If we're willing to pollute the global namespace, forego the function, and type the one-liner into the interactive console each time... 8<------------------------------------------------------------ n: 10000 k: 0 loop n[if 3 = random 3[k: k + 1]]print[k n - k] 8<------------------------------------------------------------ But, IMHO, the persuasion is in the process by which we arrived at the last version (or maybe a version or two before that... ;-) and not in its raw output. -jn- PS: As I've mentioned before, I have a random process that picks the sigs on this box. The resonance between topic and the randomly chosen sig per message has been *really* freaky today! -- If you think big enough, you'll never have to do it. -- Reisner's Rule of Conceptual Intertia joel:FIX:PUNCTUATION:dot:neely:at:fedex:dot:com

On 17-Dec-01, Carl Read wrote:

> Not being a statistician, (or having a clue what the above code > does:), my approach to such problems is to simulate them many times > description of my code. (: Anyway, it's 151 bytes long for what it's > worth.

Hi Joel,

> It seems to me that the problem in the original post was persuasion > and not just computation. That being the case, the text of the > program that seemed to contain assumptions about the very answer > I was having trouble with.

Hi, Sunanda, [SunandaDH--aol--com] wrote:

> I completely agree that a highly compressed program isn't often a > great way to win an argument. But (just to defend myself for a > moment) ... >

> The best test of a programming language isn't how compact a program > it can write, but (I would claim) how easy it is to write maintain- > able programs in it. But even that tests mainly the design skills > and long-term vision of the programmer. >

> A good test of all of our (and Perl and Matlab) solutions is how > easily can they be modified as various "real world" changes are > required. Almost by definition, we can't know what our programs > will face over there lifetimes, but here are a few of the sort of > things that might beset a Monty simulator: >

> I can see how my solution will naturally extend for some of these; > can be bodged into shape for others; and would be scrapped and > rewritten for the rest. And that's programming! >

On 17-Dec-01, Carl Read wrote:

> Here's a fixed version... > rebol[]k: s: 0 r: func[n][random n]m: does[p: r 3 c: r 3 p = c] loop > switch makes an original loss a win, so switching gives you 2 > chances in 3 of winning, thus doubling your chances of a win.

RE: [REBOL] Re: A Rebol Challenge. The Monty Hall Puzzle [carl--cybercraft--co--nz] wrote:

> On 17-Dec-01, Carl Read wrote: > > Here's a fixed version... > the hope that pictures will win out where words fail... (Not a View > version though - run it from the Console.)