Lab 5: Sequences

  • Due: Friday 10/02 @ 11:59pm
  • Points: 1
  • Download: lab05.zip

Attendance

You need to submit the lab problems in addition to attending to get credit for lab. Students in mega lab only need to submit the lab problems. Preceptor interviews are highly recommended but not required for lab submissions.

If you are in regular lab, your TA will come around during lab to check you in. If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your lab): attendance form.

Required Questions

Review

Lists

A list is a data structure that can hold an ordered collection of items. These items, known as elements, can be of any data type, including numbers, strings, or even other lists. A comma-separated list of expressions in square brackets creates a list:

>>> list_of_values = [2, 1, 3, True, 3]
>>> nested_list = [2, [1, 3], [True, [3]]]

Each position in a list has an index, with the left-most element indexed 0.

>>> list_of_values[0]
2
>>> nested_list[1]
[1, 3]

A negative index counts from the end, with the right-most element indexed -1.

>>> nested_list[-1]
[True, [3]]

Adding lists creates a longer list containing the elements of the added lists.

>>> [1, 2] + [3] + [4, 5]
[1, 2, 3, 4, 5]
List Comprehensions

A list comprehension describes the elements in a list and evaluates to a new list containing those elements.

There are two forms:

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

Here's an example that starts with [1, 2, 3, 4], picks out the even elements 2 and 4 using if i % 2 == 0, then squares each of these using i*i. The purpose of for i is to give a name to each element in [1, 2, 3, 4].

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

This list comprehension evaluates to a list of:

  • The value of i*i
  • For each element i in the sequence [1, 2, 3, 4]
  • For which i % 2 == 0

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:

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

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 = [6, 5, 4, 3, 2, 1, 0]
    >>> lst[:3]     # Start index defaults to 0
    [6, 5, 4]
    >>> lst[3:]     # End index defaults to len(lst)
    [3, 2, 1, 0]
    >>> lst[:]      # Creates a copy of the list
    [6, 5, 4, 3, 2, 1, 0]
    >>> lst[:] == lst
    True
    >>> lst[:] is lst
    False
    >>> 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]

Slicing never causes an IndexError, even when the indices are out of range or the list is empty. This is different from indexing with a single number, which does error. This difference is because a slice always evaluates to a list, while indexing evaluates to an element of a list, where if no element exists at that position, there is no valid value to return. This is why Python raises an error for invalid indexing, while slicing just returns an empty list.

Again, if a slice has nothing to include, the result is an empty list. Assume for the following doctests, lst carries through from the above doctests.

    >>> lst[10:]        # Start index is past the end of the list
    []
    >>> empty = []
    >>> # indexing an empty list is an error
    >>> empty[0]        # You'll get the following error or some similar variation
    Traceback (most recent call last):
      ...
    IndexError: list index out of range
    >>> empty[:]        # Slicing an empty list is not
    []
    >>> empty[1:]
    []
    >>> empty[:3]
    []
    >>> empty[::-1]
    []
    >>> empty[:] is empty   # Still creates a new list
    False
For Statements

A for statement executes code for each element of a sequence, such as a list or range. Each time the code is executed, the name right after for is bound to a different element of the sequence.

for <name> in <expression>:
    <suite>

First, <expression> is evaluated. It must evaluate to a sequence. Then, for each element in the sequence in order,

  1. <name> is bound to the element.
  2. <suite> is executed.

Here is an example:

for x in [-1, 4, 2, 0, 5]:
    print("Current elem:", x)

This would display the following:

Current elem: -1
Current elem: 4
Current elem: 2
Current elem: 0
Current elem: 5
Ranges

A range is a data structure that holds integer sequences. A range can be created by:

  • range(stop) contains 0, 1, ..., stop - 1
  • range(start, stop) contains start, start + 1, ..., stop - 1

Notice how the range function doesn't include the stop value; it generates numbers up to, but not including, the stop value.

For example:

>>> for i in range(3):
...     print(i)
...
0
1
2

While ranges and lists are both sequences, a range object is different from a list. A range can be converted to a list by calling list():

>>> range(3, 6)
range(3, 6)
>>> list(range(3, 6))  # list() converts the range object to a list
[3, 4, 5]
>>> list(range(5))
[0, 1, 2, 3, 4]
>>> list(range(1, 6))
[1, 2, 3, 4, 5]

Lists

Q1: WWPD: Lists & Ranges

Predict what Python will display when the following lines are entered into an interactive session, then unlock the test to check your answers:

python3 -m pytest -k lists_wwpd --unlock
Unlocking Examples 

