Due at 11:59pm on 02/26/2016.

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

• To receive credit for this lab, you must complete Questions 1-7 in lab05.py and submit through OK.
• Questions 2, 5 and 6 are designed to help introduce and test your understanding of concepts.
• Questions 8, 9 and 10 are extremely useful practice with lists and trees. They are not mandatory, but can be very helpful in understanding these topics. They can be found in the lab05_extra.py file.
• Questions 11-12 are extra practice. They can also be found in the lab05_extra.py file. It is recommended that you complete these problems on your own time.

## List Mutation

### Question 1: Map

Write a function that maps a function on the given 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 map(fn, lst):
"""Maps fn onto lst using mutation.
>>> original_list = [5, -1, 2, 0]
>>> map(lambda x: x * x, original_list)
>>> original_list
[25, 1, 4, 0]
"""
"*** YOUR CODE HERE ***"
# Iterative solution
for i in range(len(lst)):
lst[i] = fn(lst[i])

# Recursive solution
def map(fn, lst):
"""Maps fn onto lst using mutation.
>>> original_list = [5, -1, 2, 0]
>>> map(lambda x: x * x, original_list)
>>> original_list
[25, 1, 4, 0]
"""
if lst:  # True when lst != []
temp = lst.pop(0)
map(fn, lst)
lst.insert(0, fn(temp))``````

Use OK to test your code:

``python3 ok -q map``

## Dictionaries

Dictionaries are unordered sets of key-value pairs. Keys can only be immutable types (strings, numbers, tuples), but their corresponding value can be anything! To create a dictionary, use the following syntax:

``>>> singers = { 'Adele': 'Hello', 1975: 'Chocolate', 'The Weeknd': ['The Hills', 'Earned It'] }``

The curly braces denote the key-value pairs in your dictionary. Each key-value pair is separated by a comma. For each pair, the key appears to the left of the colon and the value appears to the right of the colon. Note keys/values do not all have to be the same type, as you can see we have strings, integers and lists! You can retrieve values from your dictionary by "indexing" using the key:

``````>>> singers[1975]
'Chocolate'
>>> songs = singers['The Weeknd']
>>> songs[0]
'The Hills'``````

You can add an entry or update an entry for an existing key in the dictionary using the following syntax. Note they are identical syntax, so be careful!

``````>>> singers['Adele'] = 'Rolling in the Deep'
>>> singers['Adele']
'Rolling in the Deep'
>>> singers['Kanye West'] = 'Real Friends' # New entry!
>>> singers['Kanye West']
'Real Friends'``````

You can also check for membership of keys!

``````>>> 'Adele' in singers
True``````

### Question 2: WWPP: Dictionaries

What would Python print? Type it in the intepreter if you're stuck!

``python3 ok -q dicts -u``
``````>>> pokemon = {'pikachu': 25, 'dragonair': 148, 'mew': 151}
>>> pokemon['pikachu']
______25
>>> len(pokemon)
______3
>>> pokemon['jolteon'] = 135
>>> pokemon['ditto'] = 25
>>> len(pokemon)
______5
>>> sorted(list(pokemon.keys())) # Alphabetically sorted list of pokemon's keys
______['ditto', 'dragonair', 'jolteon', 'mew', 'pikachu']
>>> 'mewtwo' in pokemon
______False
>>> pokemon['ditto'] = pokemon['jolteon']
>>> sorted(list(pokemon.keys())) # Alphabetically sorted list of pokemon's keys
______['ditto', 'dragonair', 'jolteon', 'mew', 'pikachu']
>>> pokemon['ditto']
______135``````

### Question 3: Replace All

Given a dictionary `d`, replace all occurrences of `x` as a value (not a key) with `y`.

Hint: To loop through the keys of a dictionary use `for key in d:`.

``````def replace_all(d, x, y):
"""Replace all occurrences of x as a value (not a key) in d with y.
>>> d = {3: '3', 'foo': 2, 'bar': 3, 'garply': 3, 'xyzzy': 99}
>>> replace_all(d, 3, 'poof')
>>> d == {3: '3', 'foo': 2, 'bar': 'poof', 'garply': 'poof', 'xyzzy': 99}
True
"""
"*** YOUR CODE HERE ***"
for key in d:
if d[key] == x:
d[key] = y``````

Use OK to test your code:

``python3 ok -q replace_all``

### 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() # .split() returns a list of the words in the string. Try printing it!
"*** 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``

## Trees

A `tree` is a data structure that represents a hierarchy of information. A file system is a good example of a tree structure. For example, within your `cs61a` folder, you have folders separating your `projects`, `lab` assignments, and `homework`. The next level is folders that separate different assignments, `hw01`, `lab01`, `hog`, etc., and inside those are the files themselves, including the starter files and `ok`. Below is an incomplete diagram of what your `cs61a` directory might look like.

