"""Submission for CS 61A Homework 4.
Name:
Login:
Collaborators:
"""
# Q1.
# [This problem, as promised, held over from last week.]
# Submit a copy of your hw3.py solution with this hw4.py file.
from hw3 import *
def non_zero(x):
"""Return whether x contains 0."""
return lower_bound(x) > 0 or upper_bound(x) < 0
def square_interval(x):
"""Return the interval that contains all squares of values in x, where x
does not contain 0.
"""
assert non_zero(x), 'square_interval is incorrect for x containing 0'
return mul_interval(x, x)
# The first two of these intervals contain 0, but the third does not.
seq = (make_interval(-1, 2), make_center_width(-1, 2), make_center_percent(-1, 50))
zero = make_interval(0, 0)
def sum_nonzero_with_for(seq):
"""Returns an interval that is the sum of the squares of the non-zero
intervals in seq, using a for statement.
>>> str_interval(sum_nonzero_with_for(seq))
'0.25 to 2.25'
"""
"*** YOUR CODE HERE ***"
from functools import reduce
def sum_nonzero_with_map_filter_reduce(seq):
"""Returns an interval that is the sum of the squares of the non-zero
intervals in seq, using using map, filter, and reduce.
>>> str_interval(sum_nonzero_with_map_filter_reduce(seq))
'0.25 to 2.25'
"""
"*** YOUR CODE HERE ***"
def sum_nonzero_with_generator_reduce(seq):
"""Returns an interval that is the sum of the squares of the non-zero
intervals in seq, using using reduce and a generator expression.
>>> str_interval(sum_nonzero_with_generator_reduce(seq))
'0.25 to 2.25'
"""
"*** YOUR CODE HERE ***"
# Definitions from lecture.
empty_rlist = None
def make_rlist(first, rest = empty_rlist):
"""A recursive list, r, such that first(r) is 'first' and
rest(r) is 'rest,' which must be an rlist."""
return first, rest
def first(r):
"""The first item in r."""
return r[0]
def rest(r):
"""The tail of r."""
return r[1]
def extend_rlist(left, right):
"""The sequence of items of rlist 'left' followed
by the items of 'right'."""
if left == empty_rlist:
return right
else:
return make_rlist(first(left),
extend_rlist(rest(left), right))
# Q2.
def is_tuple(x):
return type(x) is tuple
def to_rlist(items):
"""The sequence of values in 'items', converted into a corresponding
rlist. Any tuples among the items also become rlists.
>>> to_rlist((1, (0, 2), (), 3))
(1, ((0, (2, None)), (None, (3, None))))
"""
"*** YOUR CODE HERE ***"
# Q3.
def could_be_rlist(x):
"""Return true iff x might represent an rlist."""
return x is None or type(x) is tuple
def to_tuple(L):
"""Assuming L is an rlist, returns a tuple containing the same
sequence of values.
>>> x = to_rlist((1, (0, 2), (), 3))
>>> to_tuple(x)
(1, (0, 2), (), 3)
"""
"*** YOUR CODE HERE ***"
# Q4.
def inserted_into_all(item, list_list):
"""Assuming that 'list_list' is an rlist of rlists, return the
rlist consisting of the rlists in 'list_list', but with
'item' prepended as the first item in each.
>>> L0 = to_rlist(((), (1, 2), (3,)))
>>> L1 = inserted_into_all(0, L0)
>>> to_tuple(L1)
((0,), (0, 1, 2), (0, 3))
"""
"*** YOUR CODE HERE ***"
def subseqs(S):
"""Assuming that S is an rlist, return an rlist of all subsequences
of S (an rlist of rlists). The order in which the subsequences
appear is unspecified.
>>> seqs = subseqs(to_rlist((1, 2, 3)))
>>> show = list(to_tuple(seqs)) # Can only sort lists, not tuples
>>> show.sort()
>>> show
[(), (1,), (1, 2), (1, 2, 3), (1, 3), (2,), (2, 3), (3,)]
"""
"*** YOUR CODE HERE ***"
# Q5.
def inserted_into_all_tuples(item, tuple_tuple):
"""Assuming that 'tuple_tuple' is a tuple of tuples, return the
tuple consisting of the tuples in 'tuple_tuple', but with
'item' prepended as the first item in each.
>>> inserted_into_all_tuples(0, ((), (1, 2), (3, )))
((0,), (0, 1, 2), (0, 3))
"""
"*** YOUR CODE HERE ***"
def subseqs_tuples(S):
"""Assuming that S is a tuple, return tuple of all subsequences
of S (a tuple of tuples). The order in which the subsequences
appear is unspecified.
>>> seqs = subseqs_tuples((1, 2, 3))
>>> show = list(seqs)
>>> show.sort()
>>> show
[(), (1,), (1, 2), (1, 2, 3), (1, 3), (2,), (2, 3), (3,)]
"""
"*** YOUR CODE HERE ***"
# Q7.
def alt_filter(pred, L):
"""The tuple containing all elements, x, of L such that pred(x).
>>> alt_filter(lambda x: x%2 == 0, (0, 1, 3, 8, 4, 12, 13))
(0, 8, 4, 12)
"""
"*** YOUR CODE HERE ***"
# Q8.
def capitalize_sentences(S):
"""The sequence of words (strings) S, with all initial words in
sentences capitalized, and all others unchanged. A word begins a
sentence if it is either the first word in S, or the preceding word
in S ends in a period.
>>> capitalize_sentences(("see", "spot", "run.", "run", "spot", "run."))
('See', 'spot', 'run.', 'Run', 'spot', 'run.')
"""
"*** YOUR CODE HERE ***"
# Q9.
def repeat(f, x, n):
"""Apply f to x n times. When n is 0, the result is x; when n is
1, the result is f(x); when n is 2, f(f(x)), etc.
>>> repeat(lambda x: x+1, 1, 5)
6
"""
"*** YOUR CODE HERE ***"
# Q10. Extra for experts.
def sortit(S):
"""The sequence of strings S sorted into lexicographic order
(the < operator).
>>> sortit(("The", "quick", "brown", "fox", "jumps", "over", "the", "lazy",
... "dog."))
('The', 'brown', 'dog.', 'fox', 'jumps', 'lazy', 'over', 'quick', 'the')
"""
"*** YOUR CODE HERE ***"