>>> s = [7//3, 5, [4, 0, 1], 2]
>>> s[0]
______
>>> s[2]
______
>>> s[-1]
______
>>> len(s)
______
>>> 4 in s
______
>>> 4 in s[2]
______
>>> s[2] + [3 + 2]
______
>>> 5 in s[2]
______
>>> s[2] * 2
______
>>> list(range(3, 6))
______
>>> range(3, 6)
______
>>> r = range(3, 6)
>>> [r[0], r[2]]
______
>>> range(4)[-1]
______

Q2: Print If

Implement print_if, which takes a list of integers s and a one-argument function f. It prints each element x of s for which f(x) returns a true value.

def print_if(s, f):
    """Print each element of s for which f returns a true value.

    >>> print_if([3, 4, 5, 6], lambda n: n > 4)
    5
    6
    >>> result = print_if([3, 4, 5, 6], lambda n: n % 2 == 0)
    4
    6
    >>> print(result)  # print_if should return None
    None
    """
    for x in s:
        "*** YOUR CODE HERE ***"

python3 -m pytest -k print_if

Q3: Close

Implement close, which takes a list of integers s and a non-negative integer k. It returns how many of the elements of s are within k of their index. That is, the absolute value of the difference between the element and its index is less than or equal to k.

Remember that a list is "zero-indexed"; the index of the first element is 0.

def close(s, k):
    """Return how many elements of s are within k of their index.

    >>> t = [6, 2, 4, 3, 5]
    >>> close(t, 0)  # Only 3 is equal to its index
    1
    >>> close(t, 1)  # 2, 3, and 5 are within 1 of their index
    3
    >>> close(t, 2)  # 2, 3, 4, and 5 are all within 2 of their index
    4
    >>> close(list(range(10)), 0)
    10
    """
    assert k >= 0
    count = 0
    for i in range(len(s)):  # Use a range to loop over indices
        "*** YOUR CODE HERE ***"
    return count

python3 -m pytest -k close

List Comprehensions

Q4: WWPD: List Comprehensions

Predict what Python will display when the following lines are entered into an interactive session, then unlock the test to check your answers:

python3 -m pytest -k list_comprehensions_wwpd --unlock
Unlocking Examples 

>>> [2 * x for x in range(4)]
______
>>> [y for y in [6, 1, 6, 1] if y > 2]
______
>>> [[1] + s for s in [[4], [5, 6]]]
______
>>> [z + 1 for z in range(10) if z % 3 == 0]
______

Q5: Squares Only

Implement the function squares, which takes in a list of positive integers. It returns a list that contains the square roots of the elements of the original list that are perfect squares. Use a list comprehension.

To find if x is a perfect square, you can check if sqrt(x) equals round(sqrt(x)).

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

    >>> seq = [8, 49, 8, 9, 2, 1, 100, 102]
    >>> squares(seq)
    [7, 3, 1, 10]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    return [___ for n in s if ___]

python3 -m pytest -k squares

Recursion

Q6: Double Eights

Write a recursive function that takes in a positive integer n and determines if its digits contain two adjacent 8s (that is, two 8s right next to each other). You implemented this function with iteration in Lab 2; now implement it with recursion.

Hint: Start by coming up with a recursive plan: the digits of a number have double eights if either ____ (think of something that is straightforward to check) or double eights appear in the rest of the digits.

Important: Use recursion; the tests will fail if you use any loops (for, while), the in operator, or the str function.

def double_eights(n):
    """Returns whether or not n has two digits in row that
    are the number 8.

    >>> double_eights(1288)
    True
    >>> double_eights(880)
    True
    >>> double_eights(538835)
    True
    >>> double_eights(284682)
    False
    >>> double_eights(588138)
    True
    >>> double_eights(78)
    False
    >>> double_eights(1077)
    False
    """
    "*** YOUR CODE HERE ***"

python3 -m pytest -k double_eights

Submit Assignment

Submit this assignment by running Provenance: Prepare Submission Bundle from the VS Code command palette and uploading the resulting zip to Gradescope. The zip already contains the files you've edited. Lab 00 has detailed instructions.

Your responses to WWPD questions are not submitted, and they do not need to be. Lab credit is based on the code writing questions.

Optional Questions

These questions are optional. If you don't complete them, you will still receive credit for this assignment. They are great practice, so do them anyway!

Q7: Flatten

Definition. A nested list of integers is a list of items that are either integers or nested lists of integers.

Write a function flatten that takes in a nested list of integers s and returns a list of the integers that appear in s.

(If you know about list mutation operations already, don't use them to change the input. We'll cover those later.)

Hint: you can check if something is a list two ways:

(1) by using the built-in type function.

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True

(2) by using the built-in isinstance function.

>>> isinstance(3, list)
False
>>> isinstance([1, 2, 3], list)
True

def flatten(s):
    """Returns a flattened version of list s, which contains lists and integers.

    >>> flatten([1, 2, 3])
    [1, 2, 3]
    >>> deep = [1, [[2], 3], 4, [[[[5], 6]], 7]]
    >>> flatten(deep)
    [1, 2, 3, 4, 5, 6, 7]
    >>> flatten(deep[1])
    [2, 3]
    >>> deep                                # input list should be unchanged
    [1, [[2], 3], 4, [[[[5], 6]], 7]]
    """
    "*** YOUR CODE HERE ***"

python3 -m pytest -k flatten

Q8: Ten-Pairs

Write a function that takes a positive integer n and returns the number of ten-pairs it contains. A ten-pair is a pair of digits within n that sums to 10.

The number 7,823,952 has 3 ten-pairs. The first and fourth digits sum to 7+3=10, the second and third digits sum to 8+2=10, and the second and last digit sum to 8+2=10.

Important notes:

  • A digit can be part of more than one ten-pair.
  • One 5 does not make a ten-pair with itself.

Recommended: Complete and use the helper function count_digit to calculate how many times a digit appears in n.

Important: Use recursion; the tests will fail if you use any loops (for, while).

def ten_pairs(n):
    """Return the number of ten-pairs within positive integer n.

    >>> ten_pairs(7823952) # 7+3, 8+2, and 8+2
    3
    >>> ten_pairs(55055)
    6
    >>> ten_pairs(9641469) # 9+1, 6+4, 6+4, 4+6, 1+9, 4+6
    6
    """
    "*** YOUR CODE HERE ***"


def count_digit(n, digit):
    """Return how many times digit appears in n.

    >>> count_digit(55055, 5) # digit 5 appears 4 times in 55055
    4
    """
    "*** YOUR CODE HERE ***"

python3 -m pytest -k count_digit
python3 -m pytest -k ten_pairs

Back to Top

Accessibility Nondiscrimination

Copyright ©2026, Regents of the University of California and respective authors.

This site is built following the Berkeley Class Site template, which is generously based on the Just the Class, and Just the Docs templates.

View all course offerings