Lab 6: Mutable Sequences

Due at 11:59pm on Tuesday, 07/11/2017.

Starter Files

Download lab06.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.

  • Questions 1 through 6 must be completed in order to receive credit for this lab.
  • Questions 7 through 9 are optional. It is recommended that you complete these problems on your own time.

Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.

List Methods

Python's 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]

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! Each key only appears once in a dictionary. 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! You might end updating (and overwriting an old value) even if you intended to add, and vice versa.

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

Finally, here are some useful dictionary functions:

  • dict.keys() will return a sequence of keys.

    >>> list(singers.keys()) # We use list() to turn the sequence into a list
[1975, 'The Weeknd', 'Adele']

  • dict.values() will return a sequence of values.

    >>> list(singers.values())
['Chocolate', ['The Hills', 'Earned It'], 'Hello']

  • dict.items() will return a sequences of keys-value pairs.

    >>> list(singers.items())
[(1975, 'Chocolate'), ('The Weeknd', ['The Hills', 'Earned It']), ('Adele', 'Hello')]

Required Questions

WWPD?

Question 1: WWPD

Use OK to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q lists -u
>>> lst = [1, 2, 3, 4, 5, 6]
>>> lst[4] = 1
>>> lst

______
[1, 2, 3, 4, 1, 6]

>>> lst[2:4] = [9, 8]
>>> lst

______
[1, 2, 9, 8, 1, 6]

>>> lst[3] = ['hi', 'bye']
>>> lst

______
[1, 2, 9, ['hi', 'bye'], 1, 6]
>>> lst[3:] = ['oski', 'bear']
>>> lst

______
[1, 2, 9, 'oski', 'bear']

>>> lst[1:3] = [2, 3, 4, 5, 6, 7, 8]
>>> lst

______
[1, 2, 3, 4, 5, 6, 7, 8, 'oski', 'bear']
>>> lst == lst[:]

______
True

>>> lst is lst[:]

______
False

>>> a = lst[:]
>>> a[0] = 'oogly'
>>> lst

______
[1, 2, 3, 4, 5, 6, 7, 8, 'oski', 'bear']

Question 2: WWPD: Lists

Use OK to test your knowledge with the following question.

python3 ok -q box-pointer -u
  >>> s = [[1, [2]]]
  >>> t = s
  >>> t[0][1] = s[:]

  Which box-and-pointer diagram corresponds to the above code?

    s, t:
           +---+    +-------+   +---+    +---+    +-------+    +---+
    s ---> | x----> | 1 | x---->| x----> | x----> | 1 | x----> | 2 |
           +---+    +-------+   +---+    +---+    +-------+    +---+
    t ---/

    s, t:
           +---+    +-------+    +---+
    s ---> | x----> | 1 | x----> | 2 |
           +---+    +-------+    +---+
           ^
            \---------------------|
           +---+    +-------+   +-|-+
    t ---> | x----> | 1 | x---->| x |
           +---+    +-------+   +---+

    s, t:
           +---+    +-------+    +---+
    s ---> | x----> | 1 | x----> | x |
           +---+    +-------+    +-|-+
    t ---/          ^              /
                     \------------/

    s, t:
           +---+    +-------+    +---+
    s ---> | x----> | 1 | x----> | 2 |
           +---+    +-------+    +---+
                    ^
                     \---------------------|
           +---+    +-------+   +---+    +-|-+
    t ---> | x----> | 1 | x---->| x----> | x |
           +---+    +-------+   +---+    +---+

Question 3: WWPD: Dictionaries

What would Python display? 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
>>> letters = {'a': 1, 'b': 2, 'c': 3}
>>> 'a' in letters

______
True

>>> 2 in letters

______
False
>>> food = {'bulgogi': 10, 'falafel': 4, 'ceviche': 7}
>>> food['ultimate'] = food['bulgogi'] + food['ceviche']
>>> food['ultimate']

______
17

>>> len(food)

______
4

>>> food['ultimate'] += food['falafel']
>>> food['ultimate']

______
21

>>> sorted(list(food.keys()))  # Alphabetically sorted list of food's keys

______
['bulgogi', 'ceviche', 'falafel', 'ultimate']

>>> food['bulgogi'] = food['falafel']
>>> len(food)

______
4

>>> 'gogi' in food

______
False

List Mutation

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

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

Dictionaries

Question 6: 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

Optional Questions

Question 7: Deep map

Write the function deep_map_mut that takes a Python list and mutates all of the elements (including elements of sublists) to be the result of calling the function given, fn, on each element. Note that the function does not return the mutated list! 

def deep_map_mut(fn, lst):
    """Deeply maps a function over a Python list, replacing each item
    in the original list object.

    Does NOT create new lists by either using literal notation
    ([1, 2, 3]), +, or slicing.

    Does NOT return the mutated list object.

    >>> l = [1, 2, [3, [4], 5], 6]
    >>> deep_map_mut(lambda x: x * x, l)
    >>> l
    [1, 4, [9, [16], 25], 36]
    """

    "*** YOUR CODE HERE ***"

    for i in range(len(lst)):
        if type(lst[i]) == list:
            deep_map_mut(fn, lst[i])
        else:
            lst[i] = fn(lst[i])

Use OK to test your code:

python3 ok -q deep_map_mut

Question 8: 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 9: 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