Python Programming Homework

4612 days ago by medlock

Python Programming Homework

Professor Warner gave us the Stack class. (A stack is a Last-In, First-Out (LIFO) data structure.)

(I modified it slightly.)

class Stack: '''Python class for a generic Stack (Last-In, First-Out data structure).''' def __init__(self): 'Initialize an empty Stack.' self._s = [] def isEmpty(self): 'Check if the Stack is empty.' return (len(self._s) == 0) def push(self, x): 'Add a value to the end of the Stack.' self._s.append(x) def pop(self): 'Remove and return the value at the end of the Stack.' if not self.isEmpty(): return self._s.pop() else: return None def peek(self): 'Return the value at the end of the Stack *without removing it*.' if not self.isEmpty(): return self._s[-1] else: return None def __repr__(self): 'This makes printing of the Stack do the right thing.' return repr(self._s) 
       

Testing the Stack class:

s = Stack() print s # prints '[]' for the empty Stack s.push(3) # s = [3] s.push(2) # s = [3, 2] s.push(27) # s = [3, 2, 27] print s # prints '[3, 2, 27]' s.pop() # removes the last element, 27 print s # prints '[3, 2]' 
        
[]
[3, 2, 27]
[3, 2]
[]
[3, 2, 27]
[3, 2]

Problem #1: A Queue Class

Using the structure of the Stack class, write a Queue class (a First-In, First Out (FIFO) data structure).

Note that 'pop()' in used in Stack removes the last element from a list, while 'pop(0)' instead removes the first element.

# Your Queue class goes here! 
       

Test your Queue class.

q = Queue() print q # prints '[]' for the empty Queue q.push(3) # q = [3] q.push(2) # q = [3, 2] q.push(27) # q = [3, 2, 27] print q # prints '[3, 2, 27]' q.pop() # removes the first element, 3 print q # prints '[2, 27]' 
       

Problem #2: Towers of Hanoi

The Towers of Hanoi is a classic problem that can be solved by a simple algorithm.

Towers of Hanoi toy From the Wikipedia entry:

The Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

  • Only one disk may be moved at a time.
  • Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
  • No disk may be placed on top of a smaller disk.

We can solve this programmatically by thinking of each rod as a Stack. The last element in is the disk on top, and it must be the first one out.

Below is setting up 3 Stacks, one representing each rod, and filling rod #1 with 4 disks, where the disk labeled 4 is the largest and the disk labeled 1 is the smallest.

numberOfDisks = 4 rod1 = Stack() rod2 = Stack() rod3 = Stack() for j in range(numberOfDisks, 0, -1): rod1.push(j) print rod1, rod2, rod3 
        
[4, 3, 2, 1] [] []
[4, 3, 2, 1] [] []

This function moves the top-most disk from the source rod to the top-most position on the destination rod.

It does a bunch of error checking to make sure you haven't tried to move a disk from an empty stack or move a disk onto a rod with a smaller one below.

def moveOneDisk(sourceRod, destinationRod): '''Moves the top disk from the source rod to the top of the destination rod. Does error checking to make sure the source rod is not empty and that the disk to be moved is smaller than the disk on top of the destination rod, if there is one.''' if sourceRod.isEmpty(): # Raises an error and stops raise ValueError('Source Rod is empty!') else: # Check that the disk we're supposed to move # is not bigger than the disk on top of destination if (not destinationRod.isEmpty()) and (destinationRod.peek() < sourceRod.peek()): # Raises an error and stops raise ValueError('Target Disk is bigger than the Disk on top of Destination Rod!') else: # Move the disk from source to destination disk = sourceRod.pop() destinationRod.push(disk) 
       
Let's see how this works...
# Set up 2 new rods, one with 2 disks and one empty testSourceRod = Stack() testDestinationRod = Stack() testSourceRod.push(2) testSourceRod.push(1) print testSourceRod, testDestinationRod 
        
[2, 1] []
[2, 1] []
# Try to move a disk from the empty rod to the other one moveOneDisk(testDestinationRod, testSourceRod) 
        
