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.


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


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)
>>> get_lat(berkeley)
>>> get_lon(berkeley)

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)
    >>> city3 = make_city('city3', 6.5, 12)
    >>> city4 = make_city('city4', 2.5, 15)
    >>> distance(city3, city4)
"*** 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)
        >>> bucharest = make_city('Bucharest', 44.43, 26.10)
        >>> vienna = make_city('Vienna', 48.20, 16.37)
        >>> closer_city(41.29, 174.78, bucharest, vienna)
"*** 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


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
    >>> ab_plus_c(0, 3, 2)  # 0 * 3 + 2
    >>> ab_plus_c(3, 0, 2)  # 3 * 0 + 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)
    >>> is_prime(16)
    >>> is_prime(521)
"*** 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))
    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)
"*** 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


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 ...> and Error if it errors.

>>> x = 5
>>> x = lambda x: lambda x: lambda y: 3+x
>>> x(3)(5)(7)
>>> 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')
>>> 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)
>>> bears(gob)

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)
>>> t(t(s))(0)
>>> t(t)(s)(0)

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)
    >>> is_palindrome(42)
    >>> is_palindrome(2015)
    >>> is_palindrome(55)
    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)
    >>> ten_pairs(55055)
    >>> ten_pairs(9641469)
"*** 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