In [144]:
import numpy as np
In [284]:
def words_to_dict():
D = {}
with open('words.txt') as f:
for word in f:
D[word.strip()] = 0
return D
def words_to_list():
L = []
with open('words.txt') as f:
for word in f:
L.append(word.lower().strip())
return L
def in_test(struct, tests):
found = [0]*len(tests)
for i, test in enumerate(tests):
found[i] = test in struct
D = words_to_dict()
L = words_to_list()
with open('words.txt') as f:
words = f.readlines()
random_indices = np.random.randint(low=0, high=len(words), size=1000)
tests = [words[i].strip() for i in random_indices]
In [285]:
%timeit in_test(D, tests)
In [286]:
%timeit in_test(L, tests)
In [39]:
def histogram(s):
d = dict()
for c in s:
if c not in d:
d[c] = 1
else:
d[c] += 1
return d
In [40]:
def histogram_v2(s):
d = dict()
for c in s:
d[c] = d.get(c, 0) + 1
return d
In [45]:
h1 = histogram('brontosaurus')
print h1
In [46]:
h2 = histogram_v2('brontosaurus')
print h2
In [47]:
h1 == h2
Out[47]:
In [ ]:
In [48]:
def print_hist(h):
keys = sorted(h.keys())
for c in keys:
print c, h[c]
In [50]:
h = histogram_v2('parrot')
print_hist(h)
In [51]:
def reverse_lookup(d, v):
found = []
for k in d:
if d[k] == v:
found.append(k)
return found
In [54]:
h = histogram_v2('parrot')
k = reverse_lookup(h, 1)
print k
In [77]:
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
In [79]:
invert_dict(h)
Out[79]:
In [281]:
from collections import defaultdict
def invert_dict_v2(d):
inverse = defaultdict(list)
for key, value in d.iteritems():
inverse[value].append(key)
return inverse
In [282]:
inv = invert_dict_v2(h)
In [283]:
print inv
In [110]:
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
In [111]:
def fibonacci_old(n):
if n == 0:
return 0
elif n==1:
return 1
else:
return fibonacci_old(n-1) + fibonacci_old(n-2)
In [121]:
fibonacci(25)
Out[121]:
In [122]:
fibonacci_old(25)
Out[122]:
In [123]:
%timeit fibonacci(25)
In [125]:
%timeit fibonacci_old(25)
In [130]:
known = {}
def ack_v2(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:
if (m-1, 1) in known:
return known[(m-1, 1)]
res = ack_v2(m - 1, 1)
known[(m-1, 1)] = res
return res
elif m > 0 and n > 0:
if (m, n - 1) in known:
arg2 = known[(m, n - 1)]
else:
arg2 = ack_v2(m, n - 1)
known[(m, n - 1)] = arg2
if (m - 1, arg2) in known:
return known[(m - 1, arg2)]
else:
return ack_v2(m - 1, arg2)
In [132]:
ack_v2(3, 4)
Out[132]:
In [ ]:
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))
In [133]:
ack(4, 5)
Out[133]:
In [138]:
%timeit ack_v2(3,4)
In [135]:
%timeit ack(3,4)
In [160]:
def has_duplicates(L):
seen = []
for el in L:
if el in seen:
return True
seen.append(el)
return False
In [159]:
def has_duplicates_v2(L):
seen = {}
for el in L:
if el in seen:
return True
seen[el] = 1
return False
In [163]:
L = np.random.randint(0,1000,100)
In [164]:
%timeit has_duplicates(L)
In [165]:
%timeit has_duplicates_v2(L)
In [180]:
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 [177]:
D = words_to_dict()
In [181]:
find_word_pairs(D)
In [183]:
"""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 read_dictionary(filename='c06d'):
"""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
In [272]:
pronounciations = read_dictionary()
In [274]:
def words_to_list():
L = []
with open('words.txt') as f:
for word in f:
L.append(word.strip().lower())
return L
In [275]:
words = words_to_list()
In [279]:
def find_special_homophones(words, pronounciations):
for word in words:
p = pronounciations.get(word, False)
if p:
drop_first = word[1:]
drop_second = word[0] + word[2:]
if p == pronounciations.get(drop_first, False) and p == pronounciations.get(drop_second, 0):
print word
print drop_first
print drop_second
In [280]:
find_special_homophones(words, pronounciations)