In [ ]:
In [ ]:
In [3]:
def histogram(s):
d = dict()
for c in s:
d[c] = d.get(c, 0) + 1
return d
In [4]:
def print_hist(h):
keys = sorted(h.keys())
for c in keys:
print c, h[c]
In [5]:
h = histogram('parrot')
print_hist(h)
In [3]:
#The original functions:
def histogram(s):
d = dict()
for c in s:
if c not in d:
d[c] = 1
else:
d[c] += 1
return d
def reverse_lookup(d,v):
for k in d:
if d[k] ==v:
return k
raise ValueError, 'value does not appear in the dictionary'
h = histogram('easter')
k = reverse_lookup(h,2)
#this tells you the letters that appear more twice, but only the first one
print k
my new updated function:
In [4]:
def reverse_lookup2(d,v):
reverse = dict()
for k in d:
value = d[k]
if value not in reverse and value == v:
reverse[value] = [k]
if value in reverse:
reverse[value].append(k)
return reverse
In [5]:
h = histogram('easters')
k = reverse_lookup2(h,2)
k
Out[5]:
Original function:
In [6]:
#this is the original function from the text
def invert_dict1(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
hist = histogram('parrot')
print hist
In [7]:
#and the output of that function
inverse = invert_dict1(hist)
print inverse
My updated solution:
In [9]:
def invert_dict2(d):
inverse = dict()
for key, val in d.iteritems():
inverse.setdefault(val,[]).append(key)
return inverse
In [10]:
invert_dict2(hist)
Out[10]:
In [ ]:
#compare to answer from green tree press - there is an extra bit at the bottom
"""This module contains code from
Think Python by Allen B. Downey
http://thinkpython.com
Copyright 2012 Allen B. Downey
License: GNU GPLv3 http://www.gnu.org/licenses/gpl.html
"""
def invert_dict(d):
"""Inverts a dictionary, returning a map from val to a list of keys.
If the mapping key->val appears in d, then in the new dictionary
val maps to a list that includes key.
d: dict
Returns: dict
"""
inverse = {}
for key, val in d.iteritems():
inverse.setdefault(val, []).append(key)
return inverse
if __name__ == '__main__':
d = dict(a=1, b=2, c=3, z=1)
inverse = invert_dict(d)
for val, keys in inverse.iteritems():
print val, keys
In [1]:
## solution for 11.6, enjoy
import time
known = {0:0, 1:1}
def fibonacci_new(n):
if n in known:
return known[n]
res = fibonacci_new(n-1) + fibonacci_new(n-2)
known[n] = res
return res
def fibonacci_ori(n):
if n==0:
return 0
elif n==1:
return 1
else:
return fibonacci_ori(n-1) + fibonacci_ori(n-2)
# test the original one
start_time = time.time()
print fibonacci_ori(20)
print("--- %s seconds for the ori_one ---" % (time.time() - start_time))
start_time = time.time()
print fibonacci_new(20)
print("--- %s seconds for the new_one ---" % (time.time() - start_time))
In [ ]:
In [ ]:
In [7]:
def words_to_dict():
D = {}
with open('words.txt') as f:
for word in f:
D[word.strip().lower()] = True
return D
def rotate_word(word, r):
return word[r:] + word[0:r]
def find_word_pairs(D):
for k in D:
for r in range(1,len(k)):
rw = rotate_word(k, r)
if rw in D:
print k, rw
In [8]:
D = words_to_dict()
In [9]:
find_word_pairs(D)
In [3]:
def read_dictionary(filename):
"""Reads from a file and builds a dictionary that maps from
each word to a string that describes its primary pronunciation.
Secondary pronunciations are added to the dictionary with
a number, in parentheses, at the end of the key, so the
key for the second pronunciation of "abdominal" is "abdominal(2)".
filename: string
returns: map from string to pronunciation
"""
d = dict()
fin = open(filename)
for line in fin:
# skip over the comments
if line[0] == '#': continue
t = line.split()
word = t[0].lower()
pron = ' '.join(t[1:])
d[word] = pron
return d
d_pron = read_dictionary("/Users/lh15/Documents/workspace/c06d.txt")
for word in d_pron:
## first, make the 2 variations of the original words,
## and then check their exitance in the word_pronunciation_list.
## if they both exist and have the same pronuciation as the original word.
first_char = word[0]
word_var_1 = word[1:]
word_var_2 = first_char + word_var_1[1:]
if word_var_1 in d_pron and word_var_2 in d_pron and d_pron[word_var_1] == d_pron[word] and d_pron[word_var_2] == d_pron[word]:
print 'homophone: ' + word
In [ ]: