[Haskell-beginners] tower hanoi problem

[Dudley Brooks]

(I hope that no one will think that this is too much of a hint.)

There are three restrictions on how you can move:

(1)  You can only move one disc at a time.

(2)  You can only move the top disc of a stack.

(3)  You can't put a larger disc on a smaller one.

What if (1) weren't true?  What if you could move a whole bunch of discs 
at the same time?  (Which would kind of mean that (2) wasn't true 
either.)  What if, after you had removed a certain number of discs (I 
won't say how many, but think small!) from the top of a stack, you could 
simply pick up the entire remaining stack and move it?

On 2/16/15 10:45 AM, Roelof Wobben 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 <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
>>>
>>
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>

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