Lab 4: Lists

Table of Contents

Submission

This lab is due at 11:59pm on 10/01/2014.

Please start at the beginning of the lab and work your way through, working and talking over Python's behavior in the conceptual questions with your classmates nearby. These questions are designed to help you experiment with the concepts on the Python interpreter. They are good tests for your understanding.

When you are done with lab, submit Questions 6, 7, 11, and 13 provided in the starter file lab04.py to receive credit for this lab. Questions 5, 8, and 12 are marked with an asterisk and considered extra practice. They can be found in the lab04_extra.py file. It is recommended that you complete these problems on your own time.

By the end of this lab, you should have submitted the lab04 assignment using the command submit lab04. You can check if we received your submission by running glookup -t. Click here to see more complete submission instructions.

Lists

What would Python print?

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

Question 1

>>> x = [1, 2, 3]
>>> x[0]
______
1
>>> x[3]
______
IndexError
>>> x[-1]
______
3
>>> x[-3]
______
1

Question 2

>>> 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]
______
[1, 3]
>>> x[::-1]
______
[4, 3, 2, 1]
>>> x[-1:0:-1]
______
[4, 3, 2]

Note: As you may have noticed, Python has a convenient notation for slicing, or breaking up, a list. Specifically, we can write [start:end:step] to slice a list with three integers. start denotes the index for where to begin the slice, end denotes the index to stop the slice, and step denotes how many indicies 0 for the starting index, the length for the ending index, and 1 for the step size. Using negative indicies for start and end behaves in the same way as indexing into negative indicies, and using a negative step means to move backwards through the list. It is also important to note that slicing a list creates a new list, without modifying the original list.

Question 3

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

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

Write a function reverse that takes a list and returns the reverse. Write both an iterative and a recursive version. You may use slicing notation, but don't use list[::-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
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

A list that contains one or more lists as elements is called a deep list. For example, [1, [2, 3], 4] is a deep list.

Write a function deep_len that takes a list and returns its deep length. See the doctests for the function's behavior.

Hint: you can check if something is a list by using the built-in type function. For example,

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True
def deep_len(lst):
    """Returns the deep length of the list.

    >>> deep_len([1, 2, 3])     # normal list
    3
    >>> x = [1, [2, 3], 4]      # deep list
    >>> deep_len(x)
    4
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> deep_len(x)
    6
    """
"*** YOUR CODE HERE ***"
if not lst: return 0 elif type(lst[0]) == list: return deep_len(lst[0]) + deep_len(lst[1:]) else: return 1 + deep_len(lst[1:])

Question 7

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

Question 8: *

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]

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.

In lecture, you learned about a few powerful higher-order functions that process sequences. Let's review them here:

Note: apply_to_all and keep_if will always return lists, no matter what kind of sequence we pass in.

We've provided the implementation for these functions in lab04.py.

Question 9: What would Python print?

Note: First run python3 -i lab04.py to load the provided functions before trying the following questions.

>>> apply_to_all(lambda x: x**2, [1, 2, 3, 4])
______
[1, 4, 9, 16]
>>> apply_to_all(lambda a: a, 'cs61a')
______
['c', 's', '6', '1', 'a']
>>> keep_if(lambda x: x % 2 == 0, [1, 2, 3, 4])
______
[2, 4]
>>> reduce(lambda a, b: a + b, [1, 2, 3, 4, 5], 0)
______
15
>>> reduce(lambda a, b: b + a, 'hello world!', '')
______
'!dlrow olleh'

Question 10

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

>>> apply_to_all(_______, [1, 3, -1, -4, 2])
[1, 1, -1, -1, 1]
>>> keep_if(______, [1, 7, 14, 21, 28, 35, 42])
[1, 14, 28, 42]
>>> reduce(_______, _______, '')
'olleh'
>>> reduce(______, apply_to_all(______, 'nnnnn'), __) + ' batman!'
'nanananana batman!'

List Comprehensions

Our functions apply_to_all and keep_if are implemented using list comprehensions, 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 11

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 doctest if you are still confused.

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 [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]

Question 12: *

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):
    """
    >>> add_matrices([[1, 3], [2, 0]], [[-3, 0], [1, 2]])
    [[-2, 3], [3, 2]]
    """
"*** YOUR CODE HERE ***"
return [[x[i][j] + y[i][j] for j in range(len(x[0]))] for i in range(len(x))]

Question 13

Now write a list comprehension that will create a deck of cards. Each element in the list will be a card, which is represented by a list containing the suit as a string and the value as an int.

def deck():
"*** YOUR CODE HERE ***"
return [[suit, value] for suit in ["spades", "clubs", "diamonds", "hearts"] for value in range(1, 14)]

Python also includes a powerful sorted function which returns a sorted version of a list. It can also take a key function that tells sorted how to actually sort the objects. For more information, look at Python's documentation for the sorted method. Note that sorted is stable, meaning if two values are equal according to the key function, their relative positions will stay the same after sorting. Now, use the sorted function to write a function that takes in a shuffled deck and returns a sorted deck. It should sort cards of the same suit together, and then sort each card in each suit in increasing value.

def sort_deck(deck):
"*** YOUR CODE HERE ***"
deck = sorted(deck, key=lambda card: card[1]) return sorted(deck, key=lambda card: card[0])