Software Design Spring 2007 For Wednesday: 1) Read Chapter 17 of Ousterhout's "Tcl and the Tk Toolkit" http://wb/sd/code/ouster94chapter17.pdf For Thursday: 1) project proposal! No lateness -- give me what you've got. (if you started early, give me a status report.) Exam next Monday 2 April. hw07 solutions -------------- wb/sd/solutions/PokerHand.py You had some flexibility in your definition of some of the hands. a) If a hand has three of a kind, does it have a pair? b) If a hand has a straight and a pair, does it count toward the pair tally? One possibilty is to classify each hand according to its "best classification", so that every hand contributes to only one classification. This allows us to answer questions about actual poker games. But what if we didn't know the order of classification and wanted to derive it? Then we would want to apply every possible classification to each hand and count the number of times each label appears. Either one is fine for this homework; I did the second one. 700000 hands dealt: straightflush happens one time in 3571.43 fourkind happens one time in 601.89 fullhouse happens one time in 38.34 flush happens one time in 32.36 straight happens one time in 20.79 threekind happens one time in 13.02 twopair happens one time in 3.76 pair happens one time in 1.27 highcard happens one time in 1.00 So the rankings are right, but if you've got a flush, watch out for the boat! Hist ---- In my solution, I used Hist extensively class Hist(dict): """a histogram is a dictionary that maps from each item (x) to the number of times the item has appeared (frequency, f) """ def __init__(self, seq=[]): # is this safe? "create a new histogram starting with the items in seq" for x in seq: self.count(x) def count(self, x): "increment the counter associated with item x" self[x] = self.get(x, 0) + 1 For each hand, I formed two histograms and a sorted list of rank frequencies: def make_histograms(self): """computer self.suits (a histogram of the suits in the hand), self.ranks (a histogram of the ranks), and self.sets, a sorted list of the rank sets in the hand """ self.suits = Hist() self.ranks = Hist() for c in self.cards: self.suits.count(c.suit) self.ranks.count(c.rank) self.sets = self.ranks.values() self.sets.sort(reverse=True) Most of the classification functions are variations on check_sets: def check_sets(self, *t): """check whether self.sets contains sets that are at least as big as the requirements in t """ for need, have in zip(t, self.sets): if need > have: return False return True def has_pair(self): return self.check_sets(2) def has_twopair(self): return self.check_sets(2, 2) # 4 kind is not 2 pair def has_threekind(self): return self.check_sets(3) def has_fourkind(self): return self.check_sets(4) def has_fullhouse(self): return self.check_sets(3, 2) has_straight is a little tricky: def has_straight(self): # make a copy of the rank histogram before we mess with it ranks = self.ranks.copy() ranks[14] = ranks.get(1, 0) # keep track of how many consecutive ranks we have seen. # if it gets to 5, we win! count = 0 for i in range(1, 15): if i in ranks: count += 1 if count == 5: return True else: count = 0 return False Checking for a straight flush was probably the hardest. Here are two solutions. The first is an adapation of the same technique has_straight uses. def has_straightflush(self): # make a set of (rank,suit) tuples s = set() for c in self.cards: s.add((c.rank, c.suit)) # why two parens? if c.rank == 1: s.add((14, c.suit)) # look for five in a row for suit in range(4): count = 0 for rank in range(1, 15): if (rank, suit) in s: count += 1 if count == 5: return True else: count = 0 return False The second solution partitions the hand into 4 subhands: def has_straightflush(self): # make a dictionary that maps from suit to Hand d = {} for c in self.cards: d.setdefault(c.suit, PokerHand()).add_card(c) # check each sub-hand for a straight for hand in d.values(): if len(hand.cards) < 5: continue hand.make_histograms() if hand.has_straight(): return True return False The second solution is shorter and more provably correct. Finally, here is the code that applies the labels: def classify(self): self.make_histograms() self.labels = [] for label in PokerHand.labels: f = getattr(self, 'has_' + label) if f(): self.labels.append(label) And here is the code that keeps count: lhist = Hist() # the label histogram # loop n times, dealing 7 hands per iteration n = 10000 for i in range(n): if i%1000 == 0: print i deck = PokerDeck() deck.shuffle() hands = deck.deal_hands(7, 7) for hand in hands: for label in hand.labels: lhist.count(label) Object invariants ----------------- Precondition: all of the classification methods require a valid histogram There are three ways to handle this kind of dependency: 1) document the precondition the burden is on the user to guarantee the precondition, where "the user" means other programmers that use these methods. + simple, no extra code required + acceptable for private functions/methods - complicates the interface - error-prone 2) guarantee that the precondition always holds a condition that must always be true is called an invariant. make sure that the __init__ method creates a valid histogram make sure that all modifiers update the histogram + least error-prone + requires no additional code in the classifier methods - possibly hard to implement - possibly inefficient 3) compromise: guarantee that the histogram is valid or None initially it's None the first classifier builds the histogram, the rest find it valid all modifiers set the histogram to None + histograms only computed when needed - have to add code to each classifier method