Lab 4: Recursion, Lists, and Data Abstraction
Due at 11:59pm on Friday, 02/22/2019.
Starter Files
Download lab04.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.
Check that you have successfully submitted your code on
okpy.org.
Topics
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
Lists
Lists are Python data structures that can store multiple values. Each value can be any type and can even be another list! A list is written as a comma separated list of expressions within square brackets:
>>> list_of_nums = [1, 2, 3, 4]
>>> list_of_bools = [True, True, False, False]
>>> nested_lists = [1, [2, 3], [4, [5]]]
Each element in a list is assigned an index. Lists are zero-indexed, meaning
their indices start at 0
and increase in sequential order. To retrieve an element
from a list, use list indexing:
>>> lst = [6, 5, 4, 3, 2, 1]
>>> lst[0]
6
>>> lst[3]
3
Often times we need to know how long a list is when we're working with it. To find
the length of a list, call the function len
on it:
>>> len([])
0
>>> len([2, 4, 6, 8, 10])
5
Tip: Recall that empty lists,
[]
, are false-y values. Therefore, you can use an if statement like the following if you only want to do operations on non-empty lists:if lst: # Do stuff with the elements of list
This is equivalent to:
if len(lst) > 0: # Do stuff
You can also create a copy of some portion of the list using list slicing. To slice
a list, use this syntax: lst[<start index>:<end index>]
. This expression
evaluates to a new list containing the elements of lst
starting at and including
the element at <start index>
up to but not including the element at end index
.
>>> lst = [True, False, True, True, False]
>>> lst[1:4]
[False, True, True]
>>> lst[:3] # Start index defaults to 0
[True, False, True]
>>> lst[3:] # End index defaults to len(lst)
[True, False]
>>> lst[:] # Creates a copy of the whole list
[True, False, True, True, False]
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.
Programmers design ADTs to abstract away how information is stored and calculated such that the end user does not need to know how constructors and selectors are implemented. The nature of abstract data types allows whoever uses them to assume that the functions have been written correctly and work as described.
Required Questions
Lists Practice
Q1: List Indexing
Use Ok to test your knowledge with the following "List Indexing" questions:
python3 ok -q indexing -u
For each of the following lists, what is the list indexing expression that evaluates to
7
? For example, if x = [7]
, then the answer would be x[0]
. You can use the
interpreter or Python Tutor to experiment with your answers.
>>> x = [1, 3, [5, 7], 9]
______x[2][1]
>>> x = [[3, [5, 7], 9]]
______x[0][1][1]
What would Python display? If you get stuck, try it out in the Python interpreter!
>>> lst = [3, 2, 7, [84, 83, 82]]
>>> lst[4]
______Error
>>> lst[3][0]
______84
City Data Abstraction
Say we have an abstract data type for cities. A city has a name, a latitude coordinate, and a longitude coordinate.
Our ADT has one constructor:
make_city(name, lat, lon)
: Creates a city object with the given name, latitude, and longitude.
We also have the following selectors in order to get the information for each city:
get_name(city)
: Returns the city's nameget_lat(city)
: Returns the city's latitudeget_lon(city)
: Returns the city's longitude
Here is how we would use the constructor and selectors to create cities and extract their information:
>>> berkeley = make_city('Berkeley', 122, 37)
>>> get_name(berkeley)
'Berkeley'
>>> get_lat(berkeley)
122
>>> new_york = make_city('New York City', 74, 40)
>>> get_lon(new_york)
40
All of the selector and constructor functions can be found in the lab file, if you are curious to see how they are implemented. However, the point of data abstraction 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.
Q2: Distance
We will now implement the function 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. Use the latitude and longitude of a city as
its coordinates; you'll need to use the selectors to access this info!
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)
# Video walkthrough: https://youtu.be/4vB06Ymrico
Use Ok to test your code:
python3 ok -q distance
Q3: 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 the selectors and constructors introduced above and the
distance
function you just defined for this question.
Hint: How can use your
distance
function to find the distance between the given location and each of the given cities?
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)
# Video walkthrough: https://youtu.be/Owwdz_Km87g
Use Ok to test your code:
python3 ok -q closer_city
Q4: Don't violate the abstraction barrier!
Note: this question has no code-writing component (if you implemented
distance
andcloser_city
correctly!)
When writing functions that use an ADT, we should use the constructor(s) and selector(s) whenever possible instead of assuming the ADT's implementation. Relying on a data abstraction's underlying implementation is known as violating the abstraction barrier, and we never want to do this!
It's possible that you passed the doctests for distance
and closer_city
even if you violated the abstraction barrier. To check whether or not you
did so, run the following command:
Use Ok to test your code:
python3 ok -q check_abstraction
The make_check_abstraction
function exists only for the doctest, which swaps
out the implementations of the city
abstraction with something else, runs
the tests from the previous two parts, then restores the original abstraction.
The nature of the abstraction barrier guarantees that changing the implementation of an ADT shouldn't affect the functionality of any programs that use that ADT, as long as the constructors and selectors were used properly.
If you passed the Ok tests for the previous questions but not this one, the fix is simple! Just replace any code that violates the abstraction barrier, i.e. creating a city with a new list object or indexing into a city, with the appropriate constructor or selector.
Make sure that your functions pass the tests with both the first and the second implementations of the City ADT and that you understand why they should work for both before moving on.
Recursion Practice
Q5: Pascal's Triangle
Here's a part of the Pascal's trangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Every number in Pascal's triangle is defined as the sum of the item
above it and the item that is directly to the upper left of it. Use
0
if the entry is empty.
Define the procedure pascal(row, column)
which takes a row and a column,
and finds the value at that position in the triangle. Rows and columns are
zero-indexed; that is, the first row is row 0 instead of 1.
def pascal(row, column):
"""Returns a number corresponding to the value at that location
in Pascal's Triangle.
>>> pascal(0, 0)
1
>>> pascal(0, 5) # Empty entry; outside of Pascal's Triangle
0
>>> pascal(3, 2) # Row 4 (1 3 3 1), 3rd entry
3
"""
"*** YOUR CODE HERE ***"
if column == 0:
return 1
elif row == 0:
return 0
else:
return pascal(row - 1, column) + pascal(row - 1, column - 1)
Use Ok to test your code:
python3 ok -q pascal
Optional Question
This question can be found in lab04_extra.py
.
Q6: Hailstone
Recall the hailstone
function from homework 1. First, pick a
positive integer n
as the start. If n
is even, divide it by 2. If n
is
odd, multiply it by 3 and add 1. Repeat this process until n
is 1. Write a
recursive version of hailstone that prints out the values of the sequence and
returns the number of steps.
Hint: When taking the recursive leap of faith, consider both the return value and side effect of this function.
this_file = __file__
def hailstone(n):
"""Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.
>>> a = hailstone(10)
10
5
16
8
4
2
1
>>> a
7
>>> # Do not use while/for loops!
>>> from construct_check import check
>>> check(this_file, 'hailstone',
... ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"
print(n)
if n == 1:
return 1
elif n % 2 == 0:
return 1 + hailstone(n // 2)
else:
return 1 + hailstone(3 * n + 1)
# Alternate solution with helper function
def hailstone2(n):
def hail_helper(n, count):
print(n)
if n == 1:
return count
else:
if n % 2 == 0:
return hail_helper(n // 2, count + 1)
else:
return hail_helper(3 * n + 1, count + 1)
return hail_helper(n, 1)
# Video walkthrough: https://youtu.be/E4sagKZ2qWc
Use Ok to test your code:
python3 ok -q hailstone