Lab 3: Data Abstraction and Recursion/Lambdas Review
Due at 11:59pm on 02/10/2017.
Starter Files
Download lab03.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
Submission
By the end of this lab, you should have submitted the lab with
python3 ok --submit. You may submit more than once before the
deadline; only the final submission will be graded.
- To receive credit for this lab, you must complete questions 1 through 5 in lab03.py and submit through OK.
- Questions 6 through 10 are extra practice. They can be found in the lab03_extra.py file. It is recommended that you complete these problems on your own time.
Data Abstraction
Data abstraction is a powerful concept in computer science that allows programmers to treat code as objects --- for example, car objects, chair objects, people objects, etc. That way, programmers don't have to worry about how code is implemented --- they just have to know what it does.
Data abstraction mimics how we think about the world. When you want to drive a car, you don't need to know how the engine was built or what kind of material the tires are made of. You just have to know how to turn the wheel and press the gas pedal.
An abstract data type consists of two types of functions:
- Constructors: functions that build the abstract data type.
- Selectors: functions that retrieve information from the data type.
Say we have an abstract data type called city.
This city object will hold the city's name, and
its latitude and longitude. To create a city object,
you'd use a constructor like
city = make_city(name, lat, lon)To extract the information of a city object, you would use the selectors like
get_name(city)
get_lat(city)
get_lon(city)Here is how we would use the make_city constructor to create a city object to represent Berkeley
and the selectors to access its information.
>>> berkeley = make_city('Berkeley', 122, 37)
>>> get_name(berkeley)
'Berkeley'
>>> get_lat(berkeley)
122
>>> get_lon(berkeley)
37Notice that we don't need to know how these functions were implemented. We are assuming that someone else has defined them for us.
It's okay if the end user doesn't know how functions were implemented. However, the functions still have to be defined by someone.
Question 1: Distance
We will now use those selectors to write distance, which computes the
distance between two city objects. Recall that the distance between two
coordinate pairs, (x1, y1) and (x2, y2) can be found by calculating
the sqrt of (x1 - x2)**2 + (y1 - y2)**2. We have already imported
sqrt for your convenience, so use that and the appropriate selectors
to fill in the function.
from math import sqrt
def distance(city1, city2):
"""
>>> city1 = make_city('city1', 0, 1)
>>> city2 = make_city('city2', 0, 2)
>>> distance(city1, city2)
1.0
>>> city3 = make_city('city3', 6.5, 12)
>>> city4 = make_city('city4', 2.5, 15)
>>> distance(city3, city4)
5.0
"""
"*** YOUR CODE HERE ***"
lat_1, lon_1 = get_lat(city1), get_lon(city1)
lat_2, lon_2 = get_lat(city2), get_lon(city2)
return sqrt((lat_1 - lat_2)**2 + (lon_1 - lon_2)**2)Use OK to test your code:
python3 ok -q distanceQuestion 2: Closer city
Next, implement closer_city, a function that takes a latitude,
longitude, and two cities, and returns the name of the city that is
relatively closer to the provided latitude and longitude.
You may only use selectors and constructors (introduced above) and the
distance function you just defined for this question. All of the
selector and constructor functions can be found in utils.py, if you
are curious how they are implemented. However, the point of data abstraction,
as we've said, is that we do not need to know how an abstract data type is
implemented, but rather just how we can interact with and use the data type.
def closer_city(lat, lon, city1, city2):
"""
Returns the name of either city1 or city2, whichever is closest to
coordinate (lat, lon).
>>> berkeley = make_city('Berkeley', 37.87, 112.26)
>>> stanford = make_city('Stanford', 34.05, 118.25)
>>> closer_city(38.33, 121.44, berkeley, stanford)
'Stanford'
>>> bucharest = make_city('Bucharest', 44.43, 26.10)
>>> vienna = make_city('Vienna', 48.20, 16.37)
>>> closer_city(41.29, 174.78, bucharest, vienna)
'Bucharest'
"""
"*** YOUR CODE HERE ***"
new_city = make_city('arb', lat, lon)
dist1 = distance(city1, new_city)
dist2 = distance(city2, new_city)
if dist1 < dist2:
return get_name(city1)
return get_name(city2)Use OK to test your code:
python3 ok -q closer_cityRecursion
Question 3: AB+C
Implement ab_plus_c, a function that takes arguments a, b, and
c and computes a * b + c. You can assume a and b are both positive
integers. However, you can't use the * operator. Use recursion!
def ab_plus_c(a, b, c):
"""Computes a * b + c.
>>> ab_plus_c(2, 4, 3) # 2 * 4 + 3
11
>>> ab_plus_c(0, 3, 2) # 0 * 3 + 2
2
>>> ab_plus_c(3, 0, 2) # 3 * 0 + 2
2
"""
"*** YOUR CODE HERE ***"
if b == 0:
return c
return a + ab_plus_c(a, b - 1, c)Use OK to test your code:
python3 ok -q ab_plus_cQuestion 4: Is Prime
Write a function is_prime that takes a single argument n and returns True
if n is a prime number and False otherwise. Assume n > 1. We implemented
this in the project iteratively, now time to do it recursively!
Hint: You will need a helper function! Remember helper functions are useful if you need to keep track of more variables than the given parameters, or if you need to change the value of the input.
def is_prime(n):
"""Returns True if n is a prime number and False otherwise.
>>> is_prime(2)
True
>>> is_prime(16)
False
>>> is_prime(521)
True
"""
"*** YOUR CODE HERE ***"
def helper(i):
if i > (n ** 0.5): # Could replace with i == n
return True
elif n % i == 0:
return False
return helper(i + 1)
return helper(2)Use OK to test your code:
python3 ok -q is_primeMore Lambda Practice
Question 5: WWPP: Lambda Trivia
The following WWPP questions will review your understanding of lambdas. Python Tutor may be helpful in understanding what is happening.
Use OK to test your knowledge with the following "What Would Python Print?" questions:
python3 ok -q lambda -uHint: Remember for all WWPP questions, enter
Functionif you believe the answer is<function ...>andErrorif it errors.
>>> x = 5
>>> x = lambda x: lambda x: lambda y: 3+x
>>> x(3)(5)(7)
______8
>>> you = 'fly'
>>> yo, da = lambda do: you, lambda can: True
>>> yo = yo('jedi')
>>> da = (3 and 4 and 5 and (False or ' you shall'))
>>> yo+da
______'fly you shall'
>>> annoying = lambda yell: annoying
>>> annoying('aiya')('aaa')('aaaa')('aaaaa')('aaaaaa')
______Function
>>> more = ' productive'
>>> lip_service = lambda say: print(say)
>>> useful_person = lambda do: do + more
>>> lip_service('blah blah blah') + useful_person('be')
______blah blah blah
ErrorExtra Questions
Questions in this section are not required for submission. However, we encourage you to try them out on your own time for extra practice.
Question 6: Interleaved Sum
Recall that the summation function computes the sum of a sequence of
terms from 1 to n:
def summation(n, term):
"""Return the sum of the first n terms of a sequence.
>>> summation(5, lambda x: pow(x, 3))
225
"""
total, k = 0, 1
while k <= n:
total, k = total + term(k), k + 1
return totalWrite a function interleaved_sum that similarly computes the sum of a
sequence of terms from 1 to n, but uses different functions to compute
the terms for odd and even numbers. Do so without using any loops or
testing in any way if a number is odd or even. (You may test if a
number is equal to 0, 1, or n.)
Hint: Use recursion and a helper function!
def interleaved_sum(n, odd_term, even_term):
"""Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up
to n.
>>> # 1 + 2^2 + 3 + 4^2 + 5
... interleaved_sum(5, lambda x: x, lambda x: x*x)
29
"""
"*** YOUR CODE HERE ***"
return interleaved_helper(n, odd_term, even_term, 1)
def interleaved_helper(n, term0, term1, k):
if k == n:
return term0(k)
return term0(k) + interleaved_helper(n, term1, term0, k+1)
# Alternate solution
def interleaved_sum2(n, odd_term, even_term):
"""Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up
to n.
>>> # 1 + 2^2 + 3 + 4^2 + 5
... interleaved_sum2(5, lambda x: x, lambda x: x*x)
29
"""
total, term0, term1 = interleaved_helper2(n, odd_term, even_term)
return total
def interleaved_helper2(n, odd_term, even_term):
if n == 1:
return odd_term(1), even_term, odd_term
else:
total, term0, term1 = interleaved_helper2(n-1, odd_term,
even_term)
return total + term0(n), term1, term0Use OK to test your code:
python3 ok -q interleaved_sumQuestion 7: Lambda the Plentiful
Try drawing an environment diagram for the following code and predict what Python will output.
Note: This is a challenging problem! Work together with your neighbors and see if you can arrive at the correct answer.
You can check your work with the Online Python Tutor, but try drawing it yourself first!
>>> def go(bears):
... gob = 3
... print(gob)
... return lambda ears: bears(gob)
>>> gob = 4
>>> bears = go(lambda ears: gob)
______3
>>> bears(gob)
______4Hint: What is the parent frame for a lambda function?
Question 8: Church numerals
Find the value of the following three expressions, using the given
values of t and s.
>>> t = lambda f: lambda x: f(f(f(x)))
>>> s = lambda x: x + 1
>>> t(s)(0)
______3
>>> t(t(s))(0)
______9
>>> t(t)(s)(0)
______27Question 9: Palindrome
A number is considered a palindrome if it reads the same forwards and backwards. Fill in the blanks '_' to help determine if a number is a palindrome. In the spirit of exam style questions, please do not edit any parts of the function other than the blanks.
def is_palindrome(n):
"""
Fill in the blanks '_____' to check if a number
is a palindrome.
>>> is_palindrome(12321)
True
>>> is_palindrome(42)
False
>>> is_palindrome(2015)
False
>>> is_palindrome(55)
True
"""
x, y = n, 0
f = lambda: _____
f = lambda: y * 10 + x % 10 while x > 0:
x, y = _____, f()
x, y = x // 10, f() return y == nUse OK to test your code:
python3 ok -q is_palindromeQuestion 10: Ten-pairs
Write a function that takes a positive integer n and returns the
number of ten-pairs it contains. A ten-pair is a pairs of digits
within n that sum to 10. Do not use any assignment statements.
The number 7,823,952 has 3 ten-pairs. The first and fourth digits sum to 7+3=10, the second and third digits sum to 8+2=10, and the second and last digit sum to 8+2=10:
Hint: Use a helper function to calculate how many times a digit appears in n.
def ten_pairs(n):
"""Return the number of ten-pairs within positive integer n.
>>> ten_pairs(7823952)
3
>>> ten_pairs(55055)
6
>>> ten_pairs(9641469)
6
"""
"*** YOUR CODE HERE ***"
if n < 10:
return 0
else:
return ten_pairs(n//10) + count_digit(n//10, 10 - n%10)
def count_digit(n, digit):
"""Return how many times digit appears in n.
>>> count_digit(55055, 5)
4
"""
if n == 0:
return 0
else:
if n%10 == digit:
return count_digit(n//10, digit) + 1
else:
return count_digit(n//10, digit)Use OK to test your code:
python3 ok -q ten_pairs