Add Towers of Hanoi to the problem-specifications

The Towers of Hanoi problem is an essential one in my opinion that should be tried in every language track.

Maybe for someone who is already a programmer of another language, it might not be interesting, but for those who are learning programming for the first time, I think it’s a very nice one to get started with recursion.

What do you think?

I think that could be a nice exercise to add!

While I agree that Towers of Hanoi is a great exercise - especially for looking at recursive vs non recursive problem solving (and we have it on our practice exercise list for Python at some point down the line) I do want to add/remind that Exercism is not really designed for those learning programming for the first time.

Yes, this does seem like a good idea.

There are various ways to go about this. For example: what would be the desired output? I’m curious to hear all of your thoughts.

@studentenherz this exercise idea is almost an answer to your Default mutable parameter in python thread.

Yes, I thought about if after I came across the mutable parameter issue. But still, it’s not needed that the array is passed along to the recursive calls, although I can see some trying to do so.

Didn’t think of this until now…but have you looked at Pascal’s Triangle?
We recently re-wrote it to be recursive for Python.

The input would be the number of discs (and maybe the number of towers?), the output is the number of moves.

I hadn’t seen that one (I’ve only unlocked about 20 exercises on the track), it might lead to that issue, yes.

Or maybe a list of all the moves. The testing in that case is fairly easy as it could just simulate the moves and check if it gets to the final desired position.

I have never thought of a generalized Towers of Hanoi with more than 3 towers, but it might be interesting for a harder version. :thinking:

For 3 towers (1 full, 2 empty) this is too easy: the answer is always 2**disks - 1 (for moving the entire tower).

Maybe given a starting position and/or a desired end state? This riks making the task too difficult, if the point of the exercise is illustrating recursion. (I haven’t thought too hard on it.)

Huh. TIL that generalized Hanoi is called Reve’s Puzzel, and there are papers written about it. :smile:

I was thinking 3 towers but the input is the starting discs on each tower.

Well, yes, once the concept is understood getting to the initial state of all in one tower is not difficult. But I’m not sure how to assure the most efficient set of steps in that case.

Also, the description of the starting towers should be exhaustive because the relative size of the discs matter.

You can describe any tower state as a list of lists.

Or maybe as a list of integers with each integer representing a height?

Edit: The size of the top disk is needed too.
Edit: No that wouldn’t work either.

Alright, the previous post sounds about right :)