Due at 11:59pm on Friday, 02/22/2019.
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
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 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, ]]
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 6 >>> lst 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
>>> 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 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.
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 = , then the answer would be
x. You can use the
interpreter or Python Tutor to experiment with your answers.
>>> x = [1, 3, [5, 7], 9]______x>>> x = [[3, [5, 7], 9]]______x
What would Python display? If you get stuck, try it out in the Python interpreter!
>>> lst = [3, 2, 7, [84, 83, 82]] >>> lst______Error>>> lst______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 name
get_lat(city): Returns the city's latitude
get_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.
We will now implement the function
distance, which computes the
distance between two city objects. Recall that the distance between two
(x1, y1) and
(x2, y2) can be found by calculating
(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
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
distancefunction 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
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
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
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.
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
This question can be found in
hailstone function from homework 1. First, pick a
n as the start. If
n is even, divide it by 2. If
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