CS21 Lab 5: More Advanced Functions

Due Saturday, Oct 12, before midnight

As you write programs, use good programming practices:

Use a comment at the top of the file to describe the purpose of the program (see example).
All programs should have a main() function (see example).
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.
Avoid writing any lines of code that exceed 80 columns.
- Always work in a terminal window that is 80 characters wide (resize it to be this wide)
- In vscode, at the bottom right in the window, there is an indication of both the line and the column of the cursor.

Function Comments

All functions should have a top-level comment! Please see our function example page if you are confused about writing function comments.

Goals

More practice writing programs with multiple functions.
Perform input validation using indefinite while loops.
Index into lists.
Write functions that mutate lists.

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 solution.

$ 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.

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.

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.

For each function that you write, provide a comment that describes its purpose, parameters, side effects, and return value.

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 — print `"Invalid tower!"` and then repeat the prompt 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 — print "Invalid tower!" and then repeat the prompt 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.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

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']

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.

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.

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.

Strategy and Tips

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.

Requirements

The code you submit for labs is expected to follow good style practices, and to meet one of the course standards, you’ll need to demonstrate good style on six or more of the lab assignments across the semester. To meet the good style expectations, you should:

Write a comment that describes the program as a whole using a comment at the top of the file.
All programs should have a main() function.
Use descriptive variable names.
Write code with readable line length, avoiding writing any lines of code that exceed 80 columns.
Write a comment for each function (except main) that describes its parameters, return value, and purpose.
(If applicable) Add comments to explain complex code segments.

Your program should meet the following requirements:

Your program should implement the print_towers function with the same number of parameters and behavior described above.
Your program should implement the get_tower function with the same number of parameters, return type, and behavior described above.
Your program should implement the validate_move function with the same number of parameters, return type, and behavior described above.
Your program should implement the move_disk function with the same number of parameters and behavior described above.
Your program should implement the check_victory function with the same number of parameters, return type, and behavior described above.
The program should continue prompting the user to make additional moves until the victory condition (the disks are stacked in order on tower C) has been reached (or the user enters quit). Upon reaching the victory condition, the program should print a victory message and exit.

Your solution should be contained within a main function that you call at the end of your program.

Autograder

The autograder for lab 5 tests your functions independently from one another. That is, calls your functions with known inputs and checks to see if it gets the expected outputs. If a function is failing test cases, you can use (temporarily) use your main function to focus on testing that specific function to debug it.

The autograder does not test the program as a whole, so you should still test that your main function by holistically playing the game to ensure that you’ve put the pieces together correctly!

(Optional) Extra Challenge

If you work on this extra challenge, please leave the original version of print_towers for compatibility with the auto-grader.

Write an advanced tower printing function, print_towers_advanced, 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.

Answer the Questionnaire

After each lab, please complete the short Google Forms questionnaire. Please select the right lab number (Lab 05) from the dropdown menu on the first question.

Once you’re done with that, you should run handin21 again.

Submitting lab assignments

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.

Logging out

When you’re done working in the lab, you should log out of the computer you’re using.

First quit any applications you are running, including your vscode editor, the browser and the terminal. Then click on the logout icon ( or other logout icon ) and choose "log out".

If you plan to leave the lab for just a few minutes, you do not need to log out. It is, however, a good idea to lock your machine while you are gone. You can lock your screen by clicking on the lock xlock icon. PLEASE do not leave a session locked for a long period of time. Power may go out, someone might reboot the machine, etc. You don’t want to lose any work!