Tower of Hanoi

LAB9

Welcome

There is a legend that somewhere on Earth, probably in or near Hanoi, or perhaps even somewhere else, a group of monks is moving a tower of 64 cylinders of decreasing size from one rod to a second rod, using a third rod for auxiliary storage. They are required to move only one disk at a time from the top of one rod to the top of another, such that no cylinder may be placed upon a smaller rod.

When the monks finish, the world will end. The monks have been working on this for thousands of years, but are not yet finished, even though they have superpowers and make one move per second! Do you know how long it will take them to complete their task?

We’ll write a program to simulate their work. In doing so, we will encounter a program whose recursive solution is arguably simpler (and easier to understand) than its iterative counterpart. Seriously!

What We Will Learn

Multi-way Recursion Command line arguments Exceptions Raising and Catching Exceptions

Activity

Warming Up

First, let’s practice with the physical wooden blocks tower in the classroom.

Next, read the description of the problem in Wikipedia article on the Tower of Hanoi and take a look at the little animations in the article.

Now, we’re ready to explore via programming. Let’s start with a concrete example. Suppose we wanted to transfer a whole tower of size 5 from rod $A$ to rod $B$. First we have to (ultimately) transfer a tower of size 4 from $A$ to $C$, then move the remaining (largest) disc from $A$ to $B$, then transfer the tower of 4 from $C$ to $B$:

Generating the Move Instructions, Recursively

In general to move $n$ discs from a source rod to a destination rod, you move $n-1$ discs from the source to the auxiliary, then directly move the one disc from source to target, then move $n-1$ from the auxiliary to target. This is recursive! Remember from the last lab how recursion requires a base case? Our base case here is just “if $n=0$, don’t do anything.” When learning how to program, our first thought might be to write:

def move(n, source, destination, auxiliary):
    if n == 0:  # base case
        return
    else:  # recursive case
        move(n - 1, source, auxiliary, destination)
        print(f"Move disk {n} from {source} to {destination}")
        move(n - 1, auxiliary, destination, source)

But the else after the return is actually not considered a good thing. It’s kind of unnecessary, so we should write:

def move(n, source, destination, auxiliary):
    if n == 0:
        return
    move(n - 1, source, auxiliary, destination)
    print(f"Move disk {n} from {source} to {destination}")
    move(n - 1, auxiliary, destination, source)

Finally, here is yet another improvement. Make sure you understand how it does the same thing as the previous iterations, but for one super subtle difference. Can you spot it?

def move(n, source, destination, auxiliary):
    if n > 0:
        move(n - 1, source, auxiliary, destination)
        print(f"Move disk {n} from {source} to {destination}")
        move(n - 1, auxiliary, destination, source)

Create the file ~/cmsi1010/lab09/hanoi.py and copy this final version of the function into it.

You can “test” the code by writing a call such as:

move(3, "A", "B", "C")

Run the program. You should get output like:

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B

We have a nice function that other programmers can use to generate instructions for any number of disks. Now how can we make our program as flexible so that users can get instructions for any number of disks. We can use the Python input function we’ve called in so many previous labs. But there is another way we’ll learn right now.

Command Line Arguments

In each of our previous labs, we’ve run programs with commands such as:

  python zoo.py
  python yapper.py
  python carmen.py

But now, we’re going to learn how to run our tower program like this:

  python hanoi.py 3
  python hanoi.py 7

How is this done? When a Python program is run, the list sys.argv is populated with command line arguments: those things that come after python (or of course, python3 if that’s what you’re running). So, if we entered:

  python hanoi.py dog rabbit "dragon tail" 300

then our program would get the following value in sys.argv:

  ["hanoi.py", "dog", "rabbit", "dragon tail", "300"]

The first item in the list, sys.argv[0] is always the name of the program itself. The rest are the arguments we passed to it. Note that ALL arguments are strings, so if you are expecting numbers, you have to convert them!

Now let’s get our program to get the number of disks from the command line. We first have to import the sys module, so put this at the top:

import sys

Then we can get the number of disks from the command line arguments. But here’s where we have to think like a security engineer. The input is coming from a user. And users can make mistakes. Or be malicious. User input is never to be trusted. You have to think that all user input can be potential threats. Or just plain weird. What we need to do is mentally make a list of all the things that the input can possibly be and categorize them. Here’s the breakdown, intended to be investigated in order:

