## Appendix C

# Complete Python Listings

### Point class

class Point:
def __init__(self, x=0, y=0):
self.x = x
self.y = y
def __str__(self):
return '(' + str(self.x) + ', ' + str(self.y) + ')'
def __add__(self, other):
return Point(self.x + other.x, self.y + other.y)
def __sub__(self, other):
return Point(self.x - other.x, self.y - other.y)
def __mul__(self, other):
return self.x * other.x + self.y * other.y
def __rmul__(self, other):
return Point(other * self.x, other * self.y)
def reverse(self):
self.x, self.y = self.y, self.x
def frontAndBack(front):
from copy import copy
back = copy(front)
back.reverse()
print str(front) + str(back)

### Time class

class Time:
def __init__(self, hours=0, minutes=0, seconds=0):
self.hours = hours
self.minutes = minutes
self.seconds = seconds
def __str__(self):
return str(self.hours) + ":" + str(self.minutes) + ":" + str(self.seconds)
def convertToSeconds(self):
minutes = self.hours * 60 + self.minutes
seconds = self.minutes * 60 + self.seconds
return seconds
def increment(self, secs):
secs = secs + self.seconds
self.hours = self.hours + secs/3600
secs = secs % 3600
self.minutes = self.minutes + secs/60
secs = secs % 60
self.seconds = secs
def makeTime(secs):
time = Time()
time.hours = secs/3600
secs = secs - time.hours * 3600
time.minutes = secs/60
secs = secs - time.minutes * 60
time.seconds = secs
return time

### Cards, decks and games

import random
class Card:
suitList = ["Clubs", "Diamonds", "Hearts", "Spades"]
rankList = [ "narf", "Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10",
"Jack", "Queen", "King"]
def __init__(self, suit=0, rank=0):
self.suit = suit
self.rank = rank
def __str__(self):
return self.rankList[self.rank] + " of " + self.suitList[self.suit]
def __cmp__(self, other):
# check the suits
if self.suit > other.suit: return 1
if self.suit < other.suit: return -1
# suits are the same... check ranks
if self.rank > other.rank: return 1
if self.rank < other.rank: return -1
# ranks are the same... it's a tie
return 0
class Deck:
def __init__(self):
self.cards = []
for suit in range(4):
for rank in range(1, 14):
self.cards.append(Card(suit, rank))
def printDeck(self):
for card in self.cards:
print card
def __str__(self):
s = ""
for i in range(len(self.cards)):
s = s + " "*i + str(self.cards[i]) + "\n"
return s
def shuffle(self):
import random
nCards = len(self.cards)
for i in range(nCards):
j = random.randrange(i, nCards)
[self.cards[i], self.cards[j]] = [self.cards[j], self.cards[i]]
def removeCard(self, card):
if card in self.cards:
self.cards.remove(card)
return 1
else: return 0
def popCard(self):
return self.cards.pop()
def isEmpty(self):
return (len(self.cards) == 0)
def deal(self, hands, nCards=999):
nHands = len(hands)
for i in range(nCards):
if self.isEmpty(): break # break if out of cards
card = self.popCard() # take the top card
hand = hands[i % nHands] # whose turn is next?
hand.addCard(card) # add the card to the hand
class Hand(Deck):
def __init__(self, name=""):
self.cards = []
self.name = name
def addCard(self,card) :
self.cards.append(card)
def __str__(self):
s = "Hand " + self.name
if self.isEmpty():
s = s + " is empty\n"
else:
s = s + " contains\n"
return s + Deck.__str__(self)
class CardGame:
def __init__(self):
self.deck = Deck()
self.deck.shuffle()
class OldMaidHand(Hand):
def removeMatches(self):
count = 0
originalCards = self.cards[:]
for card in originalCards:
match = Card(3 - card.suit, card.rank)
if match in self.cards:
self.cards.remove(card)
self.cards.remove(match)
print "Hand %s: %s matches %s" % (self.name,card,match)
count = count+1
return count
class OldMaidGame(CardGame):
def play(self, names):
# remove Queen of Clubs
self.deck.removeCard(Card(0,12))
# make hands base on names passed
self.hands = []
for name in names : self.hands.append(OldMaidHand(name))
# deal the cards
self.deck.deal(self.hands)
print "---------- Cards have been dealt"
self.printHands()
# Remove initial matches
matches = self.removeMatches()
print "---------- Matches discarded, play begins"
self.printHands()
# Play until all 50 cards matched
turn = 0
numHands = len(self.hands)
while matches < 25:
matches = matches + self.playOneTurn(turn)
turn = (turn + 1) % numHands
print "---------- Game is Over"
self.printHands ()
def removeMatches(self):
count = 0
for hand in self.hands:
count = count + hand.removeMatches()
return count
def playOneTurn(self, i):
if self.hands[i].isEmpty():
return 0
neighbor = self.findNeighbor(i)
pickedCard = self.hands[neighbor].popCard()
self.hands[i].addCard(pickedCard)
print "Hand", self.hands[i].name, "picked", pickedCard
count = self.hands[i].removeMatches()
self.hands[i].shuffle()
return count
def findNeighbor(self, i):
numHands = len(self.hands)
for next in range(1,numHands):
neighbor = (i + next) % numHands
if not self.hands[neighbor].isEmpty():
return neighbor
def printHands(self) :
for hand in self.hands :
print hand

