Talk:Towers of Hanoi: Difference between revisions
Content added Content deleted
(New section: Who or what is "Towers of Hanoi"?) |
(→Verbose explanation for J: new section) |
||
Line 12: | Line 12: | ||
["http://www.google.com/search?hl=en&q=%22Towers+of+Hanoi%22&btnG=Google+Search"] |
["http://www.google.com/search?hl=en&q=%22Towers+of+Hanoi%22&btnG=Google+Search"] |
||
== Verbose explanation for J == |
|||
Here is one of the J implementations: |
|||
<lang j>H =: i.@,&2 ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. *</lang> |
|||
This could be rephrased as: |
|||
<lang j>H =: elsePart ` thenPart @. * |
|||
elsePart=: i.@,&2 |
|||
thenPart=: ({&0 2 1,0 2,{&1 0 2)@H@<:</lang> |
|||
First off, note that this rephrasing has introduced two new names and has also replace anonymous recursion (<code>$:</code>) with non-anonymous recursion (<code>H</code>) -- it would be bad to have the recursion happen purely within thenPart without the conditional which was in the original definition of H. |
|||
But, wait, why does else come before then? For the same reason that 0 comes before 1. The primitive <code>@.</code> uses its right argument to come up with an index which is used to select from the code fragments on the left. |
|||
In this case, the right argument to <code>@.</code> is <code>*</code> which returns 0 for zero arguments and 1 for positive arguments. So the test, in essence is: is the right argument greater than zero? |
|||
This means that elsePart only runs with a right argument of zero. And it looks like this: |
|||
<lang j> i.@,&2(0)</lang> |
|||
In other words, it returns nothing. (But it is a carefully crafted nothing: it is a numeric array with two columns and no rows.) |
|||
Now let's consider thenPart with an argument of 1: |
|||
<lang j>({&0 2 1,0 2,{&1 0 2)@H@<: 1</lang> |
|||
This is equivalent to: |
|||
<lang j>({&0 2 1,0 2,{&1 0 2)@H 0</lang> |
|||
Which, in turn, is equivalent to |
|||
<lang j>({&0 2 1,0 2,{&1 0 2) i.0 2</lang> |
|||
Which, in turn, is equivalent to: |
|||
<lang j>((i.0 2){0 2 1),0 2,((i.0 2){1 0 2)</lang> |
|||
And { is J's indexing function, but since no actual indices are being used, this is equivalent to: |
|||
<lang j>(i.0 2),0 2,(i.0 2)</lang> |
|||
In other words, we have these two column arrays with no rows and between them we put a row that has the values 0 2. So the result looks like this: |
|||
<lang j> H 1 |
|||
0 2</lang> |
|||
Simple, no? (Or, it's simple once you get used to the idea of manipulating empty arrays which have structure but no elements. Until then this whole idea of working with nothing can seem a bit strange. But, if that bothers you, then maybe you can have some sympathy for how romans must have felt when they first encountered arabic numerals.) |
|||
Now, for the <code>H 2</code> case, we know from the above that we are going to be evaluating: |
|||
<lang j>((H 1){0 2 1),0 2,((H 1){1 0 2)</lang> |
|||
And, <code>0 2 { 0 2 1</code> yields <code>0 1</code> Likewise <code>0 2 { 1 0 2</code> yields <code>1 2</code>. Thus the result of H 2 is this array: |
|||
<lang j> H 2 |
|||
0 1 |
|||
0 2 |
|||
1 2</lang> |
|||
In other words, for H n, we find H n-1 and use that result twice: |
|||
First, use it keeping our starting point the same, and swapping the use of the other two pegs. Then (after we have moved our disk from peg 0 to peg 2), we use it again but holding the end point the same and swapping the use of the first two pegs. |
|||
(Some people might feel they should object to this remapping of results as inefficient, but this remapping does not make a difference to the [[wp:Big O notation|big O]] efficiency, and in practice should be a [[wiki:PrematureOptimization|minor concern]].) |