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!

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:

1. Disks must be moved one at a time.
2. Only the top disk on a rod can be moved.
3. 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.

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.

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

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

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

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

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

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

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

8. Create a boolean function isGameOver(ndisks, rod1, rod2, rod3) that returns True if all disks are on the final rod.

9. Create a function printState(rod1, rod2, rod3) that prints the current state of the puzzle.

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.

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!

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.

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.