Lab 5 Solutions
Solution Files
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.
List Comprehensions
List comprehensions are a compact and powerful way of creating new lists out of sequences. The general syntax for a list comprehension is the following:
[<expression> for <element> in <sequence> if <conditional>]
where the if <conditional>
section is optional.
The syntax is designed to read like English: "Compute the expression for each element in the sequence (if the conditional is true for that element)."
>>> [i**2 for i in [1, 2, 3, 4] if i % 2 == 0]
[4, 16]
This list comprehension will:
- Compute the expression
i**2
- For each element
i
in the sequence[1, 2, 3, 4]
- Where
i % 2 == 0
(i
is an even number),
and then put the resulting values of the expressions into a new list.
In other words, this list comprehension will create a new list that contains
the square of every even element of the original list [1, 2, 3, 4]
.
We can also rewrite a list comprehension as an equivalent for
statement,
such as for the example above:
>>> lst = []
>>> for i in [1, 2, 3, 4]:
... if i % 2 == 0:
... lst = lst + [i**2]
>>> lst
[4, 16]
Sequences
Sequences are ordered collections of values that support element-selection and have length. We've worked with lists, but other Python types are also sequences, including strings.
Let us go through an example of some actions we can do with strings.
>>> x = 'Hello there Oski!'
>>> x
'Hello there Oski!'
>>> len(x)
17
>>> x[6:]
'there Oski!'
>>> x[::-1]
'!iksO ereht olleH'
Since strings are sequences, we can do with strings many of the same things that we can do to lists. We can even loop through a string just like we can with a list:
>>> x = 'I am not Oski.'
>>> vowel_count = 0
>>> for i in range(len(x)):
... if x[i] in 'aeiou':
... vowel_count += 1
>>> vowel_count
5
Data Abstraction
Data abstraction is a powerful concept in computer science that allows programmers to treat code as objects. For example, using code to represent cars, chairs, people, and so on. 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. If 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 to do so. You just have to know how to use the car for driving itself, such as how to turn the wheel or press the gas pedal.
A data abstraction 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 data abstractions 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 abstraction allows whoever uses them to assume that the functions have been written correctly and work as described.
Required Questions
Getting Started Videos
These videos may provide some helpful direction for tackling the coding problems on this assignment.
To see these videos, you should be logged into your berkeley.edu email.
Lists
Q1: Flatten
Write a function flatten
that takes a list and returns a
"flattened" version of it. The input list could be a deep list,
meaning that there could be a multiple layers of nesting
within the list.
Make sure your solution does not mutate the input list.
For example, one use case of flatten
could be the following:
>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]
Hint: you can check if something is a list by using the built-in
type
function. For example:>>> type(3) == list False >>> type([1, 2, 3]) == list True
def flatten(s):
"""Returns a flattened version of list s.
>>> flatten([1, 2, 3]) # normal list
[1, 2, 3]
>>> x = [1, [2, 3], 4] # deep list
>>> flatten(x)
[1, 2, 3, 4]
>>> x # Ensure x is not mutated
[1, [2, 3], 4]
>>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
>>> flatten(x)
[1, 1, 1, 1, 1, 1]
>>> x
[[1, [1, 1]], 1, [1, 1]]
>>> x = [[1, [2, 3], [4, [5, 6]]]]
>>> flatten(x)
[1, 2, 3, 4, 5, 6]
>>> x
[[1, [2, 3], [4, [5, 6]]]]
>>> x = [[1, [1, [1, [1, 1, [1, 1, [1]]]], 1]]]
>>> flatten(x)
[1, 1, 1, 1, 1, 1, 1, 1, 1]
>>> x
[[1, [1, [1, [1, 1, [1, 1, [1]]]], 1]]]
"""
lst = []
for elem in s:
if type(elem) == list:
lst += flatten(elem)
else:
lst += [elem]
return lst
# Alternate solution
if not s:
return []
elif type(s[0]) == list:
return flatten(s[0]) + flatten(s[1:])
else:
return [s[0]] + flatten(s[1:])
Use Ok to test your code:
python3 ok -q flatten
Sequences
Many languages provide map
, filter
, reduce
functions for sequences.
Python also provides these functions
(and we'll formally introduce them later on in the course),
but to help you better understand how they work,
you'll be implementing these functions in the following problems.
In Python, the
map
andfilter
built-ins have slightly different behavior than themy_map
andmy_filter
functions we are defining here.
Q2: Map
my_map
takes in a one argument function fn
and a sequence seq
and returns a
list containing fn
applied to each element in seq
.
Use only a single line for the body of the function. (Hint: use a list comprehension.)
def my_map(fn, seq):
"""Applies fn onto each element in seq and returns a list.
>>> my_map(lambda x: x*x, [1, 2, 3])
[1, 4, 9]
>>> my_map(lambda x: abs(x), [1, -1, 5, 3, 0])
[1, 1, 5, 3, 0]
>>> my_map(lambda x: print(x), ['cs61a', 'spring', '2023'])
cs61a
spring
2023
[None, None, None]
"""
return [fn(elem) for elem in seq]
Use Ok to test your code:
python3 ok -q my_map
Use Ok to run the local syntax checker (which checks that you used only a single line for the body of the function):
python3 ok -q my_map_syntax_check
Q3: Filter
my_filter
takes in a predicate function pred
and a sequence seq
and returns a
list containing all elements in seq
for which pred
returns True
. (A predicate function
is a function that takes in an argument and returns either True
or False
.)
Use only a single line for the body of the function. (Hint: use a list comprehension.)
def my_filter(pred, seq):
"""Keeps elements in seq only if they satisfy pred.
>>> my_filter(lambda x: x % 2 == 0, [1, 2, 3, 4]) # new list has only even-valued elements
[2, 4]
>>> my_filter(lambda x: (x + 5) % 3 == 0, [1, 2, 3, 4, 5])
[1, 4]
>>> my_filter(lambda x: print(x), [1, 2, 3, 4, 5])
1
2
3
4
5
[]
>>> my_filter(lambda x: max(5, x) == 5, [1, 2, 3, 4, 5, 6, 7])
[1, 2, 3, 4, 5]
"""
return [elem for elem in seq if pred(elem)]
Use Ok to test your code:
python3 ok -q my_filter
Use Ok to run the local syntax checker (which checks that you used only a single line for the body of the function):
python3 ok -q my_filter_syntax_check
Q4: Reduce
my_reduce
takes in a two argument function combiner
and a non-empty sequence
seq
and combines the elements in seq
into one value using combiner
.
def my_reduce(combiner, seq):
"""Combines elements in seq using combiner.
seq will have at least one element.
>>> my_reduce(lambda x, y: x + y, [1, 2, 3, 4]) # 1 + 2 + 3 + 4
10
>>> my_reduce(lambda x, y: x * y, [1, 2, 3, 4]) # 1 * 2 * 3 * 4
24
>>> my_reduce(lambda x, y: x * y, [4])
4
>>> my_reduce(lambda x, y: x + 2 * y, [1, 2, 3]) # (1 + 2 * 2) + 2 * 3
11
"""
total = seq[0]
for elem in seq[1:]:
total = combiner(total, elem)
return total
# Alternate solution
def my_reduce_alternate(combiner, seq):
def helper(curr, seq):
if len(seq) == 0:
return curr
return helper(combiner(curr, seq[0]), seq[1:])
return helper(seq[0], seq[1:])
Use Ok to test your code:
python3 ok -q my_reduce
Data Abstraction
Say we have an abstract data type for cities. A city has a name, a latitude coordinate, and a longitude coordinate.
Our data abstraction 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.
Q5: 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(city_a, city_b):
"""
>>> city_a = make_city('city_a', 0, 1)
>>> city_b = make_city('city_b', 0, 2)
>>> distance(city_a, city_b)
1.0
>>> city_c = make_city('city_c', 6.5, 12)
>>> city_d = make_city('city_d', 2.5, 15)
>>> distance(city_c, city_d)
5.0
"""
lat_1, lon_1 = get_lat(city_a), get_lon(city_a)
lat_2, lon_2 = get_lat(city_b), get_lon(city_b)
return sqrt((lat_1 - lat_2)**2 + (lon_1 - lon_2)**2)
Use Ok to test your code:
python3 ok -q distance
Q6: 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 you use your
distance
function to find the distance between the given location and each of the given cities?
def closer_city(lat, lon, city_a, city_b):
"""
Returns the name of either city_a or city_b, whichever is closest to
coordinate (lat, lon). If the two cities are the same distance away
from the coordinate, consider city_b to be the closer city.
>>> 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'
"""
new_city = make_city('arb', lat, lon)
dist1 = distance(city_a, new_city)
dist2 = distance(city_b, new_city)
if dist1 < dist2:
return get_name(city_a)
return get_name(city_b)
Use Ok to test your code:
python3 ok -q closer_city
Q7: Don't violate the abstraction barrier!
Note: this question has no code-writing component (if you implemented the previous two questions correctly).
When writing functions that use an data abstraction, we should use the constructor(s) and selector(s) whenever possible instead of assuming the data abstraction'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 the previous questions 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_city_abstraction
The check_city_abstraction
function exists only for the doctest, which swaps
out the implementations of the original 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 data abstraction shouldn't affect the functionality of any programs that use that data abstraction, 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 with the appropriate constructor or selector.
Make sure that your functions pass the tests with both the first and the second implementations of the data abstraction and that you understand why they should work for both before moving on.
Check Your Score Locally
You can locally check your score on each question of this assignment by running
python3 ok --score
This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.
Submit
Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.
Optional Questions
These questions are optional, but you must complete them in order to be checked off before the end of the lab period. They are also useful practice!
Q8: Count Palindromes
The Python library defines filter
, map
, and reduce
, which operate
on Python sequences. Devise a function that counts the number of
palindromic words (those that read the same backwards as forwards) in a
tuple of words using only lambda
, basic operations on strings, the
tuple constructor, conditional expressions, and the functions filter
,
map
, and reduce
. Specifically, do not use recursion or any kind of
loop:
def count_palindromes(L):
"""The number of palindromic words in the sequence of strings
L (ignoring case).
>>> count_palindromes(("Acme", "Madam", "Pivot", "Pip"))
2
"""
return len(list(filter(lambda s: s.lower() == s[::-1].lower(), L)))
Hint: The easiest way to get the reversed version of a string
s
is to use the Python slicing notation tricks[::-1]
. Also, the functionlower
, when called on strings, converts all of the characters in the string to lowercase. For instance, if the variables
contains the string "PyThoN", the expressions.lower()
evaluates to "python".
Use Ok to test your code:
python3 ok -q count_palindromes
Q9: Coordinates
Implement a function coords
that takes a function fn
, a sequence seq
,
and a lower
and upper
bound on the output of the function. coords
then
returns a list of coordinate pairs (lists) such that:
- Each (x, y) pair is represented as
[x, fn(x)]
- The x-coordinates are elements in the sequence
- The result contains only pairs whose y-coordinate is within the upper and lower bounds (inclusive)
See the doctest for examples.
Note: your answer can only be one line long. You should make use of list comprehensions!
def coords(fn, seq, lower, upper):
"""
>>> seq = [-4, -2, 0, 1, 3]
>>> fn = lambda x: x**2
>>> coords(fn, seq, 1, 9)
[[-2, 4], [1, 1], [3, 9]]
"""
return [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]
Use Ok to test your code:
python3 ok -q coords
Reflect: What are the drawbacks to the one-line answer, in terms of using computer resources?