APL Wiki|
Size: 5175
Comment:
|
← Revision 14 as of 2011-02-20 14:59:57 ⇥
Size: 5353
Comment: typo fixed
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = Goats the second = | ## page was renamed from The_3_Goats_II ## page was renamed from TheThreeGoatsII ## page was renamed from GoatsTheSecond = The Three Goats II = |
| Line 3: | Line 6: |
| '''Under construction''' | |
| Line 7: | Line 10: |
| Following 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. 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. | 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. |
| Line 30: | Line 35: |
| 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: | 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: |
| Line 42: | Line 49: |
| 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. Hence the result people find counter intuitive. 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. | 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. |
| Line 53: | Line 62: |
| 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. | 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. |
| Line 88: | Line 97: |
| 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 Kai Jaeger the author of the original problem. Kai pointed out the significant performance penalties of using nested arrays in terms of memory use and speed. 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": | 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": |
| Line 123: | Line 138: |
| 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 vendor independent. | 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. << [[Probabilities/3goats/task|The Task]] |
| Line 126: | Line 147: |
| ---- CategoryPuzzles |
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