Lab 5: Abstract Data Types
Due at 11:59:59 pm on 2/27/2024.
Starter Files
Download lab05.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
Cities
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. For example, 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.
For example, 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)
For example, 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(city_1, city_2):
"""
>>> city1 = make_city('city1', 0, 1)
>>> city2 = make_city('city2', 0, 2)
>>> distance(city1, city2)
1.0
"""
"*** YOUR CODE HERE ***"
lat_1, lon_1 = get_lat(city_1), get_lon(city_1)
lat_2, lon_2 = get_lat(city_2), get_lon(city_2)
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
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) for
this question. You may also use the distance
function
defined above. Remember, 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 ***"
return <REPLACE THIS>
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: Closer City Abstraction
Run the following ok test to make sure that you are using abstraction barriers correctly! You should not need to change your code from the previous question to pass this test.
Use OK to test your code:
python3 ok -q check_abstraction
Menu
Question 4
For this question, let's combine ADTs and dictionaries to make an ADT that represents a food object. The menu
ADT has a constructor make_food
. There are three selector functions: get_name
, get_size
, and get_price
. When you implement an ADT, you have the freedom to choose how you want to represent it. Some common data structures used to represent ADTs are lists and dictionaries. The city
ADT was implemented using a list. Now, we will use dictionaries to implemt our menu
ADT. You must use a dictionary for this question, or else you will not pass the tests.
Use OK to test your code:
python3 ok -q make_food
python3 ok -q get_food_name
python3 ok -q get_size
python3 ok -q get_price
Submission
When you are done, submit your file to Gradescope. You only need to upload the following files:
lab05.py