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 (Joel Neely)
2. Re: tower hanoi problem (Roelof Wobben)
3. Re: tower hanoi problem (Dudley Brooks)
----------------------------------------------------------------------
Message: 1
Date: Mon, 16 Feb 2015 07:07:58 -0600
From: Joel Neely <[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:
<caeezxaiodrgugkg8qvgaap4sbwoi0fxbbohjdmqtr2cd4bb...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150216/0748a59a/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 16 Feb 2015 14:14:08 +0100
From: Roelof Wobben <[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: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150216/82bc2437/attachment-0001.html>
------------------------------
Message: 3
Date: Mon, 16 Feb 2015 09:27:48 -0800
From: Dudley Brooks <[email protected]>
To: Haskell Beginners <[email protected]>
Subject: Re: [Haskell-beginners] tower hanoi problem
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"; Format="flowed"
That definitely makes the iterative solution easier to see. Not sure if
it helps with seeing the recursive solution, but you're right, it *is*
the "natural" way to do the Towers.
On 2/15/15 7:10 PM, KC wrote:
>
> The interesting way is to view the pegs not in a straight line but in
> another conic section ...
>
> --
> --
>
> Sent from an expensive device which will be obsolete in a few months! :D
>
> Casey
>
> On Feb 15, 2015 12:54 PM, "Dudley Brooks" <[email protected]
> <mailto:[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] <mailto:[email protected]>
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
> _______________________________________________
> Beginners mailing list
> [email protected] <mailto:[email protected]>
> 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/ce005c4a/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 32
*****************************************
