[Haskell-beginners] tower hanoi problem

[Dudley Brooks]

Plus I should say that the "first" (or whichever) step might also really 
be more than one step.  The crucial idea is that there are individual 
step(s) versus "lumped" step(s), where the individual step(s) are the 
base case(s) and the "lumped" step(s) are the recursive invocation(s).

On 2/16/15 10:31 AM, Dudley Brooks wrote:
> You're right, of course.  I guess the more precise way to say what I 
> meant is that you *separate* a single step from everything else, 
> dealing with everything else as a lump ... or two lumps ... or three 
> lumps ... or ...
>
> I did at least say that "a 'single step' might have more than one 
> step."  ;^)  My mistake was the use of the word "first".
>
> On 2/16/15 5:07 AM, Joel Neely wrote:
>> I'm sorry, but I must disagree with the generalization.
>>
>> You described "the very nature" of a typical recursion over a list:
>> (1) deal with the head, then
>> (2) deal with everything else.
>>
>> But lists are not the only recursive structure. Infix-order 
>> processing of a tree, for example, is more naturally described as:
>> (1) deal with the left sub-tree (the first "everything else"),
>> (2) deal with the parent (analogous to the head of a list),
>> (3) deal with the right sub-tree (the second "everything else").
>>
>> At the risk of a spoiler...
>>
>> .
>>
>> .
>>
>> .
>>
>> .
>>
>> One approach to the Towers of Hanoi problem emerges nicely from 
>> thinking of the moves as a tree.
>>
>> -jn-
>>
>> On Sun, Feb 15, 2015 at 2:54 PM, Dudley Brooks 
>> <dbrooks at runforyourlife.org <mailto:dbrooks at runforyourlife.org>> wrote:
>>
>>     In my opinion, advising Mr Wobben to watch the pattern of moves
>>     will *not* lead him to the recursive solution, since the pattern
>>     of moves is really iterative.
>>
>>     My hint would be to remember the very nature of recursion itself
>>     (for *any* problem):  Do the first step.  Then (to put it very
>>     dramatically) do *everything else* in *a single step*! 
>>     (Realizing that "everything else" is really the same problem,
>>     just made slightly smaller.)
>>
>>     Note:  "A single step" might itself have more than one step.  My
>>     point is that recursion consists of (to put it humorously):  To
>>     do ABCDEFGHIJKLMNOPQRSTUVWXYZ, first you do A, then you do
>>     BCDEFGHIJKLMNOPQRSTUVWXYZ.  And, of course, "first" might
>>     actually be "last"!  And remembering the story of the Gordian
>>     Knot might help too.  (I apologize that trying not to be too
>>     explicit in the hint possibly makes it even more obscure.)
>>
>>     Here's another hint that's useful for all kinds of programming
>>     problems, not just recursion:  Most problems consist of not only
>>     what you're trying to solve, but also what the restrictions are
>>     on what you're allowed to do to solve it.  Often some good
>>     insights come from imagining how you could solve the problem if
>>     you could ignore one or more of the restrictions (that's what I
>>     meant by the Gordian Knot reference).  So for the Towers of
>>     Hanoi, think about what the restrictions are on what kind of
>>     moves you're allowed to make.  Remove one of those restrictions.
>>
>>     (Speaking of the iterative solution, the fun thing about actually
>>     physically doing the Towers of Hanoi is that, even though you're
>>     doing it by remembering the steps of the iterative pattern, as
>>     you watch the towers grow and shrink you can kind of "see" the
>>     recursion.)
>>
>>
>>     On 2/15/15 12:51 AM, Roelof Wobben wrote:
>>
>>         YCH schreef op 15-2-2015 om 9:45:
>>
>>             How about if I say "Actually target was c not b and here
>>             is one more
>>             disc. I put it on a. Now you should move all to c"
>>
>>
>>
>>         Hanoi 1 a b c
>>
>>         A -> C
>>
>>         Hanoi 2 a b c
>>
>>         A -> B
>>         A -> C
>>         B -> C
>>
>>         Hanoi 3 a b c
>>
>>         A -> C
>>         A -> B
>>         C -> B
>>         A -> C
>>         B -> A
>>         B -> C
>>         A -> C
>>
>>
>>         Roelof
>>
>>
>>         _______________________________________________
>>         Beginners mailing list
>>         Beginners at haskell.org <mailto:Beginners at haskell.org>
>>         http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>>     _______________________________________________
>>     Beginners mailing list
>>     Beginners at haskell.org <mailto:Beginners at haskell.org>
>>     http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>>
>>
>> -- 
>> Beauty of style and harmony and grace and good rhythm depend on 
>> simplicity. - Plato
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150216/9a5e0d0e/attachment-0001.html>