#!/usr/bin/env python
# encoding: utf-8
"""
Linguist 278: Programming for Linguists
Stanford Linguistics, Fall 2013
In-class exercises, class 3 (2013-10-01)
"""
"""
WARM-UP:
Before starting in on the functions below, make sure
you can do the following in the interactive Python
interpreter:
# Paste this in:
s = "Colorless green ideas"
# Measure the length of the str s:
len(s)
# Turn s into a list of characters:
list(s)
# Remove all the spaces from s:
s.replace(' ', '')
# Paste this in:
tree = ['NP', ['D', ['the']], ['N', ['code']]]
# Index into tree to pull out the str 'the':
tree[1][1][0]
# Index into tree to pull out the list ['N', ['code']]:
tree[2]
# Index into tree to pull out the list ['code']:
tree[2][1]
# Index into tree to pull out the str 'code':
tree[2][1][0]
# Methods can be stacked if they have the right output values.
# For example, "ABC".lower().split("b") returns ["a", 'c"].
# In a single line, map "ABC" to "aDc":
"ABC".lower().replace('b', 'D')
# There is a built-in function cmp: http://docs.python.org/2/library/functions.html#cmp
# Take a minute to try to figure out how cmp works, just by playing around with it.
# We won't use cmp immediately; I'm just encouraging experimentation.
"""
def plateau_string(s):
"""Return a version of str s in which the first and last letters
are lowercase and everything between them is uppercase, no
matter what s's capitalization pattern is. Use plateau_string_test
to make sure you've covered all the edge cases."""
#<--
if len(s) < 2:
return s.lower()
else:
return s[0].lower() + s[1:-1].upper() + s[-1].lower()
#-->
def plateau_string_test():
"""This function is complete. It's here to test your plateau_string for you."""
sample = (
('abbcdde' , 'aBBCDDe'),
('AbBcDde', 'aBBCDDe'),
('ab', 'ab'),
('AB', 'ab'),
('A', 'a')
)
err_count = 0
for s, val in sample:
try:
assert plateau_string(s) == val
except AssertionError:
print 'plateau_string in error for %s' % s
err_count += 1
print "%s errors for plateau_string" % err_count
def fib(n):
"""Return the nth fibonacci number. Output:
fib(1) = 0
fib(2) = 1
fib(n) = fib(n-1) + fib(n-2) for n > 2."""
#<--
if n == 1:
return 0
elif n == 2:
return 1
else:
return fib(n-1) + fib(n-2)
#-->
def iter_fib(n):
"""If you already did fib, you might have discovered that it is
slow for large n because of the recursive call to fib. Find a way
to rewrite it so that it is faster. There are lots of ways to do
this. Perhaps the easiest for us at this point is to follow the
strategy sketched below."""
# The first two values; write to code inch them forward:
back2 = 0
back1 = 1
# xrange(2, n) is like a list of ints [2 ... n], but more efficient:
for i in xrange(2, n):
#<--
# Version 1, with a temp variable:
#
# temp = back1
# back1 = back1 + back2
# back2 = temp
# Version 2, with simultaneous assignment:
#
back1, back2 = back1+back2, back1
#-->
pass # Delete this and write the inch-forward code.
# Return the newest value:
return back1
def fib_timing(n):
"""This function is complete and is here just for fun! Those of
you who did both fib and iter_fib might enjoy running this to
compare their running times. Pick n >= 20 to see the benefits."""
import timeit
fib_str = "fib(%s)" % n
iter_fib_str = "iter_fib(%s)" % n
print fib_str, timeit.timeit(fib_str, setup="from __main__ import fib", number=1000)
print iter_fib_str, timeit.timeit(iter_fib_str, setup="from __main__ import iter_fib", number=1000)
def median(vals):
"""Caculate the median value for vals, presupposed to be numeric
(float, int, or long). The median is the number occurring at the
exact middle of vals, ordered by size. If len(vals) is even, then
the median is the average of the two values occurring in the middle.
Consider testing your function with median_test below."""
# Sort vals with the built-in function sorted:
vals = sorted(vals)
# Delete the pass calls here and fill in your code. Notes:
# * is_even is a function we wrote on day 1 (and day 2).
# * Use mean from your HW1 or the day 2 code.
# * If these are in a file in this directory called
# ling278_class02.py, then you can import it here with
# from ling278_class02 import mean, is_even
#<--
from ling278_class02_solved import mean, is_even
#-->
if is_even(len(vals)):
#<--
ind1 = len(vals) / 2
ind2 = ind1 - 1
return mean([vals[ind1], vals[ind2]])
#-->
else:
#<--
return float(vals[len(vals)/2])
#-->
def median_test():
"""This function is complete. It's here to test your median function for you."""
sample = [
[[1], 1.0],
[[1,2], 1.5],
[[1,2,3], 2.0],
[[1,1,1,1,5], 1.0],
[[1,1,1,2,2,5], 1.5]
]
err_count = 0
for s, val in sample:
try:
assert median(s) == val
except AssertionError:
print 'median in error for %s' % s
err_count += 1
print "%s errors for median" % err_count
def simple_tokencounts(s):
"""Given a str s, downcase it, split it into words, and return a
dict mapping words to their token counts in s. For example:
simple_tokencounts("The cat in the hat.") ==>
{'the': 2, 'in': 1, 'hat.': 1, 'cat': 1}"""
# Output dictionary:
counts = {}
#<--
words = s.lower().split(" ")
for w in words:
counts[w] = counts.get(w, 0) + 1
return counts
#-->
def merge_count(d1, d2):
"""Assume d1 and d2 have all numeric values. Merge dict d1 with
dict d2 to create a new dict d such that
d[x] = d1[x] + d2[x]
d[x] = d1[x] if x is not in d2
d[x] = d2[x] if x is not in d1"""
# In this context, set(vals) returns an unordered
# version of vals with all its repeats removed:
# set([1,1,2] == set([1,2])
all_keys = set(d1.keys() + d2.keys())
d = {}
#<--
for key in all_keys:
d[key] = d1.get(key, 0) + d2.get(key, 0)
return d
#-->
######################################################################
# Don't worry about this for now. We'll
# review its meaning and use soon.
if __name__ == '__main__':
print "Hello again, Pythonista!"
#<--
plateau_string_test()
print median_test()
fib_n = 20
print 'fib(%s)' % fib_n, '==>', fib(fib_n)
print 'iter_fib(%s)' % fib_n, '==>', iter_fib(fib_n)
fib_timing(fib_n)
print simple_tokencounts("The cat in the hat.")
d1 = {'a': 1, 'b': 2}
d2 = {'b': 1, 'c': 3}
print merge_count(d1, d2)
#-->