This lab involves recursion, which is the ability of a function to call itself.
This is a classic computer science problem which illustrates how recursion coupled with a divide-and-conquer strategy can enable you to trivially solve a problem which appears to be very difficult.
The set-up for the problem is as follows. You have three pegs, on which there are N disks of different sizes. The disks have sizes 1, 2, 3, ... N. All the disks start on the first peg, starting with disk N at the bottom and working consecutively up to disk 1. Your job is to move all the disks to the second peg. You can only move one disk at a time, and a disk can only be moved to an empty peg or to a peg whose top disk is larger than the disk being moved. Disks do not have to be placed on pegs in consecutive order i.e. it's OK to have disk 5 on top of disk 10 (but not on top of disk 4).
The algorithm to solve this problem goes like this. We'll call our pegs peg A, peg B, and peg C. Assume you want to move the top N disks from peg A to peg B.
First, handle the base case i.e. the case that can be solved immediately. Here, the base case is when there is only one disk to move (N = 1). In that case, you just move the disk.
If N > 1, the process is as follows:
Note that steps 1 and 3 involve recursive calls to this algorithm. We call this the recursive case.
Both of these cases should be handled in the same function (method).
Amazingly enough, that's all there is to it. Recursive algorithms may seem like magic, but they can be understood by analogy with mathematical induction. With mathematical induction, you want to prove that something is true for all numbers N > 1. To do this, you prove that it's true for N = 0, and then you show that if it's known to be true for N-1, it can be proven to be true for N. Given that, you can show that it's true for any N > 0. Here, we see that we can move 1 disk (N = 1). If we know that we can move N-1 disks, then it's clear that we can move N disks (that's the recursive case).
Another useful thing to do is to take a small value of N (say 3) and work through the above algorithm on pencil and paper until you convince yourself that it does work.
Write your program in a single file called "hanoi.py" which
will be called as follows:
python hanoi.py <n>
where <n> is the number of disks that start on the first peg. If no number is supplied, the script should print out a usage message and exit as per the instructions in the python style guide.
Since this isn't a standalone script, don't include the
#! /usr/bin/env python
line at the top of the file, and don't make it executable either. This goes for all the upcoming labs as well.
Your program should define a class called Hanoi which
encapsulates all the state variables of the problem. In particular, you
should have an explicit representation of which disks are on which pegs at
any given time. An easy way to do this is to have the pegs be python lists,
and to have the disks be numbers that are stored in the lists in the correct
order. Your Hanoi class should have the following methods:
display, which prints the current state of the problem
(which disks are on which pegs).solve, which solves the problem. solve should
take no arguments.move, which moves one disk from one peg to another. Use an
assert statement to make sure you aren't doing an illegal
operation (e.g. putting a disk on top of a smaller disk, or
duplicating a disk).You will probably want to define other methods as well (e.g. a
helper method for solve() -- hint, hint).
In addition, you should print out the state of the problem (using your
display method) before you start and after each move. The
display should look exactly like this (for 8 disks):
0: 4 1
1: 8 7 6 5
2: 3 2
where 0:, 1:, 2: identify the pegs
and the other numbers identify the disks. Make sure that printouts for
successive moves are separated by at least one blank line.
Your __init__ method should take the total number of disks as
its only argument (other than self, of course) and check that
this number is a positive integer. Raise a ValueError exception
if it isn't, along with a meaningful error message.
Don't forget to read the style guide; in particular, we want you to use docstrings to document classes and functions. Also, don't forget to run your code through the python style checker before you submit it. Starting this week, we're going to be very picky about style violations.
Add code to count the number of moves made when solving the problem. Print this number after you've finished solving the problem. How does this number vary with the number of disks?
Add code to determine the maximum recursion depth reached while solving the problem and print it out. How does this number vary with the number of disks?
Add a command-line option -v (for "verbose") which, if
present, will print out the state of the problem after each move. If it's
not present, the problem will be solved silently. Allow the -v
option to be located anywhere on the command line (as long as it's after the
python hanoi.py arguments, of course).