All exercises from Downey, Allen. Think Python. Green Tea Press, 2014. http://www.greenteapress.com/thinkpython/

Exercise 11.1 (Masa)

Write a function that reads the words in words.txt and stores them as keys in a dictionary. It doesn’t matter what the values are. Then you can use the in operator as a fast way to check whether a string is in the dictionary.

Exercise 11.2 (Wendy)

Dictionaries have a method called get that takes a key and a default value. If the key appears in the dictionary, get returns the corresponding value; otherwise it returns the default value. For example:

>>> h = histogram('a')
>>> print h
{'a': 1}
>>> h.get('a', 0)
1
>>> h.get('b', 0)
0

Use get to write histogram more concisely. You should be able to eliminate the if statement.

Exercise 11.3 (Dan)

Dictionaries have a method called keys that returns the keys of the dictionary, in no particular order, as a list. Modify print_hist to print the keys and their values in alphabetical order.

def print_hist(h):
    for c in h:
        print c, h[c]

Exercise 11.4 (Sarah)

Modify reverse_lookup so that it builds and returns a list of all keys that map to v, or an empty list if there are none.

def reverse_lookup(d, v):
    for k in d:
        if d[k] == v:
            return k
    raise ValueError

Exercise 11.5 (Sarah)

Exercise 5 Read the documentation of the dictionary method setdefault and use it to write a more concise version of invert_dict.

def invert_dict(d):
    inverse = dict()
    for key in d:
        val = d[key]
        if val not in inverse:
            inverse[val] = [key]
        else:
            inverse[val].append(key)
    return inverse

Exercise 11.6 (Liu)

Run this version of fibonacci and the original with a range of parameters and compare their run times.

known = {0:0, 1:1}

def fibonacci(n):
    if n in known:
        return known[n]

    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    return res

Exercise 11.7 (Wendy)

Memoize the Ackermann function from Exercise 5 and see if memoization makes it possible to evaluate the function with bigger arguments. Hint: no.

def ack(m, n):
    if m < 0 or n < 0:
        print "m and n must be nonnegative"
        return None
    elif m == 0:
        return n + 1
    elif m > 0 and n == 0:
        return ack(m - 1, 1)
    elif m > 0 and n > 0:
        return ack(m - 1, ack(m, n - 1))

Exercise 11.9 (Masa)

If you did Exercise 8, you already have a function named has_duplicates that takes a list as a parameter and returns True if there is any object that appears more than once in the list. Use a dictionary to write a faster, simpler version of has_duplicates.

def has_duplicates(L):
    seen = []
    for el in L:
        if el in seen:
            return True
        seen.append(el)
    return False

Exercise 11.10 (Dan)

Two words are “rotate pairs” if you can rotate one of them and get the other (see rotate_word in Exercise 12). Write a program that reads a wordlist and finds all the rotate pairs.

def rotate_word(word, r):
    return word[r:] + word[0:r]

Exercise 11.11 (Liu)

Here’s another Puzzler from Car Talk (http://www.cartalk.com/content/puzzlers):

This was sent in by a fellow named Dan O’Leary. He came upon a common one-syllable, five-letter word recently that has the following unique property. When you remove the first letter, the remaining letters form a homophone of the original word, that is a word that sounds exactly the same. Replace the first letter, that is, put it back and remove the second letter and the result is yet another homophone of the original word. And the question is, what’s the word?

Now I’m going to give you an example that doesn’t work. Let’s look at the five-letter word, ‘wrack.’ W-R-A-C-K, you know like to ‘wrack with pain.’ If I remove the first letter, I am left with a four-letter word, ’R-A-C-K.’ As in, ‘Holy cow, did you see the rack on that buck! It must have been a nine-pointer!’ It’s a perfect homophone. If you put the ‘w’ back, and remove the ‘r,’ instead, you’re left with the word, ‘wack,’ which is a real word, it’s just not a homophone of the other two words.

But there is, however, at least one word that Dan and we know of, which will yield two homophones if you remove either of the first two letters to make two, new four-letter words. The question is, what’s the word?

You can use the dictionary from Exercise 1 to check whether a string is in the word list.

To check whether two words are homophones, you can use the CMU Pronouncing Dictionary. You can download it from http://www.speech.cs.cmu.edu/cgi-bin/cmudict or from http://thinkpython.com/code/c06d and you can also download http://thinkpython.com/code/pronounce.py, which provides a function named read_dictionary that reads the pronouncing dictionary and returns a Python dictionary that maps from each word to a string that describes its primary pronunciation.

Write a program that lists all the words that solve the Puzzler.