Software Design
Spring 2006

For Wednesday you should:

1) read Chapter 15

For Friday

1) read Chapter 16

2) prepare for a quiz

Today:

1) Exam 1 solutions

2) Homework 5 solutions


Exam 1 Solutions
----------------

Part 1:

keys, values (or key-value pairs)
 
aliasing, immutable

operator, keyword (or statement)

method, class definition

traverse (or iterate through), compound object (or sequence)

Part 2:

There were many good answers to this question.  Some people proposed
interfaces that were not equally general, which was not really an
answer to the question.

Part 3:

def invert(d):
    res = {}
    for v, k in d.iteritems():
        if k in res:
            res[k].append(v)
        else:
            res[k] = [v]
    return res


Or, using mdict:

from mdict import *

def invert_dict(d):
    res = mdict()
    for v, k in d.iteritems():
        res[k] = v
    return res


Both of these solutions assume that the values of d are hashable.

Part 4:

1) {'a': 1, 'c': 1, 'b': 0}

2) """returns a new dictionary with the union of the keys
from d1 and d2, and the value d1[key] - d2[key] for each key.
Keys in one dictionary that are missing in the other are given
the value 0."""

3) see below


Homework 5 solutions
--------------------

1) my buffer, and the keys in the dictionary, are tuples of words

def process_word(word, order=2):
    """process each word.  During the first few iterations,
    all we do is store up the words; after that we start adding
    entries to the dictionary."""

    global prefix
    if len(prefix) < order:
        prefix += (word,)
        return

    try:
        dict[prefix].append(word)
    except KeyError:
        # if there is no entry for this prefix, make one
        dict[prefix] = [word]

    prefix = shift(prefix, word)

def shift(t, word):
    """form a new tuple by removing the head and adding word to the tail"""
    return t[1:] + (word,)


2) the values in the dictionary are lists of strings

def random_text(n=100):
    """generate n random words, starting with a random prefix
    from the dictionary"""
    
    # choose a random prefix
    prefix = random.choice(dict.keys())
    
    for i in range(n):
        suffixes = dict.get(prefix, None)
        if suffixes == None:
            # if the prefix isn't in dict, we got to the end of the
            # original text, so we have to start again.
            random_text(n-i)
            return

        # choose a random suffix
        word = random.choice(suffixes)
        print word,
        prefix = shift(prefix, word)


3) random_text demonstrates a slightly unusual use of recursion


Handling unusual conditions
---------------------------

We have now seen three ways of dealing with unusual conditions
(discussion based on the Python Cookbook, Alex Martelli)

LBYL (look before you leap):

    if key in d:
        d[key] += 1
    else:
        d[key] = 0


EAFTP (easier to ask forgiveness than permission):

    try:
        d[key] += 1
    except KeyError:
        d[key] = 0


HDC (homogenize different cases):

    d[key] = d.get(key, 0) + 1


What are the pros and cons?