Exercise 1

Suppose I want to write a function called reverse_list(lst) that takes a list lst as input and mutates it so that it is backwards. For example,

>>> lst = [1, 2, 3]
>>> reverse_list(lst)
>>> print(lst)
[3, 2, 1]

My first attempt at implementing this is the following:

# Modifies the list so that the elements at index1 and index2 are swapped
def swap(lst, index1, index2):
    lst[index1] = lst[index2]
    lst[index2] = lst[index1]

# Reverses the order of the elements of the list lst
def reverse_list(lst):
    # Iterates over list and swaps the elements as follows:
    #   index 0 gets swapped with len(lst) - 1
    #   index 1 gets swapped with len(lst) - 2
    #   index 2 gets swapped with len(lst) - 3
    #   and so on...
    for i in range(len(lst)):
        swap(lst, i, len(lst)-1-i)

a. Save the above code in a file named reverse.py, read it to make sure you know the basic idea behind the algorithm, and import both functions into the REPL.

>>> from reverse import *

b. Try executing reverse_list on the following list to see if it works properly.

>>> test_list = [100,200,300,400,500]
>>> reverse_list(test_list)
>>> test_list

c. OK, so it is indeed broken. Try executing it on a couple more lists; then discuss with your partner and make a hypothesis on where the most likely place the bug exists.

d. We will use pudb3 to investigate our hypothesis. To start, add the following main function to your code and feel free to change the test_list to one that may be more appropriate for testing your hypothesis.

def main():
    test_list = [100,200,300,400,500]
    reverse_list(test_list)
    print(test_list)

if __name__ == "__main__":
    main()

e. Execute the code with pudb3 to start up the Python debugger.

$ pudb3 reverse.py

f. Before we start debugging, there are a couple useful preferences to change. If pudb3 initially opens up the options menu, make sure to make the following changes.

  • Make sure Show Line Numbers is checked
  • Under Variable Stringifier, make sure that repr is checked

If the preferences did not open initially, you can press Ctrl + P to open them.

g. To step through your code line by line, type the n key to execute the next line of code. Note that n will not enter into a function, but rather it executes the whole function at once. If you’d like to step into a function call, press the s key. (At the top of the debugger, there is a helpful reference that reminds you what the keys are in case you forget.)

h. Let’s try investigating using breakpoints. Navigate to line swap(lst, i, len(lst)-1-i) and press b to set a breakpoint. Now, to continue executing your program until a breakpoint is pressed, you can press the c key. Try pressing it and watch how the list is updated when the swap function is called.

i. Try stepping into the swap function and examine what it does. Does it successfully swap the two values? If not, discuss with your partner why the values are not being swapped properly.

j. Exit out of pudb3 by pressing q and fix the swap function so that it properly swaps values. Test it in the REPL to make sure that it is working properly.

k. After fixing the swap function, try testing the reverse_list function one more time. Does it work?

l. If the only bug you fixed was in the swap function, you’ll find that the reverse_list function still does not work. Discuss with your partner what you think is happening, and investigate your hypothesis using the debugger.

m. Fix the error in the reverse_list function and make sure it is working properly by running a few tests.

Exercise 2

We have seen it is possible to append elements to the end of a list, such as:

>>> lst = [100, 200, 300]
>>> lst.append(400)
>>> print(lst)
[100, 200, 300, 400]

It is also possible to remove element from a list. To do this, we can use the pop(index) method which removes the value at the given index. It also returns the value at that index. For example,

>>> lst = [100, 200, 300]
>>> val = lst.pop(0)
>>> print(val)
100
>>> print(lst)
[200, 300]

a. Try experimenting with the pop method in the REPL to make sure you understand what it is doing.

b. What happens when you call pop() with no index parameter? Try it out!

Now suppose I want to write a function called pop_strings(lst) that takes a list lst as a parameter and pops all the strings from the list, returning them as a list. For example,

>>> lst = [100, "abc", "def", 200, 300, "ghi"]
>>> strings = pop_strings(lst)
>>> print(strings)
['abc', 'def', 'ghi']
>>> print(lst)
[100, 200, 300]

As a first attempt, I write the following code:

def pop_strings(lst):
    strings = []
    for index in range(len(lst)):
        cur_item = lst[index]
        if type(cur_item) == str:
            strings.append(cur_item)
            lst.pop(index)
    return strings

c. Read the above code, discuss it with your partner, and make sure you both understand what the idea is.

d. Copy the function into a file pop_strings_test.py along with the following main function for testing:

def main():
    lst = [100, "abc", "def", 200, 300, "ghi"]
    strings = pop_strings(lst)
    print(strings)
    print(lst)

if __name__ == "__main__":
    main()

e. Run the code to see if it works by running

$ python3 pop_strings_test.py

f. Of course it fails… Carefully examine the error message and make a hypothesis with your partner about what is going wrong.

g. Test your hypothesis using the debugger. Step through the code line by line around the region where you think the problem is until you notice something strange happen.

h. After you identified the problem, discuss with your partner possible ways of fixing the problem. (Hint: using a while loop gives you a lot more flexibility in iterating over a loop. Below is the same function implemented as a while loop, but it still will crash.)

def pop_strings(lst):
    strings = []
    index = 0
    while index < len(lst):
        cur_item = lst[index]
        if type(cur_item) == str:
            strings.append(cur_item)
            lst.pop(index)
        index = index + 1
    return strings

i. Fix the code and make sure to test it out on a variety of lists to make sure it is working on a variety of cases. If you are having trouble or questioning its correctness, have the instructor or prefect double check your work.

Exercise 3

Below is a program with two functions designed to find the elements at even and odd indices within a list and return a copy of them in a new list. (Partitioning a list in this way can be quite useful.)

Here is what each function should do:

>>> lst = [100, 200, 300, 400]
>>> e = extract_even(lst)
>>> o = extract_odd(lst)
>>> print(lst)
[100, 200, 300, 400]
>>> print(e)
[100, 300]
>>> print(o)
[200, 400]

Note that the even elements are 100 and 300 because their indicies, 0 and 2, are even. Similarly, 200 and 400 are the odd elements since their indicies are 1 and 3.

Below are the actual implementations.

def extract_even(lst):
    evens = []
    for i in len(lst):
        if i % 2 == 0:
            evens.append(i)
    return evens

def extract_odd(lst):
    odds = []
    for i in len(lst):
        if i % 2 == 0:
            odds.append(i)
    return odds

def main():
    lst = [100, 200, 300, 400]
    print("lst:", lst)

    e = extract_even(lst)
    print("evens:", e)

    o = extract_odd(lst)
    print("odds:", o)

if __name__ == "__main__":
    main()

a. Be sure to read the above code and understand the general approach for extracting the even and odd indices.

b. Examine the error produced carefully, discuss what could be causing it with your parter, and fix it. (Think about the clues of the error message that are hinting at the problem.)

c. Try running it again and fix any other errors you find in the functions. Remember you can always use the debugger if needed, but sometimes the errors are simple enough that looking at the error message can give you insight into the issue.

d. Once the functions are working properly, were you annoyed that because the two functions are similar and the author duplicated the code that you had to fix many of the errors twice? A key mantra of computer science is don’t repeat yourself (DRY) since doing so usually duplicates bugs and is harder to maintain. To avoid this code duplication, create a third function extract_by_parity(lst, parity) that can extract the evens with parity = 0 and extract by odds if parity = 1. Then have extract_even and extract_odd call this helper function rather that duplicating the code.