Norvig On Programs Design
Python Programs Design¶
Inspired by Peter Norvig's course at Udacity
https://www.udacity.com/course/design-of-computer-programs--cs212
Workflow¶
?? > problem > spec > code
understand specify design
Starting from a relative understanding of a problem/task we specify how things work in the domain of the problem, to design code that solve the problem or realize the task
Barebone¶
- Explain to yourself and in a team the task/problem
- Reach a written/unformal specification of the task, defining sequential sub-tasks or complementary functions to solve the problem
- Design your code to solve tasks and sub-tasks, minding best practices (or design patterns)
- Code
- Iterate with adjustments and tests
Code¶
- write down a function name that realize a sub-task
- write the docstring for the function
- find the best built-in functions or libraries to realize the task in the function (forget optimization for now, try to be idiomatic and use the fittest tools)
- write different functions depending on your style (functional, object oriented)
- Accomplish the task by defining a "main" script that uses the functions
Example¶
We are going to use the example of simulating a Poker game as a playground for a program design:
def poker(hands): # function name
""" Return the best hand: poker([hand, ..]) => hand """ # docstring
return max() # the fittest function to return the maximum value in Python is max()
print(max([3, 4, 5, 0])) # study from the documentation the behaviour of the function
print(max([3, 4, -5, 0], key=abs)) # https://docs.python.org/3.3/library/functions.html#max
A program is a set of functions, classes and operations working to solve/realize the same problem/task
NOTE: Python3 basic built-ins https://docs.python.org/3.3/library/functions.html
Best use of Python design principles¶
Going on we will get familiar with Python design principles and we will know how to use the tools the language provides. Let's see how it is possible by introducing in our design a function to define ranks for hands in a poker game.
NOTE: LPD stands for Leveraging Python Design, in this kind of tip I try to underline how we can design Python programs leveraging peculiar features of Python builtins or language or idioms.
def hand_rank(hand):
""" Return the rank("point") of an hand: hand => rank according to poker rules
ranks = { nothing: 0, pair: 1, double pair: 2, ..., full house: 6, four of a kind: 7, ... } """
return None # by now it is not implemented, see https://youtu.be/WYHN2HfPISY if you want more details
# How can we return the hand with the best ranking from a list of hands
def poker(hands):
""" Return the best hand: [hand, ..] => hand """
return max(hands, key=hand_rank) # use of a custom function as a key for max()
LPD: If we use the 'key' argument in max() we can find the max value coming out from the hand_rank() this is an example of how a Python function fits perfectly to solve a sub-task for our problem.
Testing¶
"To be a good programmer you need to be a good tester".
def test():
""" Test for poker() function """
sf = "6C 7C 8C 9C TC".split() # straight flush
fk = "9D 9H 9S 9C TD".split() # four of a kind
fh = "TC TD TH 9C 9h".split() # full house
assert poker([sf, fk, fh]) == sf
return "test passed"
"one of the secret of testing is to do extreme value".
def test():
""" Test for poker() function """
sf = "6C 7C 8C 9C TC".split() # straight flush
fk = "9D 9H 9S 9C TD".split() # four of a kind
fh = "TC TD TH 9C 9h".split() # full house
assert poker([sf, fk, fh]) == sf
assert poker([sf, sf]) == sf # extreme case, a hand challenging itself
assert poker([sf] + 99*[fh]) == sg # extreme case, a hand challenging 99 other hands
return 'test pass'
This is the starting design for hand_rank():
def hand_rank(hand):
""" Return a tuple describing the hand, to make hands comparable.
kind(), straight() and flush() are not yet implemented, they are functions that spot card ranks.
card_ranks() is not yet implemented also, it turns hands in card ranks (see test()) """
ranks = card_ranks(hand)
if straight(ranks) and flush(hand): # straight flush, (8, higher card, [card, card, card, card, card])
return (8, max(ranks))
elif kind(4, ranks): # 4 of a kind, (7, card, kicker)
return (7, kind(4, ranks), kind(1, ranks))
elif kind(3, ranks) and kind(2, ranks): # full house, (6, higher card, lower card)
return (6, kind(3,ranks), kind(2, ranks))
elif flush(hand): # flush, (5, higher card, [card, card, card, card, card])
return (5, max(hand))
elif straight(ranks): # straight, (4, higher card)
return (4, kind(5, ranks))
elif kind(3, ranks): # 3 of a kind, (3, card, kickers)
return (3, kind(3, ranks),kind(2, ranks))
elif two_pair(ranks): # 2 pair, (...)
return (2, kind(2, ranks), kind(2,ranks), kind(1, ranks))
elif kind(2, ranks): # kind, (...)
return (1, ranks)
else: # high card (...)
return (0, ranks)
def test():
"Test cases for the functions in poker program"
sf = "6C 7C 8C 9C TC".split() # Straight Flush
fk = "9D 9H 9S 9C 7D".split() # Four of a Kind
fh = "TD TC TH 7C 7D".split() # Full House
assert poker([sf, fk, fh]) == sf
assert poker([fk, fh]) == fk
assert poker([fh, fh]) == fh
assert poker([sf]) == sf
assert poker([sf] + 99*[fh]) == sf
assert hand_rank(sf) == (8, 10)
assert hand_rank(fk) == (7, 9, 7)
assert hand_rank(fh) == (6, 10, 7)
assert card_ranks(sf) == [10, 9, 8, 7, 6]
assert card_ranks(fk) == [9, 9, 9, 9, 7]
assert card_ranks(fh) == [10, 10, 10, 7, 7]
return 'tests pass'
LPD: Tuples have been choosen as structure for describing the hands, in general (rank, higher card, tie breakers). Each rank has its own definition. Ranks can be compared using Python's tuples and 'lexigraphical' operators:
print('hello' < 'help') # >>> True
print((8, 5) > (8, 3)) # >>> True
# a straight flush with 5 higher card has an higher rank compared to a straight flush with 3 higher card
LPD: The design choice of using int and tuples to describe ranks and hands sounds good because it leverages tuples comparision and built-in features in max().
From hands to card ranks¶
Let's see how we can add another piece to the puzzle by defining card_ranks():
mapping = { 'T': 10, 'J': 11, 'Q': 12, 'K':13, 'A':14 }
def card_ranks(cards):
"Return a list of the ranks, sorted with higher first (maps faces to integers also, to allow easier comparision)."
ranks = [int(r) if r not in mapping.keys() else mapping[r] for r,s in cards]
ranks.sort(reverse=True)
return ranks
print(card_ranks(['AC', '3D', '4S', 'KH'])) # should output [14, 13, 4, 3]
# Peter Norvig's way to define 'ranks' variable:
# ranks = ['--23456789TJQKA'.index(r) for r,s in cards]
Spot a point in hands¶
Let's see how we can add other functions to the design by defining the methods to spot poker rankings into a ranked hand, stuff like kind(), straight(), flush(), two_pair(). First we add something to our test():
def test():
"Test cases for the functions in poker program"
sf = "6C 7C 8C 9C TC".split() # Straight Flush
fk = "9D 9H 9S 9C 7D".split() # Four of a Kind
fh = "TD TC TH 7C 7D".split() # Full House
assert poker([sf, fk, fh]) == sf
assert poker([fk, fh]) == fk
assert poker([fh, fh]) == fh
assert poker([sf]) == sf
assert poker([sf] + 99*[fh]) == sf
assert hand_rank(sf) == (8, 10)
assert hand_rank(fk) == (7, 9, 7)
assert hand_rank(fh) == (6, 10, 7)
assert card_ranks(sf) == [10, 9, 8, 7, 6]
assert card_ranks(fk) == [9, 9, 9, 9, 7]
assert card_ranks(fh) == [10, 10, 10, 7, 7]
assert straight([9, 8, 7, 6, 5]) == True # new
assert straight([9, 8, 8, 6, 5]) == False # new
assert flush(sf) == True # new
assert flush(fk) == False # new
return 'tests pass'
def straight(ranks):
"Return True if the ordered ranks form a 5-card straight. NOTE: It takes a ranked hands as input"
# Your code here.
ranks = iter(sorted(ranks, reverse=True)) # using iterator protocol
value = next(ranks) # store the current value of iterator
for _ in range(4):
nxt = next(ranks) # get the next element in the iteration
if value - nxt != 1: # if the difference between consecutive elements is more than 1
return False
value = nxt # the next become the current
return True
print(straight([9, 8, 8, 6, 5]))
print(straight([9, 8, 7, 6, 5]))
# Peter Norvig's way:
# def straight(ranks):
# return (max(ranks)-min(ranks) == 4) and len(set(ranks)) == 5
def flush(hand):
"Return True if all the cards have the same suit. NOTE: It takes an hand as input, not the ranked hands"
suit = hand[0][1]
for n, h in hand: # Note the string selection directly in the for loop
if h != suit: return False
return True
print(flush("6C 7C 8C 9C TC".split())) # new
# Peter Norvig's way:
# def flush(hand):
# suits = [s for r, s in hand] # Note the string selection in the for loop
# return len(set(suits)) == 1
def card_ranks(cards):
"Return a list of the ranks, sorted with higher first (maps faces to integers also, to allow easier comparision)."
mapping = { 'T': 10, 'J': 11, 'Q': 12, 'K':13, 'A':14 }
ranks = [int(r) if r not in mapping.keys() else mapping[r] for r,s in cards]
ranks.sort(reverse=True)
return ranks
def test():
"Test cases for spotting cards of the same kind in a hand."
sf = "6C 7C 8C 9C TC".split() # Straight Flush
fk = "9D 9H 9S 9C 7D".split() # Four of a Kind
fh = "TD TC TH 7C 7D".split() # Full House
tp = "TD TH 5C 8H 5H".split()
fkranks = card_ranks(fk)
tpranks = card_ranks(tp)
assert kind(4, fkranks) == 9 # test for 4-of-a-kind
assert kind(3, fkranks) == None # test for 3-of-a-kind
assert kind(2, fkranks) == None # test for 2-of-a-kind
assert kind(1, fkranks) == 7 # test for higher card
assert two_pair(card_ranks(tp)) == (10, 5) # test for two_pair(), to check if there is a double 2-of-a-kind
return 'tests pass'
def kind(n, ranks):
"""Return the first rank that this hand has exactly n of.
Return None if there is no n-of-a-kind in the hand."""
setk = set(ranks)
for item in setk:
if ranks.count(item) == n:
return item
return None
def two_pair(ranks):
"""If there are two pair, return the two ranks as a
tuple: (highest, lowest); otherwise return None."""
if len(ranks) == len(set(ranks)): return None # all cards are different >> return None
two_of = []
for r in ranks:
if ranks.count(r) == 2 and r not in two_of: two_of.append(r)
if len(two_of) == 1: return None
return tuple(two_of)
test()
# Peter Norvig's way:
# def kind(n, ranks):
# for r in ranks:
# if ranks.count(r) == n: return r
# return None
# def two_pair(ranks):
# pair = kind(2, ranks)
# lowpair = kind(2, list(reversed(ranks)))
# if pair and lowpair != pair:
# retutn (pair, lowpair)
# else:
# return None
Testing is never enough¶
All the rankings are up and working, but we need more tests to handle edge cases and exceptions.
This is only Lesson 1!
- How would you handle a straight with Axe low (A, 2, 3, 4, 5)?
- How would you handle ties?
- How would you deal poker hands to simulate a game?
Complete course at Udacity for free.
# https://github.com/faif/python-patterns
# https://github.com/davidcorne/Design-Patterns-In-Python