[Haskell-beginners] tower hanoi problem

[Joel Neely]

Instead of thinking:

   1. "Where do I move the top (smallest) disc?" and then
   2. "How do I move everything else?"

try thinking

"Where do I move the bottom (largest) disc?" along with
"What must happen before I move the bottom disc?" and
"What must happen after I move the bottom disc?"


-jn-


On Mon, Feb 16, 2015 at 12:45 PM, Roelof Wobben <r.wobben at home.nl> wrote:

>  And Im still confused.
>
> Roelof
>
>
>
> Dudley Brooks schreef op 16-2-2015 om 19:41:
>
> 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
> > 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
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>>
>> _______________________________________________
>> Beginners mailing list
>> 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
>
>
>
>
>
> _______________________________________________
> Beginners mailing listBeginners at haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> 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/7903acad/attachment-0001.html>