Lab 5: Lists and Dictionaries

Due at 11:59pm on 07/07/2015.

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 5, 6, 7, 10, and 11 in lab05.py and submit through OK.
  • Questions 1, 2, 3, 4, 8, and 9 are designed to help introduce concepts and test your understanding.
  • Questions 12, 13, 14, 15, 16, and 17 extra practice. They can be found in the lab05_extra.py file. It is recommended that you complete these problems on your own time.

Lists

Question 1: List indexing

Predict what Python will display when you type the following into the interpreter. Then try it to check your answers.

>>> x = [1, 2, 3]
>>> x[0]

______
1

>>> x[2]

______
3

>>> x[3]

______
IndexError

>>> x[-1]

______
3

>>> x[-3]

______
1

Question 2: List slicing

Predict what Python will display when you type the following into the interpreter. Then try it to check your answers.

>>> x = [1, 2, 3, 4]
>>> x[1:3]

______
[2, 3]

>>> x[:2]

______
[1, 2]

>>> x[1:]

______
[2, 3, 4]

>>> x[-2:3]

______
[3]

>>> x[-2:4]

______
[3, 4]

>>> x[0:4:2]

______
[1, 3]

>>> x[::-1]

______
[4, 3, 2, 1]

Python can retrieve part of a list by slicing.

We can write [start:end:step] to slice a list.

  • start: the index for the beginning of the slice
  • end: the index for the end of the slice
  • step: how big your step size is

Using negative indices for start and end behaves the same way as indexing into negative indices. Negative step means to move backwards.

Slicing a list creates a new list, without modifying the original list.

Question 3: List operations

Predict what Python will display when you type the following into the interpreter. Then try it to check your answers.

>>> y = [1]
>>> len(y)

______
1

>>> 1 in y

______
True

>>> y + [2, 3]

______
[1, 2, 3]

>>> [0] + y

______
[0, 1]

>>> y * 3

______
[1, 1, 1]

>>> z = [[1, 2], [3, 4, 5]]
>>> len(z)

______
2

Question 4: Fill in the blanks

Fill in the blanks for the following lines so that each expression evaluates to the expected output: 

>>> x = [1, 3, [5, 7], 9]
>>> _______________
7
>>> x = [[7]]
>>> _______________
7
>>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
>>> _______________
7
  • x[2][1]
  • x[0][0]
  • x[1][1][1][1][1][1][0]

Question 5: Reverse (iteratively)

Write a function reverse_iter that takes a list and returns a new list that is the reverse of the original. Use iteration! You may also use slicing notation. Do not use lst[::-1]!

def reverse_iter(lst):
    """Returns the reverse of the given list.

    >>> reverse_iter([1, 2, 3, 4])
    [4, 3, 2, 1]
    """

    "*** YOUR CODE HERE ***"

    new, i = [], 0
    while i < len(lst):
        new = [lst[i]] + new
        i += 1
    return new

Use OK to test your code:

python3 ok -q reverse_iter

Question 6: Reverse (recursively)

Write a function reverse_recursive that takes a list and returns a new list that is the reverse of the original. Use recursion! You may also use slicing notation. Do not use lst[::-1]!

def reverse_recursive(lst):
    """Returns the reverse of the given list.

    >>> reverse_recursive([1, 2, 3, 4])
    [4, 3, 2, 1]
    """

    "*** YOUR CODE HERE ***"

    if not lst:
        return []
    return reverse_recursive(lst[1:]) + [lst[0]]

Use OK to test your code:

python3 ok -q reverse_recursive

Sequences

Sequences are ordered collections of values that support element-selection and have length. The most common sequence you've worked with are lists, but many other Python types are sequences as well, including strings.

Here are a few powerful higher-order functions that process sequences:

  • map(fn, seq): applies a function fn onto every element in the given sequence seq.
  • filter(cond, seq): keeps elements in the sequence seq only if those elements satisfy the condition function cond (that is, for an element x, keep it only if cond(x) is True).
  • reduce(combiner, seq, initial): combines all elements in the sequence seq with the combiner function (which must take two arguments), starting from the initial value.

Note: map and filter are built-in to python3 but reduce is in the functools package. You must import reduce from functools like this:

>>> from functools import reduce
>>> reduce(lambda x, y: x + y, [1, 2, 3])
6

Note: map and filter do not return lists. Instead, map returns a map object and filter returns a filter object. We can convert these objects to lists by using the list constructor:

>>> map(lambda x: x * x, [1, 2, 3, 4])
<map object at ...>
>>> list(map(lambda x: x * x, [1, 2, 3, 4]))
[1, 4, 9, 16]

