tower of hanoi problem

newer
Getting "Discrete Mathematics...

older
Can't connect to or contact...

Roelof Wobben

13 Feb 2015 13 Feb '15

2:39 p.m.

Attachments:

attachment.html (text/html — 1.3 KB)

Show replies by date

Mike Meyer

13 Feb 13 Feb

4:54 p.m.

On Fri, Feb 13, 2015 at 1:39 PM, Roelof Wobben wrote:

...

Hello,

After a short break I try to make the next assignment of the CIS 194 course. I do self-study.

Lets say we have 1 disk with 2 pegs then we have this :

type Peg = String. type Move = (Peg, Peg) Hanoi :: Integer -> Peg -> Peg -> [Move]

So I can do this Hanoi 2 a b

How can I proceed further.

I do not see how I can tell that the disk can move from a to b And I do not see what the base case will be . I think when a is empty and b has a value.

It's a recursion problem. So you tackle it like any other recursion problem: · Divide your input into two cases: the terminal one that ends the recursion and the one you recurse on. · Decide how to handle the terminal case. In this case, you'll return a list consisting of one move. · Decide how to divide the non-terminal case into at least two sub-problems that are all closer to the terminal case by some measurement. · Write the code that makes the non-terminal calls and combines their values to create your return value. In cases where your function returns a list, the combination is almost always appending one case to the other.

Roelof Wobben

14 Feb 14 Feb

7:43 a.m.

Hello, I try to answer your questions. Maybe then it is clear where My thinking gets the wrong turn.

...

· Divide your input into two cases: the terminal one that ends the recursion and the one you recurse on.

I think the terminal one is when there is no moves anymore so when a and b are empty and c holds all the disk.

...

· Decide how to handle the terminal case. In this case, you'll return a list consisting of one move.

There is a problem. I thought I must return all the moves then.

...

· Decide how to divide the non-terminal case into at least two sub-problems that are all closer to the terminal case by some measurement.

two subproblems ? I can only think about one and that is looking what the next move can be.

...

· Write the code that makes the non-terminal calls and combines their values to create your return value.

Oke, when I have the right answers to the former questions, I can think about how to solve this one.

...

In cases where your function returns a list, the combination is almost always appending one case to the other.

I also think so , so it will be old case ++ new case because otherwise it will display in the wrong order. Roelof

Mike Meyer

10:24 a.m.

On Sat, Feb 14, 2015 at 6:43 AM, Roelof Wobben wrote:

...

Hello,

I try to answer your questions. Maybe then it is clear where My thinking gets the wrong turn.

...
· Divide your input into two cases: the terminal one that ends the recursion and the one you recurse on.

I think the terminal one is when there is no moves anymore so when a and b are empty and c holds all the disk.

I'd say the terminal one is one move, not no moves. I even gave it away with the next comment: · Decide how to handle the terminal case. In this case, you'll return a

...

...
list consisting of one move.

There is a problem. I thought I must return all the moves then.

Ah, I think we miscommunciated about what "terminal" means. I meant the case that terminates the recursion, not the problem. That result will be combined with the values returned by other calls to create the ultimate return value having all the moves. So when hanoi is called with only 1 disk to move, you just return the list consisting of that move. If it's called with more than 1 disk, you have to make multiple recursive calls with fewer disks than it was called with. I don't think you can do this without special handling for the single disk case, so you might as well make that one your terminating case. Handling the no-disk case would be part of the initial error checking.

...

· Decide how to divide the non-terminal case into at least two

...
sub-problems that are all closer to the terminal case by some measurement.

two subproblems ? I can only think about one and that is looking what the next move can be.

There's gotta be at least two subproblems, because you have to create smaller problems for the recursive calls. If you can make the problem smaller without creating two subpropblems - well, then your problem can just goes away! For hanoi, you don't need to worry about what the next move will be. Assume that you have a working hanoi routine that can handle fewer disks that you currently have. How can you use that to solve your current problem? It should be obvious that you have to move some number less than all of them to one peg, then move the rest to the other peg, and finally move the first stack you moved on top of the second stack. So you need to figure out how many to move and where to move them to so you don't make any illegal moves in the process.

