Lab 3: Data Abstraction and Recursion/Lambdas Review
Due at 11:59pm on 02/12/2016.
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 6 in lab03.py and submit through OK.
- Questions 7 and 8 are more practice with lambda expressions. You can run Python interactively or use Online Python Tutor to test them out, but try solving them yourself first!
- Questions 9 and 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)
37
Notice 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. We'll look into defining the constructors and selectors later in this discussion.
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 distance
Question 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_city
Recursion
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. Try 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_c
Question 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 (think count_up from Lab 2)
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 < sqrt(n): #could replace with i == 1
return True
if n % i == 0:
return False
return helper(i - 1)
return helper(n - 1)
Use OK to test your code:
python3 ok -q is_prime
Question 5: 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 total
Write a function interleaved_sum
that similarly computes the sum of a
sequence of terms from 1 to n
, but uses different function 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, term0
Use OK to test your code:
python3 ok -q interleaved_sum
Lambdas
Although only question 6 is mandatory, we recommend going through question 7 and 8 through Python Tutor on your own. Lambda environment diagrams can be quite tricky and have come up on past tests.
Question 6: 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 -u
Hint: Remember for all WWPP questions, enter
Function
if you believe the answer is<function ...>
andError
if 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
Error
Question 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)
______4
Hint: 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)
______27
Extra 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 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 == n
Use OK to test your code:
python3 ok -q is_palindrome
Question 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