Homework 8

Due at 11:59:59 pm on Thursday, 11/07/2019.

Instructions

Download hw08.zip. Inside the archive, you will find starter files for the questions in this homework, along with a copy of the OK autograder.

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

Readings: This homework relies on following references:

Unexpected Behavior

Question 1: The Mutation Mystery

You just got a new job as the official code detective of UC Berkeley. You just got your first assignment on the job! There have been 3 reported cases of unusual list behavior from students who are writing python code for CS88. You're no python expert yet, but you've been studying up on the details of how python works. You're ready to investigate this mystery!


Case #1

The first case was brought to you by Alice Listmaker. Alice created two identical lists, x and y. She then wanted to modify only y. However, she was surprised to see that x had been modified too! Use the command below to see what happened.

 python3 ok -q case1 -u

Hmm... what could have gone wrong here? Here are some clues that will help you figure this out:

  1. This environment diagram
  2. Slicing, such as x[:], creates a new list.
  3. The list function, list(x), creates a new list.

You think you have found a fix using slicing and the list function. Use the command below to confirm that you have solved the mystery!

 python3 ok -q case1_solved -u

Case #2

The second report of unusual list behavior came from Alice's cousin, Bob Listmaker. Unlike Alice, Bob knew about slicing and the list function. However, he was still a victim of mutation. Let's take a look at what happened to Bob's lists using the command below.

 python3 ok -q case2 -u

Here are some clues as to what caused this error:

  1. Slicing and the list function do create new lists, but do not deep copy the values.
  2. This environment diagram
  3. This article on shallow vs. deep copy

You have figured out that Bob needs to perform a deep copy on his lists. You decide to write a deep_copy function for Bob to use. Fill in the body of the function. Do NOT use the copy module shown in the article, you need to write your own function!

def deep_copy(lst):
    """Returns a new list that is a deep copy of lst.
    >>> x = [[0, 'a'],  [1, 'b'], [2, 'c']]
    >>> y = deep_copy(x)
    >>> y[0][1] = 'z'
    >>> y
    [[0, 'z'], [1, 'b'], [2, 'c']]
    >>> x
    [[0, 'a'], [1, 'b'], [2, 'c']]
    >>> x = [[0, 'a'],  [1, 'b'], [2, 'c']]
    >>> z = deep_copy(x)
    >>> z[0][1] = 'z'
    >>> z
    [[0, 'z'], [1, 'b'], [2, 'c']]
    >>> x       #x should not change
    [[0, 'a'], [1, 'b'], [2, 'c']]
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q deep_copy

Case #3

After solving those first two cases, you're ready to tackle the final challenge. This case was brought to you by Eve (she doesn't have a list-related last name, sorry). Eve knew that she was not properly deep copying her lists. However, she could not figure out why this only caused problems some of the time. Let's investigate further.

 python3 ok -q case3 -u

Your final clues:

  1. This environment diagram
  2. Lists contain pointers to other lists.
  3. There are no pointers to strings or numbers, the values are stored directly.

Congratulations, you have solved the mutation mystery!


Additional unusual list behavior

  1. Adding elements to a list using + creates a new list.
  2. Adding elements to a list using += does not create a new list.
  3. Adding elements to a list using .append() does not create a new list.

Take a look at this environment diagram to see an example of this. Pay close attention to the difference between using + and += in the example with y and z.

Dictionaries and Mutation

Question 2: Dictionary Cycle

Build a function that takes in a dictionary. Each of the keys in the dictionary is mapped to a list. Build the function such that the dictionary is modified so that the key becomes the last item in the list, and the first item in the list becomes the new key. Hint: You may find the method dict.pop() useful. Works similarly to lst.pop()! 

def dict_cycle(dictionary):
    """Write a function that cycles each of the key-value pair such that the key becomes the last
        item in the value list, and the first item of the list becomes the new key. 

    >>> hamster = {"a":["b","c","d"], "w":["x","y","z"]}
    >>> dict_cycle(hamster)
    >>> sorted(hamster.items()) # items return list of tuples that are key value pairs
    [('b', ['c', 'd', 'a']), ('x', ['y', 'z', 'w'])]
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q dict_cycle

Mutation and ADT's

Question 3: reverse-todo

We have a todo list ADT. So far it supports adding items and returning the whole list. Let's say our priorities changed and we want to complete our tasks in the reverse order of the list.

Extend our todo list ADT by adding a function that reverses the todo list. Be sure to mutate the original list!

This function should NOT return anything. This is to emphasize that this function should utilize mutability.