Traceback (click to the left of this block for traceback)
...
ValueError: Source Rod is empty!
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_258.py", line 10, in <module>
    exec compile(u"print _support_.syseval(python, u'# Try to move a disk from the empty rod to the other one\\nmoveOneDisk(testDestinationRod, testSourceRod)', __SAGE_TMP_DIR__)" + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/home/medlock/sage-4.5.3/local/lib/python2.6/site-packages/sagenb-0.8.2-py2.6.egg/sagenb/misc/support.py", line 473, in syseval
    return system.eval(cmd, sage_globals, locals = sage_globals)
  File "/home/medlock/sage-4.5.3/local/lib/python2.6/site-packages/sage/misc/python.py", line 56, in eval
    eval(z, globals)
  File "", line 1, in <module>
    
  File "", line 9, in moveOneDisk
    
ValueError: Source Rod is empty!
# Move the top disk to the empty rod moveOneDisk(testSourceRod, testDestinationRod) print testSourceRod, testDestinationRod 
        
[2] [1]
[2] [1]
# Try to move the next disk moveOneDisk(testSourceRod, testDestinationRod) 
        
Traceback (click to the left of this block for traceback)
...
ValueError: Target Disk is bigger than the Disk on top of Destination
Rod!
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_260.py", line 10, in <module>
    exec compile(u"print _support_.syseval(python, u'# Try to move the next disk\\nmoveOneDisk(testSourceRod, testDestinationRod)', __SAGE_TMP_DIR__)" + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/home/medlock/sage-4.5.3/local/lib/python2.6/site-packages/sagenb-0.8.2-py2.6.egg/sagenb/misc/support.py", line 473, in syseval
    return system.eval(cmd, sage_globals, locals = sage_globals)
  File "/home/medlock/sage-4.5.3/local/lib/python2.6/site-packages/sage/misc/python.py", line 56, in eval
    eval(z, globals)
  File "", line 1, in <module>
    
  File "", line 15, in moveOneDisk
    
ValueError: Target Disk is bigger than the Disk on top of Destination Rod!

A very tidy way to solve this problem is recursively. The following algorithm moves n disks from rod A to rod B:

  • move n - 1 disks from A to C.
  • move the last disk, disk #n, from A to B.
  • move n - 1 disks from C to B.

The trick to recursive programming is to define a function that calls itself to solve a sub-problem. The problems keeps getting chopped up into sub-problems. (Move 4 disks is chopped into move 3 disks and move 1 disk; the move 3 disk part is chopped into move 2 disks and move 1 disk...) The recursion should keep chopping the problem up until, at the bottom, the smallest sub-problems are trivial to solve.

Write a function that implements the above recursive algorithm, making use of the above function 'moveOneDisk' to do the middle step.

To see what is going on, put 'print rodA, rodB, rodC' just before and just after the middle step.

def moveManyDisks(number, rodA, rodB, rodC): if #someCondition#: # Do nothing pass else: # Do stuff # ... print rodA, rodB, rodC moveOneDisk(rodA, rodB) print rodA, rodB, rodC # Do more stuff # ... 
       

Test your recursive function by solving the puzzle with 4 disks.

The first output is '[4, 3, 2, 1] [] []'.
The last output should be '[] [] [4, 3, 2, 1]' if you solved the puzzle.

numberOfDisks = 4 rod1 = Stack() rod2 = Stack() rod3 = Stack() for j in range(numberOfDisks, 0, -1): rod1.push(j) print rod1, rod2, rod3 moveManyDisks(numberOfDisks, rod1, rod3, rod2) print rod1, rod2, rod3 
        
[4, 3, 2, 1] [] []
[4, 3, 2, 1] [] []
[4, 3, 2] [] [1]
[4, 3, 2] [] [1]
[4, 3, 2, 1] [] []
[4, 3, 2, 1] [] []
[4, 3, 2] [] [1]
[4, 3, 2] [] [1]