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
Programming Tips
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.
Goals
-
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! *** |
Sample Runs
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,
your 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).
Your main()
function should define these lists and their initial state. As
the program executes, main()
should pass the lists to helper functions to
manipulate them.
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
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
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" |
return tower_a |
"B" or "b" |
return tower_b |
"C" or "c" |
return tower_c |
"QUIT" or "quit" |
exit the program (simply call the |
anything else |
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.
Prompt:
"Move disk from tower?"
-
To retrieve the destination tower list based on user input.
Prompt:
"Move disk to tower?"
validate_move
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.
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.
For a move to be valid:
-
The source tower must hold at least one disk (i.e., the
src
list 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
should return False
.
move_disk
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 move_disk()
.
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:
-
listvar.append(new_item)
: appendnew_item
to the end of the list namedlistvar
. 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 namedlistvar
and 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
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 False
.
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
one file.
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 = [1]
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
solution.
3. Extra Challenge
Write a version of the print_towers()
function that prints the towers in a
vertical format:
<-- 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 range()
:
>>> 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
the Questions-05.txt
file in your cs21/labs/05
directory
and answer the questions in that file.
Once you’re done with that, run handin21
again.
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 handin21
after
you complete each program or after you complete significant
work on any one program.