APL Wiki
The Three Goats II
The Approach
This is a follow on from the "New Tutorial" thread on comp.lang.apl where I offered the view that the power of APL was unlocked, in my case at least, by thinking in patterns and more often than not, boolean patterns.
I have applied this approach to the Goats problem where I think it makes the solution a little more obvious and allows a non looping simulator to be written that only relies on simple arithmetic on boolean vectors.
The logic in the form of a type of truth table goes as follows:
The full truth table of all possible outcomes is:
1 0 0 0 1 0 0 0 1
When the contestant makes his choice (first row) he has the following pattern of possible outcomes:
1 0 0
i.e. he has one chance of guessing right and two of guessing wrong so he has a 33% chance of winning the star prize.
After he has made his choice this determines the pattern (second two rows) that passes on to the game show host to be:
0 1 0 0 0 1
Now the host knows which box contains the star prize and is subject to two very important constrains: he cannot open the box the contestant has chosen nor the box containing the star prize, otherwise we do not have a game!
So, in his pattern he must now remove a zero from the outcome (column) consistent with the contestant's guess. Doing so leaves the following pattern of possible outcomes which can be passed back to the contestant which he can now choose to accept or stick with his original guess:
0 1 1
and the truth table after the host's choice reduces to:
1 0 0 0 1 1
So now you can see that the pattern he can switch to (the second row) has two chances of being correct (67%) whereas his original guess (the first row) only has a one in three chance.
Clearly when making his selection in the case where the contestant guesses correctly the host has two rather than just the one box (zero) to choose from but to the contestant the outcome is independent of the host's choice because the outcome is the same if he switches i.e. he loses.
Choosing to switch at random simply yields an average of the one in three and two in three outcomes i.e. one in two or 50%.
I have coded a simulator based on the above logic in basic apl with no requirement for looping and only using very simple arithmetic on boolean vectors. The right argument is simply the number of simulations:
Goats 1000000 33.3 66.7 50.0
To see how it works simply modify the function to output the result of each line to the screen with the right argument set at 10 say or make the internal variables global rather than local and inspect them.
The Code
r←Goats n;c;g;h;s;sr;pv;ng;ns;nsr ⍝Correct door number c←(⌈(3÷n)×n?n)⌽¨⊂1 0 0 ⍝Contestant's guess g←(⌈(3÷n)×n?n)⌽¨⊂1 0 0 ⍝Doors that cannot be opened by the host h←×c+g ⍝Doors the contestant can switch to if he always switches s←h-g ⍝Doors selected if the contestant switches at random sr←(s×~pv)+(pv←⌊0.5+(÷n)×n?n)×g ⍝Number of original guesses correct ng←(+/3=+/¨c=¨g) ⍝Number of switches correct ns←(+/3=+/¨c=¨s) ⍝Number of random switches correct nsr←(+/3=+/¨c=¨sr) ⍝Probabilies of for each outcome r←1⍕(100÷n)×ng,ns,nsr
In the function above I have used nested arrays so that anyone inspecting the results, as I suggest above, will see them set out similar to the truth table I describe in the approach.
Before submitting my solution to the wiki I discussed it with KaiJaeger the author of the original problem. Kai pointed out the significant performance penalties of using nested arrays in terms of speed and memory use in this case.
I have, therefore, included the function below which does exactly the same thing but without nesting. This makes following the logic a bit harder, but it's much faster.
You might like to compare the two on your machine. The message being "do not use nesting unless you really have to":
r←Goats2 n;c;g;h;s;sr;pv;ng;ns;nsr ⍝Faster version ⍝Correct door number c←(⌈(3÷n)×n?n)⌽(n,3)⍴1 0 0 ⍝Contestant's guess g←(⌈(3÷n)×n?n)⌽(n,3)⍴1 0 0 ⍝Doors that cannot be opened by the host h←×c+g ⍝Doors the contestant can switch to if he always switches s←h-g ⍝Doors selected if the contestant switches at random pv←⌊0.5+(÷n)×n?n sr←(s×[1]~pv)+pv×[1]g ⍝Number of original guesses correct ng←(+/3=+/c=g) ⍝Number of switches correct ns←(+/3=+/c=s) ⍝Number of random switches correct nsr←(+/3=+/c=sr) ⍝Probabilies of for each outcome r←1⍕(100÷n)×ng,ns,nsr
In conclusion I believe that this section of the wiki is the ideal place for members to post classical problems and their solutions in APL together with a commentary on the approach adopted.
Most people enjoy a challenge and it is an excellent way to learn.
Clearly it will be of benefit to more people if the solutions are not vendor specific.
<< The Task
Author: GrahamSteer