CS21 Lab 5: More Advanced Functions
Written Assignment: Due Friday, October 11, at the start of class
Programming Assignment: Due Saturday, October 12, before midnight
As you write your first programs, start using good programming practices now:
Use a comment at the top of the file to describe the purpose of the program.
Use variable names that describe the contents of the variables.
Write your programs incrementally and test them as you go. This is really crucial to success: don’t write lots of code and then test it all at once! Write a little code, make sure it works, then add some more and test it again.
Don’t assume that if your program passes the sample tests we provide that it is completely correct. Come up with your own test cases and verify that the program is producing the right output on them.
Draw stack diagrams.
Implement a larger program that combines multiple functions.
Write functions that operate on lists.
1. Written Assignment: Stack Diagram
The first part of the lab involves you tracing a program with functions and showing the resulting stack that the function calls generate. This is excellent practice for what will almost certainly be a quiz question! Download the PDF, print it out, and turn it in at the start of class on Friday.
2. Programming Assignment: Tower of Hanoi
For this lab’s programming component, you’ll write several functions to simulate the famous Tower of Hanoi mathematical puzzle game. The game consists of several disks of varying sizes stacked onto one of three rods (A, B, and C). Initially, all the disks are stacked in a pyramid shape (smallest on the top, largest on the bottom) on the leftmost rod (tower A), and the player’s goal is to move the disks one at a time until the entire stack is on the rightmost rod (tower C):
The challenge comes from the game’s three rules:
The player can move only one disk at a time.
The player can only move a disk from the top of a stack.
The player cannot place a larger disk on top of a smaller disk.
Here’s an example of a sequence of moves to solve the game (for our version, we’ll use three disks):
If your browser supports hiding sections, click here to reveal/hide the example.
$ python3 tower.py A: 3 2 1 B: C:
Move disk from tower? A Move disk to tower? C A: 3 2 B: C: 1
Move disk from tower? A Move disk to tower? B A: 3 B: 2 C: 1
Move disk from tower? C Move disk to tower? B A: 3 B: 2 1 C:
Move disk from tower? A Move disk to tower? C A: B: 2 1 C: 3
Move disk from tower? B Move disk to tower? A A: 1 B: 2 C: 3
Move disk from tower? B Move disk to tower? C A: 1 B: C: 3 2
Move disk from tower? A Move disk to tower? C A: B: C: 3 2 1 *** Victory! ***
Take a look at some sample runs for more examples.
2.1. Representing Towers
Your program should store information about a tower (a stack of disks) by
keeping integers in a list, where the value of a integer indicates the size of
a disk. Larger integers represent larger disks (e.g., a
3 represents a large
disk, while a
1 represents a small disk).
You’ll need to keep a separate list for each of the three towers. Lower
indices in a list represent the bottom of the tower, and higher indices
represent the top. For example, to represent the starting state of the game,
main() function should initialize three tower lists like this:
def main(): tower_a = [3, 2, 1] tower_b =  tower_c =  ...
Here, towers B and C are empty. Tower A holds a large disk (3) at the bottom (list index 0), a medium-sized disk (2) in the middle (list index 1), and a small disk (1) at the top (list index 2).
main() function should define these lists and their initial state. As
the program executes,
main() should pass the lists to helper functions to
2.2. Writing Helper Functions
To complete your Tower of Hanoi program, you must write the following
functions, and your implementation must match the specifications given here.
You may write additional functions if you’d like. You should read the function
specifications all the way through and only start programming when you have a
good understanding of how
main() uses each of the other functions.
print_towers(tower_a, tower_b, tower_c): This function takes in the three tower
lists and prints the current status of the disk stacks. For example, in the
starting state of the game, it should print output that looks like:
<-- Note blank line at top for spacing / readability. A: 3 2 1 B: C:
Note: the bottom of the tower corresponds to the left side of the output, nearest the tower letter. Consider using a string accumulator to build each row of output.
get_tower(tower_a, tower_b, tower_c, prompt): This function takes in the
three tower lists and a
prompt string. It should call
input() to prompt
the user for input according to the
prompt string. Depending on what the
user types as input, you should do one of the following:
|user input value||action to take|
"A" or "a"
"B" or "b"
"C" or "c"
"QUIT" or "quit"
exit the program (simply call the
invalid input — repeat the question to the user
Note that you’ll need to use
get_tower() twice for each turn the player
makes. Your prompt should make it clear what your program is asking about:
To retrieve the source tower list based on user input.
"Move disk from tower?"
To retrieve the destination tower list based on user input.
"Move disk to tower?"
validate_move(src, dst): This function takes in two tower lists and
determines whether or not moving a disk from one to the other is valid
according to the game’s rules. Note, it does not move the disk, it just
determines a move’s validity.
src list represents the source tower the
user has selected to move a disk from, and the
dst list represents the
destination tower the user has selected to move a disk to.
For a move to be valid:
The source tower must hold at least one disk (i.e., the
srclist must not be empty).
The destination tower must either be empty, or the disk at the top of the destination tower must be larger than the disk at the top of the source tower.
If a move is valid,
validate_move() should return
True. Otherwise, it
move_disk(src, dst): This function takes in two tower lists and moves a disk
from one to the other. The
src list represents the source tower the user has
selected to move a disk from, and the
dst list represents the destination
tower the user has selected to move a disk to. Your
main() function should
validate a proposed move with
validate_move() prior to calling
Note that the
move_disk() function does not return a value — it just changes
the contents of the list arguments it receives. To move a disk from one tower
to another, you should remove the disk at the end of the source list and append
it to the end of the destination list. Fortunately, Python provides some
convenient list methods for working with items at the end of a list:
new_itemto the end of the list named
listvar. For example:
$ python3 >>> mylist = ["a", "b", "c"] >>> mylist.append("d") >>> print(mylist) ['a', 'b', 'c', 'd']
listvar.pop(): remove the item at the end of the list named
listvarand return it. For example:
$ python3 >>> mylist = ["a", "b", "c"] >>> last_item = mylist.pop() >>> print(mylist) ['a', 'b'] >>> print(last_item) c
Use these two functions to facilitate a disk move between tower lists.
check_victory(tower_a, tower_b, tower_c): This function takes in the three tower
lists and determines whether or not the user has won the game. To win:
Towers A and B must not hold any disks — all the disks must be on tower C.
The disks on tower C must be in order from largest to smallest.
Note: no other orderings should be possible if the game is correctly validating moves to prevent invalid disk stacking. Regardless, it’s a good idea to verify the order to help catch bugs!
If the towers meet the victory conditions,
check_victory() should return
True. Otherwise, it should return
2.3. Writing a Main Function
In the beginning, you should use
main() to incrementally test your individual
helper functions and then gradually build the complete program, similar to
how you worked on lab 04, except instead of using multiple files, you’re using
A finished program might have the primary steps in
main() shown below. Think
about how to use the helper functions to implement each step.
Initialize tower lists.
Until the user has reached a victory state:
Print the current state of the towers.
Prompt the user to input a source and destination tower for the next move.
Validate the move.
If valid, apply the move and check for victory.
Print the final state of the towers and a victory message.
Note: you may assume that the user must make at least one move before reaching a victory state. That is, the game should never start in a victory state.
2.4. Strategy and Tips
It is very important that you think carefully about how each of your functions should be used. Each of the steps in the main function that we have outlined should only need a few lines of code — the helper functions handle most of the complexity.
Additionally, it is incredibly important that you use incremental development. The outline of main is a good starting point — you should complete one step at a time, thoroughly test it to see if your program works, and only move on after getting it to work. The ninjas and instructors will ask you to backtrack and do incremental development if you do not follow this strategy. If you try to implement the whole program at once, you will waste a lot of time and energy trying to fix your program.
For testing certain functionality, it may be helpful to modify the starting
lists. For example, to test the
check_victory() function, you might want to
start with an initial configuration that is only one move away from victory:
def main(): tower_a =  tower_b =  tower_c = [3, 2] ...
This starting configuration will reduce the amount of typing / interaction
required to test
check_victory(). Remember to reset the initial
configuration to the game’s official starting point before submitting your
3. Extra Challenge
Write a version of the
print_towers() function that prints the towers in a
<-- Note blank line at top for spacing / readability. A B C 1 2 3
Hint: When building each line of tower output, consider the contents of the
tower lists in reverse order, since lower indices correspond to the bottom of
the tower. You can iterate over the indices backwards with
>>> for i in range(2, -1, -1): ... print(i) ... 2 1 0
Check the length of a list with
len() to determine whether or not it has an
item in a position before trying to index into it.
4. Answer the Questionnaire
Each lab has a short questionnaire at the end. Please edit
Questions-05.txt file in your
and answer the questions in that file.
Once you’re done with that, run
Turning in your labs….
Remember to run
handin21 to turn in your lab files!
You may run
handin21 as many times as you want. Each time it will
turn in any new work. We recommend running
you complete each program or after you complete significant
work on any one program.