Question 7: Map, Filter, Reduce

As an exercise, implement three functions map, filter, and reduce to behave like their built-in counterparts. For map and filter, you can return the results as Python lists.

def map(fn, seq):
    """Applies fn onto each element in seq and returns a list.

    >>> map(lambda x: x*x, [1, 2, 3])
    [1, 4, 9]
    """

    "*** YOUR CODE HERE ***"

    result = []
    for elem in seq:
        result += [fn(elem)]
    return result

def filter(pred, seq):
    """Keeps elements in seq only if they satisfy pred.

    >>> filter(lambda x: x % 2 == 0, [1, 2, 3, 4])
    [2, 4]
    """

    "*** YOUR CODE HERE ***"

    result = []
    for elem in seq:
        if pred(elem):
            result += [elem]
    return result

def reduce(combiner, seq):
    """Combines elements in seq using combiner.

    >>> reduce(lambda x, y: x + y, [1, 2, 3, 4])
    10
    >>> reduce(lambda x, y: x * y, [1, 2, 3, 4])
    24
    >>> reduce(lambda x, y: x * y, [4])
    4
    """

    "*** YOUR CODE HERE ***"

    total = seq[0]
    for elem in seq[1:]:
        total = combiner(total, elem)
    return total

Use OK to test your code:

python3 ok -q map
python3 ok -q filter
python3 ok -q reduce

List Comprehension

A list comprehension is Python syntax for quickly creating lists.

  • For loop: sequence to iterate over
  • Map expression: what to do to each element in sequence
  • Filter expression: which elements to keep (optional)

For example:

>>> seq = [1, 2, 3, 4]
>>> [x * x for x in seq if x % 2 == 0]
[4, 16]

Question 8: What would Python print?

What would Python print? Try to figure it out before you type it into the interpreter!

>>> [x*x for x in range(5)]

______
[0, 1, 4, 9, 16]

>>> [n for n in range(10) if n % 2 == 0]

______
[0, 2, 4, 6, 8]

>>> ones = [1 for i in ["hi", "bye", "you"]]
>>> ones + [str(i) for i in [6, 3, 8, 4]]

______
[1, 1, 1, '6', '3', '8', '4']

>>> [i+5 for i in [n for n in range(1,4)]]

______
[6, 7, 8]

Dictionaries

Dictionaries are unordered sets of key-value pairs. To create a dictionary, use the following syntax:

>>> singers = { 'Iggy Azalea': 'Fancy', 'Beyonce': 'Flawless', 'Adam Levine': 'Maps'}

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. You can retrieve values from your dictionary by "indexing" using the key:

>>> singers['Beyonce']
'Flawless'
>>> singers['Iggy Azalea']
'Fancy'

You can update an entry for an existing key in the dictionary using the following syntax. Be careful adding a new key follows identical syntax!

>>> singers['Beyonce'] = 'Survivor'
>>> singers['Beyonce']
'Survivor'
>>> singers['Nicki Minaj'] = 'Anaconda' # new entry!
>>> singers['Nicki Minaj']
'Anaconda'

You can also check for membership of keys!

>>> 'Adam Levine' in singers
True

Question 9: What Would Python Print?

What would Python print? Try to figure it out before you type it into the interpreter!

>>> pokemon = {'pikachu': 25, 'dragonair': 148, 'mew': 151}
>>> pokemon['pikachu']

______
25

>>> pokemon['jolteon'] = 135
>>> pokemon

______
{'jolteon': 135, 'pikachu': 25, 'dragonair': 148, 'mew': 151}

>>> pokemon['ditto'] = 25
>>> pokemon

______
{'jolteon': 135, 'pikachu': 25, 'dragonair': 148,
’ditto’: 25, ’mew’: 151}

>>> ’mewtwo’ in pokemon

______
False

>>> len(pokemon)

______
5

>>> pokemon[’ditto’] = pokemon[’jolteon’]
>>> pokemon

______
{'mew': 151, 'ditto': 135, 'jolteon': 135, 'pikachu': 25, 'dragonair': 148}

Shakespeare and Dictionaries

We will use dictionaries to approximate the entire works of Shakespeare! We're going to use a bigram language model. Here's the idea: We start with some word — we'll use "The" as an example. Then we look through all of the texts of Shakespeare and for every instance of "The" we record the word that follows "The" and add it to a list, known as the successors of "The". Now suppose we've done this for every word Shakespeare has used, ever.

