Solutions: You can find the file with solutions for all questions here.

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

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']]
"""
return [elem if not isinstance(elem, list) else deep_copy(elem) for elem in lst]``````

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

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!

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'])]
"""
keys = list(dictionary.keys())
for key in keys:
val = dictionary.pop(key)
dictionary[val[0]] = val[1:] + [key]``````

Use OK to test your code:

``python3 ok -q dict_cycle``

### 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():
>>> add, get_list, reverse = todo()
>>> get_list()
['clean', 'homework', 'cook', 'sleep']
>>> reverse()
>>> get_list()
['sleep', 'cook', 'homework', 'clean']
>>> get_list()
['sleep', 'cook', 'homework', 'clean', 'wake up']
>>> reverse()
>>> get_list()
['wake up', 'clean', 'homework', 'cook', 'sleep']
"""
lst = []
def get_list():
return lst
lst.append(item)
def reverse():
# iterative solution
midpoint = len(lst) // 2
last = len(lst) - 1
for i in range(midpoint):
lst[i], lst[last - i] = lst[last - i], lst[i]
# Recursive solution
def reverse(lst):
"""Reverses lst using mutation.
>>> original_list = [5, -1, 29, 0]
>>> reverse(original_list)
>>> original_list
[0, 29, -1, 5]
"""
if len(lst) > 1:
temp = lst.pop()
reverse(lst)
lst.insert(0, temp)

# Alternative recursive solution
def reverse(lst):
"""Reverses lst using mutation.
>>> original_list = [5, -1, 29, 0]
>>> reverse(original_list)
>>> original_list
[0, 29, -1, 5]
"""
midpoint = len(lst) // 2
last = len(lst) - 1
def helper(i):
if i == midpoint:
return
lst[i], lst[last - i] = lst[last - i], lst[i]
helper(i + 1)
helper(0)

Use OK to test your code:

``python3 ok -q todo``

### Question 4: Mailbox

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")
>>> get_mail("Lyric")
>>> 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"])
>>> get_mail("Amir")
"""
mailbox = {}
def get_mail(name):
if len(mailbox) == 0 or name not in mailbox or mailbox[name] == None:
return None
mail = mailbox[name]
mailbox[name] = None
return mail
def deliver_mail(name, mail):
if len(mailbox) == 0 or name not in mailbox or mailbox[name] == None:
mailbox[name] = mail
else:
mailbox[name] += mail
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["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"}

pokemon_set[pokemon] = evolution

def evolve(pokemon):
if pokemon not in pokemon_set:
return pokemon
else:
return evolve(pokemon_set[pokemon])

def evolve_all(gym):
for i in range(gym_size(gym)):
gym[i] = evolve(gym[i])

``python3 ok -q make_pokemon_set``