Homework 4
Due by 9:00pm on Friday, 9/28/2018
Instructions
Download hw04.zip. Inside the archive, you will find starter files for the questions in this homework, along with a copy of the OK autograder.
Submission: When you are done, submit the homework by uploading the
hw04.py file to okpy.org.
You may submit more than once before the deadline; only the
final submission will be scored.
Readings: This homework relies on following references:
Required questions
Question 1: Coordinates
Implement a function coords, which takes a function, a sequence, and
an upper and lower bound on output of the function. coords then
returns a list of x, y coordinate pairs (lists) such that:
- Each pair contains
[x, fn(x)] - The x coordinates are the elements in the sequence
- Only pairs whose y coordinate is within the upper and lower bounds (inclusive)
See the doctests for examples.
One other thing: your answer can only be one line long. You should make use of list comprehensions!
def coords(fn, seq, lower, upper):
"""
>>> seq = [-4, -2, 0, 1, 3]
>>> def fn(x):
... return x**2
>>> coords(fn, seq, 1, 9)
[[-2, 4], [1, 1], [3, 9]]
"""
"*** YOUR CODE HERE ***"
return ______Use OK to test your code:
python3 ok -q coords --localQuestion 2: Repeated
Implement repeated(f, n):
fis a one-argument function that takes a number and returns another number.nis a positive integer
repeated returns another function that, when given an argument x, will
compute f(f(....(f(x))....)) (apply f a total n times). For example,
repeated(square, 3)(42) evaluates to square(square(square(42))).
def repeated(f, n):
"""Return the function that computes the nth application of f.
>>> def increment(x):
... return x + 1
>>> def square(x):
... return x**2
>>> def triple(x):
... return x*3
>>> add_three = repeated(increment, 3)
>>> add_three(5)
8
>>> repeated(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> repeated(square, 2)(5) # square(square(5))
625
>>> repeated(square, 4)(5) # square(square(square(square(5))))
152587890625
"""
"*** YOUR CODE HERE ***"
return ______Hint: You may find it convenient to use compose1 from the textbook:
def compose1(f, g):
"""Return a function h, such that h(x) = f(g(x))."""
def h(x):
return f(g(x))
return hUse OK to test your code:
python3 ok -q repeated --localQuestion 3: Double
Using repeated define a function double that takes a function of
one argument as an argument and returns a function that applies the
original function twice. For example, if inc is a function that
returns 1 more than its argument, then double(inc) should be a
function that returns two more:
def double(f):
""" Return a function that applies f twice.
f -- a function that takes one argument
>>> def square(x):
... return x**2
>>> double(square)(2)
16
"""
"*** YOUR CODE HERE ***"
return ______Use OK to test your code:
python3 ok -q double --localQuestion 4: Count van Count
Consider the following implementations of count_factors and count_primes:
def count_factors(n):
"""Return the number of positive factors that n has."""
i, count = 1, 0
while i <= n:
if n % i == 0:
count += 1
i += 1
return count
def count_primes(n):
"""Return the number of prime numbers up to and including n."""
i, count = 1, 0
while i <= n:
if is_prime(i):
count += 1
i += 1
return count
def is_prime(n):
return count_factors(n) == 2 # only factors are 1 and nThe implementations look quite similar! Generalize this logic by writing a
function count_cond, which takes in a two-argument predicate function condition(n,
i). count_cond returns a count of all the numbers from 1 to n that satisfy
condition.
Note: A predicate function is a function that returns a boolean (True or False).
def count_cond(condition, n):
"""
>>> def divisible(n, i):
... return n % i == 0
>>> count_cond(divisible, 2) # 1, 2
2
>>> count_cond(divisible, 4) # 1, 2, 4
3
>>> count_cond(divisible, 12) # 1, 2, 3, 4, 6, 12
6
>>> def is_prime(n, i):
... return count_cond(divisible, i) == 2
>>> count_cond(is_prime, 2) # 2
1
>>> count_cond(is_prime, 3) # 2, 3
2
>>> count_cond(is_prime, 4) # 2, 3
2
>>> count_cond(is_prime, 5) # 2, 3, 5
3
>>> count_cond(is_prime, 20) # 2, 3, 5, 7, 11, 13, 17, 19
8
"""
"*** YOUR CODE HERE ***"
return ______Use OK to test your code:
python3 ok -q count_cond --localQuestion 5: Match and Apply
Sometimes when we are given a dataset, we need to alter it for specific values. For example, say we have a table with one column being people's names and the other being the price they have to pay.
We can use a list of pairs for this:
[["Jessica", 5], ["Andrew", 9], ["Alex", 2], ["Amir", 11], ["John", 3], ["Ting", 2]]
The first value in each pair is the name, the second is the price.
Now, let's say we want to give a discount to specific people. We have a discount function that we want to apply to the person's price. Now, we need a function that will only apply the discount function to specific people.
Implement match_and_apply(pairs, function):
pairsis a list of pairs.functionis some function
match_and_apply returns a function such that when the function is given an input that
matches the first of a pair, returns the result of applying function to the second value in the pair.
def match_and_apply(pairs, function):
"""
>>> pairs = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 0]]
>>> def square(num):
... return num**2
>>> func = match_and_apply(pairs, square)
>>> result = func(3)
>>> result
16
>>> result = func(1)
>>> result
4
>>> result = func(7)
>>> result
64
>>> result = func(15)
>>> print(result)
None
"""
"*** YOUR CODE HERE ***"
return ______Use OK to test your code:
python3 ok -q match_and_apply --local