The main learning goals for this lab is to give you experience
working with lists and defining, calling, and testing functions.
Some of your functions will call other functions (which might
even themselves call other functions!) To achieve these
learning goals, you will implement a puzzle game called
The
Towers of Hanoi.
First, run update21 to get the template files we
have provided for you. These will serve as starting points for
your programs. Next, use cd to change into
your cs21/labs/06 directory and begin working on the
Python programs for this lab. The pwd command helps
you verify that you are in the correct sub-directory.
$ update21
$ cd cs21/labs/06
$ pwd
/home/your_user_name/cs21/labs/06
We will only grade files submitted by handin21 in
this directory, so make sure your programs are in this
directory!
Introduction
For this lab assignment, you will write a single program that
implements a famous puzzle
called The
Towers of Hanoi.
This puzzle consists of three rods along with a
certain number of disks. Each disk has a diferent size. The
disks on each rod are stacked, as shown in the picture. Disks
can be moved from any rod to any rod, subject to the following
rules:
- Disks must be moved one at a time.
- Only the top disk on a rod can be moved.
- No disk may be placed on top of a smaller disk.
Initially, all disks are on the first rod, as shown in the
picture above. The goal of this puzzle is to make a series of
moves so that all disks are on the third rod.
For this lab, you will write a program representing the Towers
of Hanoi puzzle. You will need to maintain all the
information needed to play this puzzle, and you will let the
user make moves and solve this puzzle.
(Note: you do
not need to write a program that solves this puzzle,
only one that lets the user play this puzzle.)
Using the graphics library is NOT required, but is an
optional extension.
Python: List operations and helper
functions
Open the program hanoi.py and work incrementally
towards implementing this puzzle.
In this lab, you should represent disks as
integers 1,2,...,ndisks, where ndisks is the
number of disks in the puzzle, and smaller numbers represent
smaller disks. In addition to the disks, you should represent
each rod as a list of positive integers, representing the
disks that are on this rod. The integer at the end of the
list represents the disk on top, while the disk at the
beginning of the list represents the disk on the bottom of the
rod.
Hint: how will you maintain this state? Recall
that L[-1] returns the last element in a list.
Hint: Feel free to use any list method that you find
in the Python documentation. In particular, the append
and pop methods might be useful. append adds
an element to a list. pop removes the last element
from the list and returns the element. Sample code for these
function calls lies below:
L = ["Jeff","Lisa"]
L.append("Joshua") # adds "Joshua" to end of list L
...
print(L.pop()) # removes "Joshua" from L, returns "Joshua"
For this lab, you will need to implement several helper
functions which use lists, as well as a main program
that calls the helper functions and implements functionality
of the Towers of Hanoi puzzle. To help you out, we specify
the functions you'll need to implement and some structure for
incremental development below.
All of your functions should include a comment describing the
behavior of the function, the parameters and the return value.
Python: helper functions
-
Initially, main should only be used to call a test()
function, which takes no inputs. This test() function should
be used to test each of the helper functions you are required to write
below. You should develop and test your program incrementally; that
is, you should write each function one at a time, then test that
function, before moving on to the next function. Keep this practice
up until you have written all of the functions.
Note: do not delete your test() function. While in
your final implementation, your main function should not
call test(), we will look at this function to see how
thoroughly you tested your helper functions.
- getInt takes a prompt string and two
integers low and high and asks the user to enter an
integer between low and high (inclusive) using that
prompt. The function repeats the prompt until the user enters a valid
integer in the range, and returns the first valid integer entered by
the user. Your function should use try/except to
validate that the user enters only integers, along with an if
statement to validate the user enters an integer in the proper range.
>>> ndisks = getInt("How many disks do you want?", 1, 100)
How many disks do you want? -4
Please enter an integer between 1 and 100.
How many disks do you want? 101
Please enter an integer between 1 and 100.
How many disks do you want? 100
- Create a boolean function diskMovable(disk, rod1, rod2,
rod3) that takes an integer disk and three lists of
integers rod1,rod2,rod3 representing the state of each rod in
the program. This function should return True
if disk is on top of one of the three rods. Remember,
the top disk on a rod corresponds to the last integer in the list.
Example function calls lie below:
result = diskMovable(5, [], [5,4,3,2,1], []) # returns False
result = diskMovable(5, [4,3], [2,1], [5]) # returns True
- Create a function getValidMove(ndisks, rod1, rod2, rod3).
This function has four parameters: an integer ndisks
representing the total number of disks in the puzzle, as well as three
lists of integers representing the state of each rod. Similar
to getInt, getValidMove repeatedly asks the user for
a disk, and checks to see if the disk can be legally moved. If it can
be moved, getValidMove returns this disk. Otherwise, the
function repeats and asks the user for another disk.
Note: when the user enters an invalid disk move, print an
appropriate error message stating why the disk cannot be moved
before prompting the user for another disk choice.
- Create a boolean function checkRod(disk, rod) that takes
a disk and a list representing a rod and returns True if this
disk can be placed on this rod. In addition to
returning False if the disk cannot be placed on this rod, you
should print a simple message stating why the move is not
allowed.
- Create a function getValidRod(disk, rod1, rod2, rod3)
that prompts the user for which rod to move the
given disk to. The function should then verify that it is
possible to move this disk to the chosen rod. If it
is, getValidRod should return the rod number. Otherwise, the
function should repeat until the user enters a valid rod to move the
disk to.
- Create a function move(disk, rodnum, rod1, rod2, rod3) that
changes the state of the rods to move disk from whichever rod
on which it currently lies to rod rodnum. You should already have
verified that moving disk to rod rodnum is a legal move.
- Create a boolean function isGameOver(ndisks, rod1, rod2, rod3)
that returns True if all disks are on the final rod.
- Create a function printState(rod1, rod2, rod3)
that prints the current state of the puzzle.
Python: The main function
Once you have
implemented and tested all of the helper functions listed
above, you are ready to implement the main function.
Your main function should do the following:
- ask the user how many disks they want.
- create an initial puzzle configuration. Initially, the
first rod should hold all disks, and the other two rods should
have none.
- loop coninuously over the following until the user arrives
at a winning game state.
- check to see if the game is over
- print the current game state
- ask the user for a valid disk to move
- ask the user for a valid rod to move this disk to.
- move the chosen disk to the chosen rod. You'll need to
both add this disk to the new rod and remove it from the old
rod.
- print a congratulatory message once the game has finished.
Sample Output
How many disks do you want? 3
Rod 1: [3, 2, 1]
Rod 2: []
Rod 3: []
Game is not over!
Which disk do you want to move? 1
Where do you want to move the disk? 3
Rod 1: [3, 2]
Rod 2: []
Rod 3: [1]
Game is not over!
Which disk do you want to move? 2
Where do you want to move the disk? 3
I'm sorry, you can't place the disk here!
Please try again.
Where do you want to move the disk? 2
Rod 1: [3]
Rod 2: [2]
Rod 3: [1]
Game is not over!
Which disk do you want to move? 1
Where do you want to move the disk? 2
Rod 1: [3]
Rod 2: [2, 1]
Rod 3: []
Game is not over!
Which disk do you want to move? 3
Where do you want to move the disk? 3
Rod 1: []
Rod 2: [2, 1]
Rod 3: [3]
Game is not over!
Which disk do you want to move? 1
Where do you want to move the disk? 1
Rod 1: [1]
Rod 2: [2]
Rod 3: [3]
Game is not over!
Which disk do you want to move? 2
Where do you want to move the disk? 3
Rod 1: [1]
Rod 2: []
Rod 3: [3, 2]
Game is not over!
Which disk do you want to move? 1
Where do you want to move the disk? 3
Rod 1: []
Rod 2: []
Rod 3: [3, 2, 1]
You won!
Extra Challenges
Below are some ideas for some optional extensions to your Towers of
Hanoi implementation.
Note: extra challenges are just for fun (i.e., no bonus points).
Please only attempt them after completing your regular assignment.
- Add a way for the user to quit early, in case they get bored.
Rod 1: [16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4]
Rod 2: [2, 1]
Rod 3: [3]
Which disk do you want to move? -1
quitting the game...
- Change the display so it prints the rods vertically.
How many disks? 3
1
2
3
------
1 2 3
Which disk do you want to move? 1
Where do you want to move it? 3
2
3 1
------
1 2 3
Which disk do you want to move? 2
Where do you want to move it? 2
3 2 1
------
1 2 3
- Use the graphics module to provide a graphical user
interface for your Towers of Hanoi implementation. Instead of
asking the user to enter integers to represent the disk to move and
rod to move to, have the user click on the disk and rod.
Submit
Remember you may run handin21 as many times as you like. Each
time you run it new versions of your files will be submitted. Running
handin21 after you finish a program, after any major changes
are made, and at the end of the day (before you log out) is a good
habit to get into.