New Exercise Proposal: Tower of Hanoi

Exercism Building Exercism
1

After the positive response to the new “Camicia” exercise, I got carried away looking for ideas for new exercises.

I saw that there was already a topic open for this idea, but I thought about it before reviving a thread from two years ago. (thanks to the pop-up)

There are several ways to implement this exercise, each with its own purpose. Here are a few:

  1. Classic Tower of Hanoi (3 poles, n discs)
    I don’t think there’s any need for introductions. Anyone who has never tried to create their first recursive algorithm with this game has missed out on a piece of their childhood. I think it’s a milestone in realising how complex a topic can be, which, after seeing the solution, can become trivial (or not in my case).
    That said, four years after seeing it for the first time, I can say that I don’t remember anything AHAH.

  2. General Tower of Hanoi (k poles, n discs)
    I investigated further, and as reported in the old topic, there is the Reve’s puzzle.
    Similar to the Tower of Hanoi game, the puzzle is generalised to k>=4 poles and n discs.
    The solution to this exercise, finding the minimum number of moves, is given by the Frame–Stewart algorithm, which has not yet been proven and verified to be optimal, but remains an unproven conjecture.
    Here we reconnect with the world of research in the field of game theory.
    You can find many papers on this topic; there is no single main resource from which to draw information.

  3. Shortest path between positions A and B (3 poles, n discs)
    Known as the Sierpiński triangle, TOH can be represented using this interesting mathematical diagram.
    The idea is to find the shortest path to reach state B from state A in the game.
    There aren’t many exercises on path finding on this platform, so I think it would be a nice addition.

Let me know what you think.
It’s been two years since the last time, and maybe the general opinion on this has changed.

If you have any other types of exercises you want to implement, feel free to create a new topic about it and tag me.
I’ll be very happy to investigate and find new exciting challenges.
It could easily become my hobby LOL.

Other relevant links:

2

I’m not entirely sure what we’d want students to implement and to test here. Return the final state? And set of steps that moves from a start state to an end state? The minimum number of steps by implementing a specific algorithm?

Most of the exercises have a very clear mapping from input to an exact expected output. Most of the exercises do not impose any specific implementation.

3

The exercise could be to return the number of steps to take and then that’s it. That leaves you free to implement one of the few optimal strategies.

4

In my opinion, all three exercises could simply return the minimum number of steps, or make a list of minimum paths taken (using the Sierpiński triangle in case 3, there may be multiple minimum paths).

I am leaning towards implementing case 3, as it is simpler and more feasible for the student.
Case 1 can be solved with a simple formula of 2^n -1, and case 2 is perhaps very complicated and there is no real solution for now (we would have to test all the minimums manually and tell the user that this is the minimum we found).

5

I think it is an exercise where we cannot propose tests in canonical-data like dot-dsl, hangman, lens-person, or tree-building. And I think that is why the former thread didn’t result in a PR - there is nothing one may test for.

1 Like
6

I think that being solvable with a simple formula is not a problem. Both functions in difference of squares can be solved with a simple mathematical formula, the same happens with grains. There might be other examples I don’t remember now.

I don’t think we should be discouraged by the exercise being too simple, because most easy exercises are.

The classic tower of hanoi is usually a good introduction to recursion. Any exercise can be solved with recursion and we have a few which are more intuitive with it (like binary search tree). But of the easy ones I don’t remember right now one which focus on that (the same way, for instance, allergies focus on bitwise ops although it can be solved in other ways).

So, I’d go for it.

7

We (old maintainers) have decided a while back (years) that we will not add more exercises implementing a specific algorithm, unless it’s “vital” / “core” / “very interesting”. For example, doing a Dijkstra / a* / jump* algo correctly is very interesting, but a “Fisher–Yates shuffle” less so.

I am inclined to not be in support of adding an exercise adding a specific algorithm to solve a relatively generic problem. Then again, I am only one person :hugs:

1 Like
8

But does the tower of hanoi implement a specific algorithm (like for instance sieve does)? It can be solved either recursively or iteratively and there are probably many other ways to solve it, like simulating all the steps for instance.

9

This is why I am recommending testing for minimum number of steps to solve, not intermediary states.

The latter would fixate on a specific implementation.

3 Likes
10

Yes, I agree with you. I’d go for the classic exercise, 3 poles with n discs. The tests would be different values for n and the result would be minimum number of steps.

12

Note, the solution here would be 2^n - 1. I’m not sure asking people to solve the number of steps for a 3-pole Tower of Hanoi is very interesting or different from the existing Grains exercise.

13

But the steps to reach this result are different, no? As far as I know, they are very different problems.

