[Haskell-beginners] tower hanoi problem

[Dudley Brooks]

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/a5e0da5f/attachment.html>