CS88 | Lab 5: Dictionaries and Abstract Data Types

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.

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. See this article for more instructions on okpy and submitting assignments.

When you are ready to submit, run ok with the --submit option:

python3 ok --submit

After submitting, ok will display a submission URL, with which you can view your submission on okpy.org.

ADTs - 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

Dictionaries

Question 4: Counter

Implement the function counter which takes in a string of words, and returns a dictionary where each key is a word in the message, and each value is the number of times that word is present in the original string.

def counter(message):
    """ Returns a dictionary of each word in message mapped
    to the number of times it appears in the input string.

    >>> x = counter('to be or not to be')
    >>> x['to']
    2
    >>> x['be']
    2
    >>> x['not']
    1
    >>> y = counter('run forrest run')
    >>> y['run']
    2
    >>> y['forrest']
    1
    """
    word_list = message.split()
    "*** YOUR CODE HERE ***"
    
    result_dict = {}
    for word in word_list:
        if word in result_dict:
            result_dict[word] += 1
        else:
            result_dict[word] = 1
    return result_dict

Use OK to test your code:

python3 ok -q counter

Question 5: Replace All

Given a dictionary d, return a new dictionary where all occurences of x as a value (not a key) is replaced with y.

def replace_all(d, x, y):
    """
    >>> d = {'foo': 2, 'bar': 3, 'garply': 3, 'xyzzy': 99}
    >>> e = replace_all(d, 3, 'poof')
    >>> e == {'foo': 2, 'bar': 'poof', 'garply': 'poof', 'xyzzy': 99}
    True
    """
    "*** YOUR CODE HERE ***"
    
    new = {}
    for key in d:
        if d[key] == x:
            new[key] = y
        else:
            new[key] = d[key]
    return new

Use OK to test your code:

python3 ok -q replace_all

Question 6: Build the Full Rosters

Implement the function common_players. The common_players function identifies which keys from the full_roster share the same values. The function returns a new dictionary where each key is the value from the original dictionary, and the corresponding values of the new dictionary are list that contain keys that share the same value.

def common_players(roster):
    """Returns a dictionary containing values along with a corresponding
    list of keys that had that value from the original dictionary.
    >>> full_roster = {"bob": "Team A", "barnum": "Team B", "beatrice": "Team C", "bernice": "Team B", "ben": "Team D", "belle": "Team A", "bill": "Team B", "bernie": "Team B", "baxter": "Team A"}
    >>> common_players(full_roster)
    {'Team A': ['bob', 'belle', 'baxter'], 'Team B': ['barnum', 'bernice', 'bill', 'bernie'], 'Team C': ['beatrice'], 'Team D': ['ben']}
    """
    "*** YOUR CODE HERE ***"
    
    result_dict = {}
    for player in roster:
        team = roster[player]
        if team in result_dict:
            result_dict[team] += [player]
        else:
            result_dict[team] = [player]
    return result_dict

Use OK to test your code:

python3 ok -q common_players

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Lab 5: Dictionaries and Abstract Data Types Due at 11:59:59 pm on 10/05/2021.

Starter Files

Submission

ADTs - Cities

Question 1: Distance

Question 2: Closer city

Question 3: Closer City Abstraction

Dictionaries

Question 4: Counter

Question 5: Replace All

Question 6: Build the Full Rosters

Submit

Lab 5: Dictionaries and Abstract Data Types
Due at 11:59:59 pm on 10/05/2021.