As you can see, unlike trees in nature, which is where this data structure gets its name from, CS trees are drawn with the root at the top and the leaves at the bottom.

• node: a single unit in a tree.
• root: the node at the top of a tree; every tree has one root node and the node's data we call its label.
• child: a child of a larger tree; has its own root and possibly children of its own.
• subtree: a descendant of a larger tree; a subtree is either a child or a subtree of a child of a larger tree.
• leaf: a node that has no children.

Our `tree` abstract data type consists of a root node and a list of its `children`. To create a tree and access its root and children, use the following constructor and selectors:

• Constructor

• `tree(label, children=[])`: creates a tree object with the given `label` at its root and list of `children`.
• Selectors

• `label(tree)`: returns the value (or label) of the root of the `tree`.
• `children(tree)`: returns the list of children of the given `tree`.
• `is_leaf(tree)`: returns `True` if `tree`'s list of `children` is empty, and `False` otherwise.

For example, the tree generated by

``````t = tree(1, [tree(2),
tree(3, [tree(4), tree(5)]),
tree(6, [tree(7)])])``````

would look like this:

``````   1
/ | \
2  3  6
/ \  \
4   5  7``````

It may be easier to visualize this translation by formatting the code like this:

``````t = tree(1,
[tree(2),
tree(3,
[tree(4),
tree(5)]),
tree(6,
[tree(7)])])``````

To extract the number `3` from this tree, which is the label of the root of its second child, we would do this:

``label(children(t)[1])``

The `print_tree` function prints out a tree in a human-readable form. The exact form follows the pattern illustrated above, where the root's label is unindented, and each of its children is indented one level further.

``````def print_tree(t, indent=0):
"""Print a representation of this tree in which each node is
indented by two spaces times its depth from the label.

>>> print_tree(tree(1))
1
>>> print_tree(tree(1, [tree(2)]))
1
2
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> print_tree(numbers)
1
2
3
4
5
6
7
"""
print('  ' * indent + str(label(t)))
for child in children(t):
print_tree(child, indent + 1)``````

### Question 5: Height & Depth

The depth of a node in a tree is defined as the number of edges between that node and the root. The root has depth 0, its children have depth 1, and so on.

The height of a tree is the depth of the lowest leaf (furthest away from the root).

Test your understanding of depth and height with OK tests using the following command:

``python3 ok -q height_depth -u``

### Question 6: Tree Structure

As described above, trees are constructed recursively with smaller subtrees using the constructor:

``tree(label, children=[])``

Test your understanding of how trees are constructed in Python by examining trees and deciding which of the choices of Python code matches that tree:

``python3 ok -q structure -u``

### Question 7: Acorn Finder

The squirrels on campus need your help! There are a lot of trees on campus and the squirrels would like to know which ones contain acorns. Define the function `acorn_finder`, which takes in a tree and returns `True` if the tree contains a node with the value `'acorn'` and `False` otherwise.

``````def acorn_finder(t):
"""Returns True if t contains a node with the value 'acorn' and
False otherwise.

>>> scrat = tree('acorn')
>>> acorn_finder(scrat)
True
>>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('acorn')]), tree('branch2')])
>>> acorn_finder(sproul)
True
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> acorn_finder(numbers)
False
"""
"*** YOUR CODE HERE ***"
if label(t) == 'acorn':
return True
for child in children(t):
if acorn_finder(child) == True:
return True
return False

# Alternative solution
def acorn_finder(t):
if label(t) == 'acorn':
return True
return any(acorn_finder(c) for c in children(t))    ``````

Use OK to test your code:

``python3 ok -q acorn_finder``

Questions in this section are not required for submission. However, they are very good practice for learning these topics. — they can be found in the the lab05_extra.py file. It is recommended that you complete these problems on your own time.

Python has a `list` class that contains many useful methods. Using the builtin `dir()` function will show you all of them, like so:

``dir(list)``

Some of the most common methods include `append()`, `extend()`, and `pop()`.

``````>>> l = [3, 5, 6]
>>> l.append(10) # Adds an element to the end
>>> l
[3, 5, 6, 10]
>>> l.extend([-1, -6]) # Concatenates another list to the end
>>> l
[3, 5, 6, 10, -1, -6]
>>> l.pop() # Removes and returns the last element
-6
>>> l
[3, 5, 6, 10, -1]
>>> l.pop(2) # Removes and returns the element at the index given
6
>>> l
[3, 5, 10, -1]``````

### Question 8: Filter

Write a function that filters a list, only keeping elements that satisfy the predicate. Be sure to mutate the original list.

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

