Lab 5: ADT and Dictionary Review
Due at 11:59:59 pm on 03/02/2020.

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.

• To receive full credit for this lab, all questions must be attempted.

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.

Using Abstractions

In this problem you will fill out three functions to complete the Group ADT and the Diner ADT. The goal is to organize how diners manage the groups that want to eat there and the tables where these groups sit.

It is important to take the time to read through the docstrings and the doctests. Additionally, make sure to not violate abstraction barriers for other ADTs, i.e. when implementing functions for the Diner ADT, do not violate abstraction barriers for the Group ADT, and vice versa.

# Diner ADT
def make_diner(name):
    """ Diners are represented by their name and the number of free tables they have."""
    return [name, 0]

def num_free_tables(diner):
    return diner[1]

def name(diner):
    return diner[0]
# You will implement add_table and serve which are part of the Diner ADT
# Group ADT
def make_group(name):
    """ Groups are represented by their name and their status."""
    return [name, 'waiting']

def name(group):
    return group[0]

def status(group):
    return group[1]

def start_eating(group, diner):
    group[1] = 'eating'

# You will implement finish_eating which is part of the Group ADT    

Question 1

Implement add_table which increases the diner's number of free tables by 1:

def add_table(diner):
    """
    >>> din = make_diner("Croads")
    >>> num_free_tables(din)
    0
    >>> add_table(din)
    >>> add_table(din)
    >>> num_free_tables(din)
    2
    """
    "*** YOUR CODE HERE ***"
    diner[1] += 1

Use OK to test your code:

python3 ok -q add_table

Question 2

Implement serve so that the diner uses one of its free tables to seat the group. If there are no free tables, return the string 'table not free'. If there are free tables, the group's status should be updated to 'eating' and the diner should have one less free table.

def serve(diner, group):
    """
    >>> din = make_diner("Cafe 3")
    >>> add_table(din)
    >>> g1 = make_group("Vandana's Group")
    >>> g2 = make_group("Shreya's Group")
    >>> serve(din, g1)
    >>> status(g1)
    'eating'
    >>> num_free_tables(din)
    0
    >>> serve(din, g2)
    'table not free'
    >>> status(g2)
    'waiting'
    """
    "*** YOUR CODE HERE ***"
    if diner[1] > 0:
        diner[1] -= 1
        start_eating(group, diner)
    else:
        return 'table not free'

Use OK to test your code:

python3 ok -q serve

Question 3

Implement finish_eating which sets a group's status to 'finished' and frees the table they were using so that the diner has one more free table.

def finish_eating(group, diner):
    """
    >>> din = make_diner("Foothill")
    >>> add_table(din)
    >>> g1 = make_group("Nick's Group")
    >>> serve(din, g1)
    >>> num_free_tables(din)
    0
    >>> finish_eating(g1, din)
    >>> num_free_tables(din)
    1
    >>> status(g1)
    'finished'
    """
    "*** YOUR CODE HERE ***"
    group[1] = 'finished'
    add_table(diner)

Use OK to test your code:

python3 ok -q finish_eating

Dictionary Review

Question 4: 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 5: 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