Lab 4: Lists

Due at 11:59pm on 02/18/2015.

Starter Files

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

Table of Contents

Lists

Question 1: What would Python print? 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[x[0]]

______
2

>>> x[x[x[0]]]

______
3

>>> x[3]

______
IndexError

>>> x[-1]

______
3

>>> x[-3]

______
1

Question 2: What would Python print? 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]

As you may have noticed, Python has a convenient notation for slicing to retrieve part of a list. Specifically, we can write [start:stop] to slice a list with two integers.

Using negative indices for start and end behaves in the same way as indexing into negative indices. In addition, slicing a list creates a new list, without modifying the original list.

Question 3: What would Python print? 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

For each of the following, use element selection to get the number 7 from the particular list in the doctest. Don't worry about making this work for all lists.

def get_seven_a(x):
    """
    >>> x = [1, 3, [5, 7], 9]
    >>> get_seven_a(x)
    7
    """

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

    return x[2][1]

def get_seven_b(x):
    """
    >>> x = [[7]]
    >>> get_seven_b(x)
    7
    """

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

    return x[0][0]

def get_seven_c(x):
    """
    >>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
    >>> get_seven_c(x)
    7
    """

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

    return x[1][1][1][1][1][1][0]

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

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

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

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

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

List Comprehensions

List comprehensions are a compact and powerful way of creating new lists out of sequences. Let's work with them directly:

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

is equivalent to

>>> lst = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         lst += [i**2]
>>> lst
[4, 16]

The general syntax for a list comprehension is

[<expression> for <element> in <sequence> if <conditional>]

The syntax is designed to read like English: "Compute the expression for each element in the sequence if the conditional is true."

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

Question 8: Perfect squares

Implement the function squares, which takes in a list of positive integers, and returns a new list which contains only elements of the original list that are perfect squares. Use a list comprehension.

from math import sqrt

def is_square(n):
    return float(sqrt(n)) == int(sqrt(n))

def squares(seq):
    """Returns a new list containing elements of the original list that are
    perfect squares.

    >>> seq = [49, 8, 2, 1, 102]
    >>> squares(seq)
    [49, 1]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """

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

    return [n for n in seq if is_square(n)]

Extra Questions

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

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

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

Question 10: Mergesort

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

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]

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

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]

Question 12: 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]

Question 13: Adding matrices

To practice, write a function that adds two matrices together using list comprehensions. The function should take in two 2D lists of the same dimensions. Try to implement this in one line!

def add_matrices(x, y):
    """
    >>> matrix1 = [[1, 3],
    ...            [2, 0]]
    >>> matrix2 = [[-3, 0],
    ...            [1, 2]]
    >>> add_matrices(matrix1, matrix2)
    [[-2, 3], [3, 2]]
    """

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

    return [[x[i][j] + y[i][j] for j in range(len(x[0]))]
                               for i in range(len(x))]