...

· Write the code that makes the non-terminal calls and combines their

...
values to create your return value.

Oke, when I have the right answers to the former questions, I can think about how to solve this one.

Yup.

...

In cases where your function returns a list, the combination is almost

...
always appending one case to the other.

I also think so , so it will be old case ++ new case because otherwise it will display in the wrong order.

Well, the solution I outlined has more than one case to deal with, as you have to make three recursive calls.

Julian Birch

10:39 a.m.

Slightly off-topic, but you may be interesting in my post about the Fox/Goose/Corn problem. http://www.colourcoding.net/blog/archive/2015/01/03/fox-goose-corn-in-haskel... It's a full Haskell solution from beginning to end, and explains the steps as it goes along, and it's a pretty similar problem to Hanoi. J On 14 February 2015 at 15:24, Mike Meyer wrote:

...

On Sat, Feb 14, 2015 at 6:43 AM, Roelof Wobben wrote:

...
Hello,

I try to answer your questions. Maybe then it is clear where My thinking gets the wrong turn.

...
· Divide your input into two cases: the terminal one that ends the recursion and the one you recurse on.

I think the terminal one is when there is no moves anymore so when a and b are empty and c holds all the disk.

I'd say the terminal one is one move, not no moves. I even gave it away with the next comment:

· Decide how to handle the terminal case. In this case, you'll return a

...
...
list consisting of one move.

There is a problem. I thought I must return all the moves then.

Ah, I think we miscommunciated about what "terminal" means. I meant the case that terminates the recursion, not the problem. That result will be combined with the values returned by other calls to create the ultimate return value having all the moves.

So when hanoi is called with only 1 disk to move, you just return the list consisting of that move. If it's called with more than 1 disk, you have to make multiple recursive calls with fewer disks than it was called with. I don't think you can do this without special handling for the single disk case, so you might as well make that one your terminating case. Handling the no-disk case would be part of the initial error checking.

...
· Decide how to divide the non-terminal case into at least two

...
sub-problems that are all closer to the terminal case by some measurement.

two subproblems ? I can only think about one and that is looking what the next move can be.

There's gotta be at least two subproblems, because you have to create smaller problems for the recursive calls. If you can make the problem smaller without creating two subpropblems - well, then your problem can just goes away!

For hanoi, you don't need to worry about what the next move will be. Assume that you have a working hanoi routine that can handle fewer disks that you currently have. How can you use that to solve your current problem? It should be obvious that you have to move some number less than all of them to one peg, then move the rest to the other peg, and finally move the first stack you moved on top of the second stack. So you need to figure out how many to move and where to move them to so you don't make any illegal moves in the process.

...
· Write the code that makes the non-terminal calls and combines their

...
values to create your return value.

Oke, when I have the right answers to the former questions, I can think about how to solve this one.

Yup.

...
In cases where your function returns a list, the combination is almost

...
always appending one case to the other.

I also think so , so it will be old case ++ new case because otherwise it will display in the wrong order.

Well, the solution I outlined has more than one case to deal with, as you have to make three recursive calls.

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Roelof Wobben

12:56 p.m.

Dudley Brooks

1:43 p.m.

An aside about the Towers of Hanoi which does not answer the OP's question but is interesting: A recursive solution is a great method for having a computer play the game. But human beings might want to play it also, and humans don't think recursively -- we can't keep track of the intermediate results and where we are in the process. We think iteratively. It turns out that if you actually physically play the game you will discover that there is a very simple iterative pattern to the moves. I won't tell it, so that people can have the fun of discovering it. Disclosure: I "discovered" this while teaching the game to a child friend who had no particular mathematical or computer-related inclination ... and it was actually *she* who discovered it. She couldn't articulate it in words ... but she could *do* it. Here's a "Chinese proverb" definition (or example) of recursion: A journey of 10,000 miles starts with a single step ... followed by being able to take one more step no matter how many steps you have already taken. On 2/14/15 7:24 AM, Mike Meyer wrote:

...

On Sat, Feb 14, 2015 at 6:43 AM, Roelof Wobben mailto:r.wobben@home.nl> wrote:

Hello,

I try to answer your questions. Maybe then it is clear where My thinking gets the wrong turn.

· Divide your input into two cases: the terminal one that ends the recursion and the one you recurse on.

I think the terminal one is when there is no moves anymore so when a and b are empty and c holds all the disk.

I'd say the terminal one is one move, not no moves. I even gave it away with the next comment:

· Decide how to handle the terminal case. In this case, you'll return a list consisting of one move.

There is a problem. I thought I must return all the moves then.

Ah, I think we miscommunciated about what "terminal" means. I meant the case that terminates the recursion, not the problem. That result will be combined with the values returned by other calls to create the ultimate return value having all the moves.

So when hanoi is called with only 1 disk to move, you just return the list consisting of that move. If it's called with more than 1 disk, you have to make multiple recursive calls with fewer disks than it was called with. I don't think you can do this without special handling for the single disk case, so you might as well make that one your terminating case. Handling the no-disk case would be part of the initial error checking.

· Decide how to divide the non-terminal case into at least two sub-problems that are all closer to the terminal case by some measurement.

two subproblems ? I can only think about one and that is looking what the next move can be.

There's gotta be at least two subproblems, because you have to create smaller problems for the recursive calls. If you can make the problem smaller without creating two subpropblems - well, then your problem can just goes away!

For hanoi, you don't need to worry about what the next move will be. Assume that you have a working hanoi routine that can handle fewer disks that you currently have. How can you use that to solve your current problem? It should be obvious that you have to move some number less than all of them to one peg, then move the rest to the other peg, and finally move the first stack you moved on top of the second stack. So you need to figure out how many to move and where to move them to so you don't make any illegal moves in the process.

· Write the code that makes the non-terminal calls and combines their values to create your return value.

Oke, when I have the right answers to the former questions, I can think about how to solve this one.

Yup.

In cases where your function returns a list, the combination is almost always appending one case to the other.

I also think so , so it will be old case ++ new case because otherwise it will display in the wrong order.

Well, the solution I outlined has more than one case to deal with, as you have to make three recursive calls.

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

YCH

8:16 a.m.

On Sat, Feb 14, 2015 at 4:39 AM, Roelof Wobben wrote:

...

Hello,

After a short break I try to make the next assignment of the CIS 194 course. I do self-study.

Lets say we have 1 disk with 2 pegs then we have this :

type Peg = String. type Move = (Peg, Peg) Hanoi :: Integer -> Peg -> Peg -> [Move]

So I can do this Hanoi 2 a b

Should it be, hanoi :: Integer -> Peg -> Peg -> Peg -> [Move] ? So, hanoi n a b c hanoi 2 "a" "b" "c" - You have n disks at 'a' peg in right order(bigger is on bottom). - n should be >= 2. - You have to move all disk from 'a' to 'b'. - You can use 'c' as your temporary place. I've done this as, - write 'hanoi 2 "a" "b" "c" - write 'hanoi 3 "a" "b" "c" - write 'hanoi 4 "a" "b" "c" - find some common pattern

...

I do not see how I can tell that the disk can move from a to b

Output of hanoi is 'move plan'. It does not actually do somthing. [ ("a", "b") , ("a", "c") ] means, - move disk on top of "a" peg to "b" - move disk on top of "b" peg to "c"

3753

Age (days ago)

3754

Last active (days ago)

List overview

Download

7 comments

5 participants

participants (5)

Dudley Brooks
Julian Birch
Mike Meyer
Roelof Wobben
YCH