``````def filter(pred, lst):
"""Filters lst with pred using mutation.
>>> original_list = [5, -1, 2, 0]
>>> filter(lambda x: x % 2 == 0, original_list)
>>> original_list
[2, 0]
"""
"*** YOUR CODE HERE ***"
i = len(lst) - 1
while i >= 0:
if not pred(lst[i]):
lst.pop(i)
i -= 1

def filter(pred, lst):
"""Filters lst with pred using mutation.
>>> original_list = [5, -1, 2, 0]
>>> filter(lambda x: x % 2 == 0, original_list)
>>> original_list
[2, 0]
"""
if lst:
temp = lst.pop(0)
filter(pred, lst)
if pred(temp):
lst.insert(0, temp)``````

Use OK to test your code:

``python3 ok -q filter``

### Question 9: Replace Leaf

Define `replace_leaf`, which takes a tree, a value `old`, and a value `new`. `replace_leaf` returns a new tree where every leaf value equal to `old` has been replaced with `new`.

``````def replace_leaf(t, old, new):
"""Returns a new tree where every leaf value equal to old has
been replaced with new.

>>> yggdrasil = tree('odin',
...                  [tree('balder',
...                        [tree('thor'),
...                         tree('loki')]),
...                   tree('frigg',
...                        [tree('thor')]),
...                   tree('thor',
...                        [tree('sif'),
...                         tree('thor')]),
...                   tree('thor')])
>>> laerad = copy_tree(yggdrasil) # Creates a copy of yggdrasil, only for testing purposes
>>> print_tree(replace_leaf(yggdrasil, 'thor', 'freya'))
odin
balder
freya
loki
frigg
freya
thor
sif
freya
freya
>>> laerad == yggdrasil # Make sure original tree is unmodified
True
"""
"*** YOUR CODE HERE ***"
if is_leaf(t) and label(t) == old:
return tree(new)
else:
new_children = [replace_leaf(child, old, new) for child in children(t)]
return tree(label(t), new_children)``````

Use OK to test your code:

``python3 ok -q replace_leaf``

### Question 10: Tree Map

Define the function `tree_map`, which takes in a tree and a one-argument function as arguments and returns a new tree which is the result of mapping the function over the entries of the input tree.

``````def tree_map(fn, t):
"""Maps the function fn over the entries of tree and returns the
result in a new tree.

>>> numbers = tree(1,
...                [tree(2,
...                      [tree(3),
...                       tree(4)]),
...                 tree(5,
...                      [tree(6,
...                            [tree(7)]),
...                       tree(8)])])
>>> print_tree(tree_map(lambda x: 2**x, numbers))
2
4
8
16
32
64
128
256
"""
"*** YOUR CODE HERE ***"
if children(t) == []:
return tree(fn(label(t)), [])
mapped_subtrees = []
for subtree in children(t):
mapped_subtrees += [ tree_map(fn, subtree) ]
return tree(fn(label(t)), mapped_subtrees)

# Alternate solution
def tree_map(fn, t):
return tree(fn(label(t)), [tree_map(fn, t) for t in children(t)])``````

Use OK to test your code:

``python3 ok -q tree_map``

## Extra Questions

Questions in this section are also not required for submission. We encourage you to try them out on your own time for extra practice.

### Question 11: Reverse

Write a function that reverses the given 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 reverse(lst):
"""Reverses lst using mutation.

>>> original_list = [5, -1, 29, 0]
>>> reverse(original_list)
>>> original_list
[0, 29, -1, 5]
>>> odd_list = [42, 72, -8]
>>> reverse(odd_list)
>>> odd_list
[-8, 72, 42]
"""
"*** YOUR CODE HERE ***"
# 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]
>>> odd_list = [42, 72, -8]
>>> reverse(odd_list)
>>> odd_list
[-8, 72, 42]
"""
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]
>>> odd_list = [42, 72, -8]
>>> reverse(odd_list)
>>> odd_list
[-8, 72, 42]
"""
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 reverse``

### Question 12: Preorder

Define the function `preorder`, which takes in a tree as an argument and returns a list of all the entries in the tree in the order that `print_tree` would print them.

Note: This ordering of the nodes in a tree is called a preorder traversal.

``````def preorder(t):
"""Return a list of the entries in this tree in the order that they
would be visited by a preorder traversal (see problem description).

>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> preorder(numbers)
[1, 2, 3, 4, 5, 6, 7]
>>> preorder(tree(2, [tree(4, [tree(6)])]))
[2, 4, 6]
"""
"*** YOUR CODE HERE ***"
if children(t) == []:
return [label(t)]
flattened_children = []
for child in children(t):
flattened_children += preorder(child)
return [label(t)] + flattened_children

# Alternate solution
from functools import reduce

def preorder(t):
return reduce(add, [preorder(child) for child in children(t)], [label(t)])``````

Use OK to test your code:

``python3 ok -q preorder``