def todo():
    """Returns add and reverse, which add to and reverse the list
    >>> add, get_list, reverse = todo()
    >>> add("clean")
    >>> add("homework")
    >>> add("cook")
    >>> add("sleep")
    >>> get_list()
    ['clean', 'homework', 'cook', 'sleep']
    >>> reverse()
    >>> get_list()
    ['sleep', 'cook', 'homework', 'clean']
    >>> add("wake up")
    >>> get_list()
    ['sleep', 'cook', 'homework', 'clean', 'wake up']
    >>> reverse()
    >>> get_list()
    ['wake up', 'clean', 'homework', 'cook', 'sleep']
    """
    lst = []
    def get_list():
        return lst
    def add(item):
        lst.append(item)
    def reverse():
        "*** YOUR CODE HERE ***"
        
    return add, get_list, reverse

Use OK to test your code:

python3 ok -q todo

Question 4: Mailbox

Mutation is crucial for ADTs.

Below, we can see the power of mutability which allows us to change the name and amount of money in account_1.

>>> account_1 = account("Sophia", 10)
>>> get_account_name(account_1)
Sophia
>>> change_account_name(account_1, "Julia")
>>> get_account_name(account_1)
Julia
>>> deposit(account_1, 20)
>>> get_account_savings(account_1)
30
>>> withdraw(account_1, 10)
>>> get_account_savings(account_1)
20

Let's apply this concept to a new ADT: a mailbox. The mail box's internal representation is a dictionary that holds key value pairs corresponding to a person, and a list of their mail. Below is an example of a TA mailbox.

{"Sophia":["receipt", "worksheets"], "Lyric":["worksheets", "form", "bills"], "Andrew":["paycheck"], "Julia":None, "John":None, "Amir":None}

The get_mail(name) function, given a mailbox, should return the mail corresponding to the name argument given. The postman can also put in mail by using the deliver_mail(name, mail) function.

Please provide implementations for these functions. Make sure to mutate the dictionary! (You can assume mail will always be in a list.)

def mailbox():
    """
    >>> get_mail, deliver_mail = mailbox()
    >>> get_mail("Sophia")
    >>> deliver_mail("Sophia", ["postcard"])
    >>> get_mail("Sophia")
    ['postcard']
    >>> get_mail("Sophia")
    >>> deliver_mail("Lyric", ["paycheck", "ads"])
    >>> get_mail("Lyric")
    ['paycheck', 'ads']
    >>> deliver_mail("Lyric", ["bills"])
    >>> get_mail("Lyric")
    ['bills']
    >>> deliver_mail("Julia", ["survey"])
    >>> get_mail("Julia")
    ['survey']
    >>> get_mail("Julia")
    >>> get_mail("Amir")
    >>> deliver_mail("Amir", ["postcard", "paycheck"])
    >>> deliver_mail("Amir", ["ads"])
    >>> get_mail("Amir")
    ['postcard', 'paycheck', 'ads']
    """
    mailbox = {}
    def get_mail(name):
        "*** YOUR CODE HERE ***"
        
    def deliver_mail(name, mail):
        "*** YOUR CODE HERE ***"
        
    return get_mail, deliver_mail

Use OK to test your code:

python3 ok -q mailbox

Optional

Question 5: Pokemon

Remember the good old days when we played Pokemon Go? Complete the implementation of a Pokemon ADT below by filling out add_pokemon, evolve, and evolve_all.

def make_gym(a, b, c, d):
    """Returns a pokemon gym (represented by list) of the four pokemons a, b, c, d."""
    return [a, b, c, d]

def gym_size(gym):
    """Returns the size of the gym."""
    return len(gym)

def make_pokemon_set():
    """Returns a dictionary of pokemon methods.

    >>> my_pokemons = make_pokemon_set()
    >>> my_pokemons["add"]("pikachu", "raichu")
    >>> my_pokemons["evolve"]("charmander")
    'charizard'
    >>> my_pokemons["evolve"]("celebi")
    'celebi'
    >>> my_gym = make_gym("charmander", "celebi", "pikachu", "rattata")
    >>> my_pokemons["evolve_all"](my_gym)
    >>> my_gym
    ['charizard', 'celebi', 'raichu', 'raticate']

    """
    pokemon_set = {"charmander":"charmeleon",
            "charmeleon":"charizard",
            "squirtle":"wartortle",
            "wartortle":"blastoise",
            "rattata":"raticate",
            "sandshrew":"sandslash"}

    def add(pokemon, evolution):
        "*** YOUR CODE HERE ***"
        

    def evolve(pokemon):
        "*** YOUR CODE HERE ***"
        

    def evolve_all(gym):
        "*** YOUR CODE HERE ***"
        

    return {"add":add, "evolve":evolve, "evolve_all":evolve_all}

Use OK to test your code:

python3 ok -q make_pokemon_set