### Linked Lists

def printList(node) :
while node :
print node,
node = node.next
print
def printBackward(list) :
if list == None : return
head = list
tail = list.next
printBackward(tail)
print head,
def printBackwardNicely(list) :
print "(",
if list != None :
head = list
tail = list.next
printBackward(tail)
print head,
print ")",
def removeSecond(list) :
if list == None : return
first = list
second = list.next
first.next = second.next
second.next = None
return second
class Node :
def __init__(self, cargo=None) :
self.cargo = cargo
self.next = None
def __str__(self) :
return str(self.cargo)
def printBackward(self) :
if self.next != None :
tail = self.next
tail.printBackward()
print self.cargo,
class LinkedList :
def __init__(self) :
self.length = 0
self.head = None
def printBackward(self) :
print "(",
if self.head != None :
self.head.printBackward()
print ")",
def addFirst(self, cargo) :
node = Node(cargo)
node.next = self.head
self.head = node
self.length = self.length + 1

### Stack class

class Stack: # Python list implementation
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def isEmpty(self):
return(self.items == [])
def evalPostfix(expr) :
import re
expr = re.split("([^0-9])", expr)
stack = Stack()
for token in expr :
if token == '' or token == ' ':
continue
if token == '+' :
sum = stack.pop() + stack.pop()
stack.push(sum)
elif token == '*' :
product = stack.pop() * stack.pop()
stack.push(product)
else :
stack.push(int(token))
return stack.pop()

### Queues and priority queues

class Queue :
def __init__(self) :
self.length = 0
self.head = None
def empty(self) :
return (self.length == 0)
def insert(self, cargo) :
node = Node(cargo)
node.next = None
if self.head == None :
# If list is empty our new node is first
self.head = node
else :
# Find the last node in the list
last = self.head
while last.next : last = last.next
# Append our new node
last.next = node
self.length = self.length + 1
def remove(self) :
cargo = self.head.cargo
self.head = self.head.next
self.length = self.length - 1
return cargo
class ImprovedQueue :
def __init__(self) :
self.length = 0
self.head = None
self.last = None
def empty(self) :
return (self.length == 0)
def insert(self, cargo) :
node = Node(cargo)
node.next = None
if self.length == 0 :
# If list is empty our new node is first
self.head = self.last = node
else :
# Find the last node in the list
last = self.last
# Append our new node
last.next = node
self.last = node
self.length = self.length + 1
def remove(self) :
cargo = self.head.cargo
self.head = self.head.next
self.length = self.length - 1
if self.length == 0 : self.last = None
return cargo
class PriorityQueue :
def __init__(self) :
self.items = []
def empty(self) :
return self.items == []
def insert(self, item) :
self.items.append(item)
def remove(self) :
maxi = 0
for i in range(1,len(self.items)) :
if self.items[i] > self.items[maxi] :
maxi = i
item = self.items[maxi]
self.items[maxi:maxi+1] = []
return item
class Golfer :
def __init__(self, name, score) :
self.name = name
self.score= score
def __str__(self) :
return "%-15s: %d" % (self.name, self.score)
def __cmp__(self, other) :
if self.score < other.score : return 1 # less is more
if self.score > other.score : return -1
return 0

