APL Wiki|
⇤ ← Revision 1 as of 2008-10-25 09:11:19
Size: 4181
Comment:
|
Size: 5175
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 7: | Line 7: |
| I have just applied this approach to your Goats problem and I think it makes the solution obvious and allows a non looping simulator to be written that only relies on simple arithmetic on boolean vectors. | 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. |
| Line 30: | Line 30: |
| 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. 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 46: | Line 46: |
| 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. I have attached a copy in a text file in the standard Dyalog font so hopefully if you open it with !NoteBook say, and set the font to Dyalog std you should be able to read it. The right argument is simply the number of simulations. To see how it works simply 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. | 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: |
| Line 52: | Line 52: |
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 85: | Line 88: |
| The following function does exactly the same thing but is optimized for speed. Following the logic is a bit harder, but it's much faster: | 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": |
| Line 89: | Line 92: |
| ⍝ Improved version | ⍝Faster version |
| Line 120: | Line 123: |
| 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. |
Goats the second
Under construction
The Approach
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.
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. 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.
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 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":
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 vendor independent.
Author: GrahamSteer