Norvig Writes Concise Python

Only a couple weeks ago, I was browsing through Peter Norvig's Sudoku solution, and I was super impressed with his solution. It was short, readable, and really easy to follow.

So, when I heard that he was teaching a course on "Design of Computer Programs" through Udacity, I knew I had to sign up right away. The online course lasts for 7 weeks, and each week's unit consists of a series of short video lessons, with interactive quizzes and very short programming assignments to reinforce the most important concepts. Slightly longer, and more challenging homework problems are handed out at the end of each unit.

All work can be done right in the browser. They provide an interactive code editor, right within the browser (using CodeMirror), which is how you complete the problem sets and submit your work. Once you submit, the Udacity server runs your code and tells you whether you got the problem right.

One nice touch is that the code editor saves your work, so you can start a problem, close the browser, and return to the problem a day later. (Though it would be nice to be able to download the code, or clone it from a git repository, so that it's easier to work offline in the text editor of my choice.)

As for the lessons themselves, they've been excellent. Listening to Norvig talk through his thought process has been eye-opening, and the homework programming assignments have turned into a showcase of how to write concise Python code

It would appear that, on average, I take about 3x as many lines as Peter Norvig to solve any given problem. Here's what I mean:

Example 1: card_ranks()

Mine

def convert_rank(rank):
    rank_map = {'A': 14, 'K': 13, 'Q': 12, 'J': 11, 'T': 10}
    if rank in rank_map:
        rank = rank_map[rank]
    return int(rank)

def card_ranks(cards):
    "Return a list of the ranks, sorted with higher first."
    ranks = [r for r,s in cards]
    ranks = [convert_rank(r) for r in ranks]
    ranks.sort(reverse=True)
    return ranks

Norvig

def card_ranks(hand):
    "Return a list of the ranks, sorted with higher first."
    ranks = ['--23456789TJQKA'.index(r) for r, s in hand]
    ranks.sort(reverse = True)
    return ranks

Sure, my card_ranks() function could be condensed further into a single line comprehension, but it still doesn't compare to his elegance of using the list index, rather than my comparatively clunky convert_rank() function.

Example 2: deal()

Mine

mydeck = [r+s for r in '23456789TJQKA' for s in 'SHDC'] 

def deal(numhands, n=5, deck=mydeck):
    random.shuffle(deck)
    index = 0
    hands = []
    for x in range(numhands):
        if index + n < len(deck):
            hands.append(deck[index: index + n])
            index += n
        else:
            raise Exception
    return hands

Norvig

def deal(numhands, n=5, deck=[r+s for r in '23456789TJQKA' for s in 'SHDC']):
    "Shuffle the deck and deal out numhands n-card hands."
    random.shuffle(deck)
    return [deck[n*i:n*(i+1)] for i in range(numhands)]

Another example of how I more readily think in for loops, rather than list comprehensions. Not sure why I thought I needed an extra index variable. One point in my favor is that I handle the case where there aren't enough cards to deal to all the hands!

Example 3: allmax()

Mine

def allmax(iterable, key=None):
    "Return a list of all items equal to the max of the iterable."
    max_hand = max(iterable, key=key)
    return [x for x in iterable if key(x) == key(max_hand)]

Here, I really thought I was onto something. Two lines of code in the allmax() function...how can it get much shorter than that?

Norvig

def allmax(iterable, key=None):
    "Return a list of all items equal to the max of the iterable"
    result, maxval = [], None
    key = key or (lambda x: x)
    for x in iterable:
        xval = key(x)
        if not result or xval > maxval:
            result, maxval = [x], xval
        elif xval == maxval:
            result == append(x)
    return result

Then, I saw Norvig's solution and was stunned. Look how long that is! Why would he do it that way? Turns out his solution points to several problems with mine:

1. Mine was not as efficient. I traverse through the list twice, whereas his only goes through one time.

2. Mine doesn't work with generators. Calling the arg "iterable" was a clue that a general solution for allmax() should handle lists and generator expressions, which means that you can only traverse one time, since can't consume a generator twice.

3. Mine breaks when key=None. Oops...I noticed that, but couldn't think of a good solution. I like how he assigns lambda x: x to key to solve this problem.

So, the one time I wrote more concise code, his solution was still way better...guess I'll have to try again next week!