Let's go back to "The". Now, we randomly choose a word from this list, say "cat". Then we look up the successors of "cat" and randomly choose a word from that list, and we continue this process. This eventually will terminate in a period (".") and we will have generated a Shakespearean sentence!

The object that we'll be looking things up in is called a "successor table", although really it's just a dictionary. The keys in this dictionary are words, and the values are lists of successors to those words.

Question 10: Successor Tables

Here's an incomplete definition of the build_successors_table function. The input is a list of words (corresponding to a Shakespearean text), and the output is a successors table. (By default, the first word is a successor to "."). See the example below.

Note: there are two places where you need to write code, denoted by the two "*** YOUR CODE HERE ***"

def build_successors_table(tokens):
    """Return a dictionary: keys are words; values are lists of
    successors.

    >>> text = ['We', 'came', 'to', 'investigate', ',', 'catch', 'bad', 'guys', 'and', 'to', 'eat', 'pie', '.']
    >>> table = build_successors_table(text)
    >>> sorted(table)
    [',', '.', 'We', 'and', 'bad', 'came', 'catch', 'eat', 'guys', 'investigate', 'pie', 'to']
    >>> table['to']
    ['investigate', 'eat']
    >>> table['pie']
    ['.']
    >>> table['.']
    ['We']
    """
    table = {}
    prev = '.'
    for word in tokens:
        if prev not in table:

            "*** YOUR CODE HERE ***"

            table[prev] = []
        "*** YOUR CODE HERE ***"

        table[prev] += [word]
        prev = word
    return table

Use OK to test your code:

python3 ok -q build_successors_table

Question 11: Construct the Sentence

Let's generate some sentences! Suppose we're given a starting word. We can look up this word in our table to find its list of successors, and then randomly select a word from this list to be the next word in the sentence. Then we just repeat until we reach some ending punctuation.

Hint: to randomly select from a list, first make sure you import the Python random library with import random and then use the expression random.choice(my_list))

This might not be a bad time to play around with adding strings together as well. Let's fill in the construct_sent function!

def construct_sent(word, table):
    """Prints a random sentence starting with word, sampling from
    table.
    """
    import random
    result = ' '
    while word not in ['.', '!', '?']:

        "*** YOUR CODE HERE ***"

        result += word + ' '
        word = random.choice(table[word])
    return result + word

Use OK to test your code:

python3 ok -q construct_sent

Putting it all together

Great! Now all that's left is to run our functions with some actual code. The following snippet included in the skeleton code will return a list containing the words in all of the works of Shakespeare.

Warning: do NOT try to print the return result of this function.

def shakespeare_tokens(path='shakespeare.txt', url='http://composingprograms.com/shakespeare.txt'):
    """Return the words of Shakespeare's plays as a list."""
    import os
    from urllib.request import urlopen
    if os.path.exists(path):
        return open('shakespeare.txt', encoding='ascii').read().split()
    else:
        shakespeare = urlopen(url)
        return shakespeare.read().decode(encoding='ascii').split()

Next, we probably want an easy way to refer to our list of tokens and our successors table. Let's make the following assignments (Note: the following lines are commented in the provided file. Uncomment them before procceding)

tokens = shakespeare_tokens()
table = build_successors_table(tokens)

Finally, let's define an easy to call utility function:

>>> def sent():
...     return construct_sent('The', table)
>>> sent()
" The plebeians have done us must be news-cramm'd "

>>> sent()
" The ravish'd thee , with the mercy of beauty "

>>> sent()
" The bird of Tunis , or two white and plucker down with better ; that's God's sake "

Notice that all the sentences start with the word "The". With a few modications, we can make our sentences start with a random word. The following random_sent function (defined in your starter file) will do the trick:

def random_sent():
    import random
    return construct_sent(random.choice(table['.']), table)

Go ahead and load your file into Python (be sure to use the -i flag). You can now call the random_sent function to generate random Shakespearean sentences!

>>> random_sent()
' Long live by thy name , then , Dost thou more angel , good Master Deep-vow , And tak'st more ado but following her , my sight Of speaking false !'

>>> random_sent()
' Yes , why blame him , as is as I shall find a case , That plays at the public weal or the ghost .'

Extra Questions

The following questions are for extra practice — they can be found in the the lab05_extra.py file. It is recommended that you complete these problems on your own time.

Question 12: Merge

Write a function merge that takes 2 sorted lists lst1 and lst2, and returns a new list that contains all the elements in the two lists in sorted order.

