Lab 5 Solutions

Solution Files

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.


Lists

A list is a data structure that can store multiple elements. Each element can be any type, even a list itself. We write a list as a comma-separated list of expressions in square brackets:

>>> list_of_ints = [1, 2, 3, 4]
>>> list_of_bools = [True, True, False, False]
>>> nested_lists = [1, [2, 3], [4, [5]]]

Each element in the list has an index, with the index of the first element starting at 0. We say that lists are therefore "zero-indexed."

With list indexing, we can specify the index of the element we want to retrive. A negative index represents starting from the end of the list, so the negative index -i is equivalent to the positive index len(lst)-i.

>>> lst = [6, 5, 4, 3, 2, 1, 0]
>>> lst[0]
6
>>> lst[3]
3
>>> lst[-1] # Same as lst[6]
0

To create a copy of part or all of a list, we can use list slicing. The syntax to slice a list lst is: lst[<start index>:<end index>:<step size>].

This expression evaluates to a new list containing the elements of lst:

  • Starting at and including the element at <start index>.
  • Up to but not including the element at <end index>.
  • With <step size> as the difference between indices of elements to include.

If the start, end, or step size are not explicitly specified, Python has default values for them. A negative step size indicates that we are stepping backwards through a list when including elements.

>>> lst[:3]   # Start index defaults to 0
[6, 5, 4]
>>> lst[3:]   # End index defaults to len(lst)
[3, 2, 1, 0]
>>> lst[::-1]   # Make a reversed copy of the entire list
[0, 1, 2, 3, 4, 5, 6]
>>> lst[::2]  # Skip every other; step size defaults to 1 otherwise
[6, 4, 2, 0]


List Comprehensions

List comprehensions are a compact and powerful way of creating new lists out of sequences. The general syntax for a list comprehension is the following:

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

where the if <conditional> section is optional.

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

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

This list comprehension will:

  • Compute the expression i**2
  • For each element i in the sequence [1, 2, 3, 4]
  • Where i % 2 == 0 (i is an even number),

and then put the resulting values of the expressions into a new list.

In other words, this list comprehension will create a new list that contains the square of every even element of the original list [1, 2, 3, 4].

We can also rewrite a list comprehension as an equivalent for statement, such as for the example above:

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


Mutability

We say that an object is mutable if its state can change as code is executed. The process of changing an object's state is called mutation. Examples of mutable objects include lists and dictionaries. Examples of objects that are not mutable include tuples and functions.

Required Questions

What Would Python Do?

Q1: WWPD: List-Mutation

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

python3 ok -q list-mutation -u

Important: For all WWPD questions, type Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing is displayed.

>>> lst = [5, 6, 7, 8]
>>> lst.append(6)

______
None

>>> lst

______
[5, 6, 7, 8, 6]

>>> lst.insert(0, 9)
>>> lst

______
[9, 5, 6, 7, 8, 6]

>>> x = lst.pop(2)
>>> lst

______
[9, 5, 7, 8, 6]

>>> lst.remove(x)
>>> lst

______
[9, 5, 7, 8]

>>> a, b = lst, lst[:]
>>> a is lst

______
True

>>> b == lst

______
True

>>> b is lst

______
False

>>> lst = [1, 2, 3]
>>> lst.extend([4,5])
>>> lst

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

>>> lst.extend([lst.append(9), lst.append(10)])
>>> lst

______
[1, 2, 3, 4, 5, 9, 10, None, None]

Parsons Problems

To work on these problems, open the Parsons editor:

python3 parsons

Q2: Replace Elements

Complete the function replace_elements, a function which takes in source_list and dest_list and mutates the elements of dest_list to be the elements at the corresponding index in source_list.

dest_list always has a length greater than or equal to the length of source_list.

