CS61A Lab 5

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)
? Nothing
-- OK! --

>>> lst
? [5, 6, 7, 8, 6]
-- OK! --

>>> lst.insert(0, 9)
>>> lst
? [9, 5, 6, 7, 8, 6]
-- OK! --

>>> x = lst.pop(2)
>>> lst
? [9, 5, 7, 8, 6]
-- OK! --

>>> lst.remove(x)
>>> lst
? [9, 5, 7, 8]
-- OK! --

>>> a, b = lst, lst[:]
>>> a is lst
? False
-- Not quite. Try again! --

? True
-- OK! --

>>> b == lst
? True
-- OK! --

>>> b is lst
? False
-- OK! --

>>> lst = [1, 2, 3]
>>> lst.extend([4,5])
>>> lst
? [1, 2, 3, 4, 5]
-- OK! --

>>> lst.extend([lst.append(9), lst.append(10)])
>>> lst
? [1, 2, 3, 4, 5, 9, 10, None, None]
-- OK! --

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]
    """
    "*** YOUR CODE HERE ***"
    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]]
    """
    "*** YOUR CODE HERE ***"
    res = []
    for item in s:
        if type(item) == list:
            res.extend(flatten(item))
        else:
            res.append(item)
    return res

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)
    "*** YOUR CODE HERE ***"
    def make_pair(a, b):
        return [a, b]
    
    res = []
    for index in range(len(s)):
        pair = make_pair(s[index], t[index])
        res.append(pair)
    return res

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
    """
    "*** YOUR CODE HERE ***"
    idx = 0
    while idx < len(lst):
        if lst[idx] == entry:
            lst.insert(idx + 1, elem)
            idx += 2
        else:
            idx += 1
    return lst

Use Ok to test your code:

python3 ok -q insert_items