def merge(lst1, lst2):
    """Merges two sorted lists.

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """

    "*** YOUR CODE HERE ***"

    # recursive
    if not lst1 or not lst2:
        return lst1 + lst2
    elif lst1[0] < lst2[0]:
        return [lst1[0]] + merge(lst1[1:], lst2)
    else:
        return [lst2[0]] + merge(lst1, lst2[1:])

# Iterative solution 
def merge_iter(lst1, lst2):
    """Merges two sorted lists.

    >>> merge_iter([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge_iter([], [2, 4, 6])
    [2, 4, 6]
    >>> merge_iter([1, 2, 3], [])
    [1, 2, 3]
    >>> merge_iter([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    new = []
    while lst1 and lst2:
        if lst1[0] < lst2[0]:
            new += [lst1[0]]
            lst1 = lst1[1:]
        else:
            new += [lst2[0]]
            lst2 = lst2[1:]
    if lst1:
        return new + lst1
    else:
        return new + lst2

Use OK to test your code:

python3 ok -q merge

Question 13: Mergesort

Mergesort is a type of sorting algorithm. It follows a naturally recursive procedure:

  • Break the input list into equally-sized halves
  • Recursively sort both halves
  • Merge the sorted halves.

Using your merge function from the previous question, implement mergesort.

Challenge: Implement mergesort itself iteratively, without using recursion.

def mergesort(seq):
    """Mergesort algorithm.

    >>> mergesort([4, 2, 5, 2, 1])
    [1, 2, 2, 4, 5]
    >>> mergesort([])     # sorting an empty list
    []
    >>> mergesort([1])   # sorting a one-element list
    [1]
    """

    "*** YOUR CODE HERE ***"

    # recursive solution
    if len(seq) < 2:
        return seq
    mid = len(seq) // 2
    return merge(mergesort(seq[:mid]), mergesort(seq[mid:]))

# Iterative solution
def mergesort_iter(seq):
    """Mergesort algorithm.

    >>> mergesort_iter([4, 2, 5, 2, 1])
    [1, 2, 2, 4, 5]
    >>> mergesort_iter([])     # sorting an empty list
    []
    >>> mergesort_iter([1])   # sorting a one-element list
    [1]
    """
    if not seq:
        return []
    queue = [[elem] for elem in seq]
    while len(queue) > 1:
        first, second = queue[0], queue[1]
        queue = queue[2:] + [merge(first, second)]
    return queue[0]

Use OK to test your code:

python3 ok -q mergesort

Question 14: Coordinates

Implement a function coords, which takes a function, a sequence, and an upper and lower bound on output of the function. coords then returns a list of x, y coordinate pairs (lists) such that:

  • Each pair contains [x, fn(x)]
  • The x coordinates are the elements in the sequence
  • Only pairs whose y coordinate is within the upper and lower bounds (inclusive)

See the doctests for examples.

One other thing: your answer can only be one line long. You should make use of list comprehensions!

def coords(fn, seq, lower, upper):
    """
    >>> seq = [-4, -2, 0, 1, 3]
    >>> fn = lambda x: x**2
    >>> coords(fn, seq, 1, 9)
    [[-2, 4], [1, 1], [3, 9]]
    """ 

    "*** YOUR CODE HERE ***"
    return ______

    return [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]

Use OK to test your code:

python3 ok -q coords

Question 15: Deck of cards

Write a list comprehension that will create a deck of cards, given a list of suits and a list of numbers. Each element in the list will be a card, which is represented by a 2-element list of the form [suit, number].

def deck(suits, numbers):
    """Creates a deck of cards (a list of 2-element lists) with the given
    suits and numbers. Each element in the returned list should be of the form
    [suit, number].

    >>> deck(['S', 'C'], [1, 2, 3])
    [['S', 1], ['S', 2], ['S', 3], ['C', 1], ['C', 2], ['C', 3]]
    >>> deck(['S', 'C'], [3, 2, 1])
    [['S', 3], ['S', 2], ['S', 1], ['C', 3], ['C', 2], ['C', 1]]
    >>> deck([], [3, 2, 1])
    []
    >>> deck(['S', 'C'], [])
    []
    """

    "*** YOUR CODE HERE ***"
    return ______

    return [[suit, number] for suit in suits
                           for number in numbers]

Use OK to test your code:

python3 ok -q deck

Question 16: 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()

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

Question 17: Replace All

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

def replace_all(d, x, y):
    """
    >>> d = {'foo': 2, 'bar': 3, 'garply': 3, 'xyzzy': 99}
    >>> replace_all(d, 3, 'poof')

    >>> d == {'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