### Trees

class Tree :
def __init__(self, cargo, left=None, right=None) :
self.cargo = cargo
self.left = left
self.right = right
def __str__(self) :
return str(self.cargo)
def getCargo(self): return self.cargo
def getLeft (self): return self.left
def getRight(self): return self.right
def setCargo(self, cargo): self.cargo = cargo
def setLeft (self, left): self.left = left
def setRight(self, right): self.right = right
def total(tree) :
if tree == None : return 0
return total(tree.left) + total(tree.right) + tree.cargo
def printTree(tree) :
if tree == None : return
print tree.cargo,
printTree(tree.left)
printTree(tree.right)
def printTreePostorder(tree) :
if tree == None : return
printTreePostorder(tree.left)
printTreePostorder(tree.right)
print tree.cargo,
def printTreeInorder(tree) :
if tree == None : return
printTreeInorder(tree.left)
print tree.cargo,
printTreeInorder(tree.right)
def printTreeIndented(tree, level=0) :
if tree == None : return
printTreeIndented(tree.right, level+1)
print ' '*level + str(tree.cargo)
printTreeIndented(tree.left, level+1)

### Expression trees

def getToken(tokenList, expected) :
if tokenList[0] == expected :
tokenList[0:1] = [] # remove the token
return 1
else :
return 0
def getProduct(tokenList) :
a = getNumber(tokenList)
if getToken(tokenList, '*') :
b = getProduct(tokenList)
return Tree('*', a, b)
else :
return a
def getSum(tokenList) :
a = getProduct(tokenList)
if getToken(tokenList, '+') :
b = getSum(tokenList)
return Tree('+', a, b)
else :
return a
def getNumber(tokenList) :
if getToken(tokenList, '(') :
x = getSum(tokenList) # get subexpression
getToken(tokenList, ')') # eat the closing parenthesis
return x
else :
x = tokenList[0]
if type(x) != type(0) : return None
tokenList[0:1] = [] # remove the token
return Tree(x, None, None) # return a leaf with the number

### Guess the animal

def animal() :
# start with a singleton
root = Tree("bird")
# loop until the user quits
while 1 :
print
if not yes("Are you thinking of an animal? ") : break
# walk the tree
tree = root
while tree.getLeft() != None :
prompt = tree.getCargo() + "? "
if yes(prompt):
tree = tree.getRight()
else:
tree = tree.getLeft()
# make a guess
guess = tree.getCargo()
prompt = "Is it a " + guess + "? "
if yes(prompt) :
print "I rule!"
continue
# get new information
prompt = "What is the animal\'s name? "
animal = raw_input(prompt)
prompt = "What question would distinguish a %s from a %s? "
question = raw_input(prompt % (animal,guess))
# add new information to the tree
tree.setCargo(question)
prompt = "If the animal were %s the answer would be? "
if yes(prompt % animal) :
tree.setLeft(Tree(guess))
tree.setRight(Tree(animal))
else :
tree.setLeft(Tree(animal))
tree.setRight(Tree(guess))
def yes(ques) :
from string import lower
ans = lower(raw_input(ques))
return (ans[0:1] == 'y')

### Fraction class

class Fraction:
def __init__(self, numerator, denominator=1):
g = gcd(numerator, denominator)
self.numerator = numerator / g
self.denominator = denominator / g
def __mul__(self, object):
if type(object) == type(5):
object = Fraction(object)
return Fraction(self.numerator*object.numerator,
self.denominator*object.denominator)
__rmul__ = __mul__
def __add__(self, object):
if type(object) == type(5):
object = Fraction(object)
return Fraction(self.numerator*object.denominator +
self.denominator*object.numerator,
self.denominator * object.denominator)
__radd__ = __add__
def __cmp__(self, object):
if type(object) == type(5):
object = Fraction(object)
diff = (self.numerator*object.denominator -
object.numerator*self.denominator)
return diff
def __repr__(self):
return self.__str__()
def __str__(self):
return "%d/%d" % (self.numerator, self.denominator)
def gcd(m,n):
"return the greatest common divisor of 2 integer arguments"
if m % n == 0:
return n
else:
return gcd(n,m%n)