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

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 `exit()` function)
anything else	invalid input — repeat the question to the user

"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 exit() function)

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): append new_item to 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 listvar 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:
1. Print the current state of the towers.
2. Prompt the user to input a source and destination tower for the next move.
3. Validate the move.
4. 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.