Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: tower hanoi problem (Roelof Wobben)
2. Re: tower hanoi problem (Joel Neely)
----------------------------------------------------------------------
Message: 1
Date: Mon, 16 Feb 2015 19:45:40 +0100
From: Roelof Wobben <[email protected]>
To: [email protected], The Haskell-Beginners Mailing List -
Discussion of primarily beginner-level topics related to Haskell
<[email protected]>
Subject: Re: [Haskell-beginners] tower hanoi problem
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150216/bfd7a26e/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 16 Feb 2015 14:01:32 -0600
From: Joel Neely <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] tower hanoi problem
Message-ID:
<CAEEzXAgzZd9=mep8-tz268qcoohgx4gmmmniikdpfgwhb+7...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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 <[email protected]> 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 <[email protected]
> > 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
>>> [email protected]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> 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
> [email protected]http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> 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.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 80, Issue 34
*****************************************
