[Haskell-beginners] tower of hanoi problem

[Julian Birch]

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-haskell-for-clojure-programmers.aspx

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 <mwm at mired.org> wrote:

> 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.
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20150214/b19b2bfa/attachment-0001.html>