[Haskell-beginners] tower of hanoi problem

[Mike Meyer]

On Sat, Feb 14, 2015 at 6:43 AM, Roelof Wobben <r.wobben at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20150214/4b357ebe/attachment.html>