• 😱 There might not be any arguments at all.
• 😱 There might be more than one argument (and we want exactly one).
• 😱 The argument might not be a number.
• 😱 The argument might be a negative number.
• 😱 The argument might be zero.
• 😱 The argument might be a very large number, which would cause the program to run for a crazy large amount of time and consume computing resources.
• Finally, the nice one: a single positive integer that is not too big so the program runs nicely to completion.

So many things can go wrong, but at least we can test them all in order. But how should we report the errors? The quickest way is to raise an exception. An exception is an object you raise when an error is detected. If an exception is raised, you can handle it:

try:
    if len(sys.argv) != 2:
        raise ValueError("Exactly one argument is required")
    if not sys.argv[1].isdigit():
        raise ValueError("The argument must be a positive integer")
    number_of_disks = int(sys.argv[1])
    if number_of_disks <= 1 or number_of_disks > 20:
        raise ValueError(
            "The argument must be between 1 and 20, inclusive")
    move(number_of_disks, "A", "B", "C")
except ValueError as e:
    print(f"Error: {e}")

We’ll discuss it in class. Make sure to try it out. When you get it working, as always: add, commit, and push.

A Side Exploration on Python Exceptions

Take a moment to evaluate these expressions in the Python REPL:

>>> dog
NameError: name 'dog' is not defined
>>> 1/0
ZeroDivisionError: division by zero
>>> len(5)
TypeError: object of type 'int' has no len()
>>> ["dog","cat","bat"][10]
IndexError: list index out of range
>>> 10.0 ** 1000
OverflowError: (34, 'Result too large')
>>> {"x": 1, "y": 2}["z"]
KeyError: 'z'
>>> int("dog")
ValueError: invalid literal for int() with base 10: 'dog'

You can see that Python has quite a few kinds of exceptions already built-in for you! You can, if you like, create your own kinds of exceptions. We’re not ready to do this yet—we’ll have to learn about classes first.

The naming of exceptions

Yes, Python likes to put the word Error into the names of exceptions, but you know, that is just fine. Just remember an “error” is a generic term for something that is wrong, but an “exception” is a Python object that is raised and can be handled in your program, to, you know, help your users have a good experience.

Final Thoughts

Finally, as this is a laboratory exercise, spend some time thinking about how to implement the Tower program without using recursion. It’s far from obvious. Not like in the last lab. So what’s the difference? It’s mainly that in our new problem there are two recursive calls (and they are not even back-to-back).

Yes, it’s true that there do exist some rather clever non-recursive (sometimes called iterative) Tower of Hanoi solutions out there. You can read about them at Wikipedia but there is absolutely no expectation for you to understand them.

Challenges

Now it’s your turn. Here are some ideas for you to extend the activities above:

• Enhance the program to display move numbers and the total number of moves made.
• Determine the minimum number of (single-disk) moves required to transfer an $n$ disk tower according to the rules.
• Has this kid made the minimum number of moves? Why or why not?

• Enhance the program to display the current state of the rods after each move.

Further Study

Keep up the momentum with some self-study, or study with friends:

• Go back over previous readings in Think Python, 2nd edition, focusing on the Glossary sections, and make notes of anything you missed the first time around that are now making more sense to you.
• Skim Section 8 of the Python Tutorial that covers errors and exceptions. If you see anything particularly interesting, read deeper.

Summary

Recall Practice

Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.

1. What is the Tower of Hanoi legend?
   Monks are moving a tower of 64 disks from one rod to another under explicit rules, using a third rod for auxiliary storage, with the world ending when they finish.
2. What is the recursive solution to the Tower of Hanoi problem?
   To move n disks from source to destination, move n-1 disks to auxiliary, move the nth disk directly, then move the n-1 disks from auxiliary to destination.
3. How do you handle command line arguments in Python?
   Use the sys module and access sys.argv to get the command line arguments passed to the program.
4. What is an exception in Python?
   An exception is an object that is raised when an error occurs, which can be caught and handled to prevent program crashes.
5. What are some common exceptions in Python?
   ValueError, TypeError, IndexError, KeyError, ZeroDivisionError, and OverflowError.
6. How can you improve the Tower of Hanoi program to handle user input safely?
   By checking the number of arguments, ensuring the argument is a positive integer, and raising exceptions for invalid input.
7. Why is it often said that the Tower of Hanoi is a good exemplar of a problem where recursion is easier than iteration?
   There are multiple recursive calls.
8. What is the base case in the Tower of Hanoi recursive solution?
   The base case is when n equals 0, meaning no disks to move.
9. What kinds of checks should be made on the inputs to a Tower of Hanoi function?
   There should be a single input, which should be a integer, which should be positive, and not too large.