Of course, one can “cheat” and just answer 2^n - 1, but this is not much different than solving zebra puzzle by returning the nationality of the people, or stuff like that.

On grains, however, there’s no further step, the very nature of the problem is to return the power of two, at least in one of the functions.

14

Grains can be solved using a loop and calculating steps one by one, as well :) Often that’s not how it is solved, though.

Plenty of community solutions for Zebra just return the solution, too!

2 Likes
15

To sum up.

The problem with the ‘cheated’ solution 2^n - 1 is also present in other exercises (zebra or others).
A good student will certainly try to do the exercise properly.

We can do the exercise with 3 poles and n discs, testing only the minimum number of moves.
We implement the tests by increasing by 1 at a time until we get a long one.
When the student gets to that point, they will say:
“Wow! That takes a really long time! Let’s see if there’s a better solution.”

Changing the subject, it would be useful for me to know which topics you prefer for the new practice exercises. Do you prefer strange and curious things rather than actual algorithms?
For example, I hated the various recursive nursery rhymes with all my heart, haha.
I’m sure there was more than one. :joy:

16

Haha yeah we definitely do not need another one.

I think the most interesting things are those exercises that explore new concepts across languages, but they don’t need to be concept exercises. Advent of Code often explores interesting things.

We have very little exercises on multi-threading (specifically mutexes, semaphores, memory barriers, thread-local variables, synchronisation), memory stuff (mostly for the low-level languages such as C and Rust) – e.g. do a string reversal in constant space (although THAT by itself isn’t interesting), and other less-common concepts.

That said, any exercises that practices a concept (just pick a language with a concept tree / learning mode and go from there) will generally work, and they can be made interesting by matching some real-life domain, such as the resistor series which are based on actual resistors. That also means that non-gotcha interview questions would be interesting to exercisfy by adding a good story. The gotcha-ones are just stupid and shouldn’t be considered.

And yes, every once in a while a “strange and curious” thing is great to have! Bob for example is absolutely cray cray.

1 Like
17

Out of the basic data structures, I believe the only one without a specific exercise is the priority queue/heap. It’d be nice to have something for it.

But overall I’d go for anything curious, puzzling or just interesting/with a good story.

18

Maybe it would be worthwhile if someone could demonstrate different ways of solving the exercise? That way we get a better feel for what a solution would look like.

1 Like
19 
#Recursive
def toh(n , source, destination, auxiliary):
    if n==1:
        return 1
    return toh(n-1, source, auxiliary, destination) + 1 + toh(n-1, auxiliary, destination, source)
     
print(toh(3,'A','B','C')) # 7
print(toh(4,'A','B','C')) # 15
print(toh(5,'A','B','C')) # 31

#Iterative
def toh(n, source, target, auxiliary):
    move_count = 0
    stack = [(n, source, target, auxiliary)]

    while stack:
        cur_n, s, t, a = stack.pop()
        if cur_n == 1:
            move_count += 1
        else:
            stack.append((cur_n - 1, a, t, s))  # third: move (n-1) from aux -> target
            stack.append((1, s, t, a))          # middle: move the largest disk
            stack.append((cur_n - 1, s, a, t))  # first: move (n-1) from source -> aux

    return move_count

print(toh(3,'A','B','C')) # 7
print(toh(4,'A','B','C')) # 15
print(toh(5,'A','B','C')) # 31

#Iterative with poles
def toh(n, source, target, auxiliary):
    poles = {source: list(range(n, 0, -1)), target: [], auxiliary: []}
    move_count = 0
    stack = [(n, source, target, auxiliary)]

    while stack:
        cur_n, s, t, a = stack.pop()
        if cur_n == 1:
            disk = poles[s].pop()
            poles[t].append(disk)
            move_count += 1
        else:
            stack.append((cur_n - 1, a, t, s))  # third: move (n-1) from aux -> target
            stack.append((1, s, t, a))          # middle: move the largest disk
            stack.append((cur_n - 1, s, a, t))  # first: move (n-1) from source -> aux

    return move_count, poles

print(toh(3,'A','B','C')) # (7, {'A': [], 'B': [3, 2, 1], 'C': []})
print(toh(4,'A','B','C')) # (15, {'A': [], 'B': [4, 3, 2, 1], 'C': []})
print(toh(5,'A','B','C')) # (31, {'A': [], 'B': [5, 4, 3, 2, 1], 'C': []})

If you want, I can also do the minimum path exercise with Sierpinski’s triangle.
(Poles in state X&Y, find the minimum number and/or a list of moves made)

20

I’m not sure why, but I find it hard to judge this exercise. What do others think?

21

Given the lack of interest, shall we close the topic?