def replace_elements(source_list, dest_list):
    """
    Complete the function replace_elements, a function which takes in source_list
    and dest_list and mutates the elements of dest_list to be the elements at the
    corresponding index in source_list.

    dest_list always has a length greater than or equal to the length of
    source_list.

    >>> s1 = [1, 2, 3]
    >>> s2 = [5, 4]
    >>> replace_elements(s2, s1)
    >>> s1
    [5, 4, 3]
    >>> s3 = [0, 0, 0, 0, 0]
    >>> replace_elements(s1, s3)
    >>> s3
    [5, 4, 3, 0, 0]
    """

    for i in range(len(source_list)):
        dest_list[i] = source_list[i]

Code Writing Questions

Q3: Flatten

Write a function flatten that takes a list and "flattens" it. The list could be a deep list, meaning that there could be a multiple layers of nesting within the list.

For example, one use case of flatten could be the following:

>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]

Make sure your solution does not mutate the input list.

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 flatten(s):
    """Returns a flattened version of list s.

    >>> flatten([1, 2, 3])     # normal list
    [1, 2, 3]
    >>> x = [1, [2, 3], 4]     # deep list
    >>> flatten(x)
    [1, 2, 3, 4]
    >>> x # Ensure x is not mutated
    [1, [2, 3], 4]
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> flatten(x)
    [1, 1, 1, 1, 1, 1]
    >>> x
    [[1, [1, 1]], 1, [1, 1]]
    """

    if not s:
        return []
    elif type(s[0]) == list:
        return flatten(s[0]) + flatten(s[1:])
    else:
        return [s[0]] + flatten(s[1:])

Use Ok to test your code:

python3 ok -q flatten

Q4: Couple

Implement the function couple, which takes in two lists and returns a list that contains lists with i-th elements of two sequences coupled together. You can assume the lengths of two sequences are the same. Try using a list comprehension.

Hint: You may find the built in range function helpful.

def couple(s, t):
    """Return a list of two-element lists in which the i-th element is [s[i], t[i]].

    >>> a = [1, 2, 3]
    >>> b = [4, 5, 6]
    >>> couple(a, b)
    [[1, 4], [2, 5], [3, 6]]
    >>> c = ['c', 6]
    >>> d = ['s', '1']
    >>> couple(c, d)
    [['c', 's'], [6, '1']]
    """
    assert len(s) == len(t)

    return [[s[i], t[i]] for i in range(0, len(s))]

Use Ok to test your code:

python3 ok -q couple

Q5: Insert Items

Write a function which takes in a list lst, an argument entry, and another argument elem. This function will check through each item in lst to see if it is equal to entry. Upon finding an item equal to entry, the function should modify the list by placing elem into lst right after the item. At the end of the function, the modified list should be returned.

See the doctests for examples on how this function is utilized.

Important: Use list mutation to modify the original list. No new lists should be created or returned.

Note: If the values passed into entry and elem are equivalent, make sure you're not creating an infinitely long list while iterating through it. If you find that your code is taking more than a few seconds to run, the function may be in a loop of inserting new values.

def insert_items(lst, entry, elem):
    """Inserts elem into lst after each occurence of entry and then returns lst.

    >>> test_lst = [1, 5, 8, 5, 2, 3]
    >>> new_lst = insert_items(test_lst, 5, 7)
    >>> new_lst
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> double_lst = [1, 2, 1, 2, 3, 3]
    >>> double_lst = insert_items(double_lst, 3, 4)
    >>> double_lst
    [1, 2, 1, 2, 3, 4, 3, 4]
    >>> large_lst = [1, 4, 8]
    >>> large_lst2 = insert_items(large_lst, 4, 4)
    >>> large_lst2
    [1, 4, 4, 8]
    >>> large_lst3 = insert_items(large_lst2, 4, 6)
    >>> large_lst3
    [1, 4, 6, 4, 6, 8]
    >>> large_lst3 is large_lst
    True
    >>> # Ban creating new lists
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'insert_items',
    ...       ['List', 'ListComp', 'Slice'])
    True
    """

    index = 0
    while index < len(lst):
        if lst[index] == entry:
            lst.insert(index + 1, elem)
            if entry == elem:
                index += 1
        index += 1
    return lst

Use Ok to test your code:

python3 ok -q insert_items

Video Walkthrough:

YouTube link

Submit

Make sure to submit this assignment by running:

python3 ok --submit