Sequences, Containers, Data Abstraction

Sep 27 2025 2 weeks ago

Sequences, Containers, Data Abstraction

Hi, I’m Ju Ho Kim and thank you very much for taking your time to visit my website!

In Week5, we learned about Sequences, Containers, and Data Abstraction.

This post is study notes about what I learned this week to make it useful for reviewing.

1. Sequences

List Indexing

x = [3, 1, [4, 1, [5, 2], 6, 5], 3, 5]

An expression to get the 2: x[2][2][1]

One thing that’s useful with list is to get a single element out of the list.

`for` loops

It’s also useful to loop over all of the elements in a list.

`range`

A range is a sequence of consecutive integers.

>>> list(range(-2, 2))  # List constructor
[-2, -1, 0, 1]
>>> list(range(4))      # Range with a 0 starting value
[0, 1, 2, 3]

The range just keeps track of what the starting and ending values are.

But the reason that we use range is that it’s a convenient way to get a bunch of integers in a row and it’s also a more efficient way of storing those than to actually create the list.

List Comprehensions

>>> digits = [1, 8, 0, 8]

>>> [100 * d for d in digits]
[100, 800, 0, 800]

>>> [100 * d for d in digits if d < 5]
[100, 0]

>>> numbers = range(10)
>>> even = [num for num in numbers if num % 2 == 0]
[0, 2, 4, 6, 8]

Two snippets below work the same way but use different syntax:

Using a for loop:

output = []         # create an empty list
for item in a:      # iterate through each item
    if condition:   # check a condition
        output.append(item * 2) # then append if `True`

Using a list comprehensions:

[item * 2 for item in a if condition]

Example 1: Evens

def evens(n: int) -> list[int]:
    """Return a list of the first n even numbers

    >>> evens(0)
    []
    >>> evens(3)
    [0, 2, 4]
    """
    return __________________

    return [2 * i for i in range(n)]

Or we can also come up with an another way

    return [i for i in range(n * 2) if i % 2 == 0]

Example 2: Two Lists

"""
Given these two related lists of the same length:
`xs = list(range(-10, 11))`,
`ys = [x*x - 2*x + 1 for x in xs]`

Write a list comprehension that evaluates to:
A list of all the x values (from xs) for which the corresponding y (from ys) is below 10.
"""
____________________________________________

[xs[i] for i in range(len(xs)) if ys[i] < 10]

This confused me during the class. The thing is, we always need to remember what we’re even trying to do.

We want a list of all the x values for which the corresponding y is below ten. That’s why it begins with [xs[i]].

for i in range(len(xs)): this iterates through all the indices of xs.

And we want it if the thing in ys at index i is less than ten. So, it’s followed by if ys[i] < 10.

>>> xs = list(range(-10, 11))
>>> ys = [x*x - 2*x + 1 for x in xs]
>>> [xs[i] for i in range(len(xs)) if ys[i] < 10]
[-2, -1, 0, 1, 2, 3, 4]

As shown above, these are the two ways that we’re using to pull the elements out when we’re writing list comprehensions:

we’re going to walk through all of the elements in a list with something like for x in xs or
we’re going to walk over all of the possible indices like for i in range(len(xs))

Example 3: Promoted

"""
Implement `promoted`, which takes a sequence `s` and a one-argument function `f`. It returns a
list with the same elements as `s`, but with all elements `e` for which `f(e)` is a true value
ordered first. Among those placed first and those placed after, the order stays the same.
"""

def promoted(s, f):
    """Return a list with the same elements as s, but with all
    elements e for which f(e) is a true value placed first.
    >>> promoted(range(10), odd) # odds in front
    [1, 3, 5, 7, 9, 0, 2, 4, 6, 8]
    """
    # Hint: two list comprehensions
    return ____________

    return [e for e in s if f(e)] + [e for e in s if not f(e)]

The boolean expression not f(e) is the same thing as saying only the elements for which f(e) returns False.

Slices & Recursion

“Slices of lists are useful for making recursive calls”

For any list s, the expression s[1:] creates a slice from index 1 to the end. Just chopped off the 0th element of s, which is s[0].

But, slicing does not impact the original list.

>>> s = [2, 3, 6, 4]
>>> s[1:]
[3, 6, 4]
>>> s
[2, 3, 6, 4]    # slicing `s` doesn't affect `s`

So, s = s[0] + s[1:].

Example 1: Reverse

# def reverse(s: list) -> list:
def reverse(s):
    """Return `s` in reverse order.

    >>> reverse([4, 6, 2])
    [2, 6, 4]
    """
    if not s:   # Note: The False value of a list is an empty list
        return []   # if the list `s` is empty, just return the empty list
    return _________

One way to do this is to reverse everything from the first element on and then take the thing that was formerly the first element and stick it at the end:

    return reverse(s[1:]) + [s[0]]

Another way of writing this is the opposite of the first one we just did. Take the last thing and stick it on the beginning:

    return [s[-1]] + reverse(s[:-1])

# might get confused
reverse(s[1:])  # reverse elements including s[1]
reverse(s[:-1]) # reverse elements excluding s[-1]

Example 2: Max Product

Implement max_product, which takes a list of numbers and returns the maximum product that can be formed by multiplying together non-consecutive elements of the list. Assume that all numbers in the input list are greater than or equal to 1.

def max_product(s):
    """Return the maximum product of non-consecutive elements of s.

    >>> max_product([10, 3, 1, 9, 2])   # 10 * 9
    90
    >>> max_product([5, 10, 5, 10, 5])  # 5 * 5 * 5
    125
    >>> max_product([])   # The product of no numbers is 1
    1
    """
    if s == []:
        return _
    if len(s) == 1:
        return ____
    else:
        return ___(________________________, __________________)

    if s == []:
        return 1
    if len(s) == 1:
        return s[0]
    else:   # Recursive step
        return max(s[0] * max_product(s[2:]), max_product(s[1:]))

In recursive step, we have a choice to make regarding the first element s[0]. We must return the max result from two paths.

One path is to include s[0], which simplifies the problem to finding max_product(s[2:])
and another path is to exclude the s[0], which simplifies the problem to finding max_product(s[1:])

Example 3: Sum Fun

Implement sums(n, m), which takes a total n and maximum m. It returns a list of all lists:
- that sum to n,
- that contain only positive numbers up to m, and
- in which no two adjacent numbers are the same.
Two lists with the same numbers in a different order should both be returned.

def sums(n, m):
    """Return lists that sum to n containing positive numbers up to 
    m that have no adjacent repeats.

    >>> sums(5, 1)
    []
    >>> sums(5, 2)
    [[2, 1, 2]]
    >>> sums(5, 3)
    [[1, 3, 1], [2, 1, 2], [2, 3], [3, 2]]
    >>> sums(5, 5)
    [[1, 3, 1], [1, 4], [2, 1, 2], [2, 3], [3, 2], [4, 1], [5]]
    """
    if n < 0:
        return []
    if n == 0:
        sums_to_zero = []     # Only way to sum to zero
        return [sums_to_zero] # List of all ways to sum to zero
    result = []
    for k in range(1, m + 1):
        result = result + [ ___ for rest in ___ if rest == [] or ___ ]
    return result

So here I need to complete the sums(n, m). I’m looking for all lists of positive integers that sum up to n, where each integer is at most m, and the key constraint is that no two adjacent nums can be the same. Order matters, meaning lists [1, 2] and [2, 1] are distinct.

Since I am exploring all possible lists that lead to a total n, a recursive backtracking approach is the most desired fit. I’ll make a choice (the first num k), reduce the problem size, and recurse. When I saw this problem at first, I struggled to find a way to combine the k with the recursive solutions in the given list comprehensive format.

I have the loop for k in range(1, m + 1):, and I know I need to build the result list. I kept getting stuck on what exactly fills these blanks.

I need to keep reminding that recursion is about simplifying. So let’s simplify. Say that I selected a k, then I need to think what is the new, smaller problem that I need to solve to find the rest of the list. The new total is not n anymore, it’s n - k, but the max num remains m. So, the necessary recursive call is sums(n - k, m). That goes into the second blank.

Now, I need to append the selected k into a list rest. In order to combine them into a list, I need [k] + rest, which is what goes into the first blank.

Now, the only remaining task is the constraint “no two adjacent nums can be the same”. In the if condition, I’m checking if I can put the k next to the list rest. I must know which single num in rest must be checked against k. It must be the first element rest[0] for sure. Because that’s the num adjacent to k. They must not be equal, so rest[0] != k is the condition that should be in the thrid blank. When we look at the line, since a case rest == [] is already handled, the entire line is completed. (IMPORTANT: We can’t swap the things in the or clause.)

Base cases are already provided in the skeleton. But, let’s make sure the stopping conditions are correctly established there. 1) If n == 0, we’ve found a valid list. So, we should return a list containing a single empty list which is [[]]. 2) If n < 0, that path is invalid, so return an empty list [].

    for k in range(1, m + 1):
        result = result + [ [k] + rest for rest in sums(n - k, m) if rest == [] or rest[0] != k ]
    return result

2. Containers

List review

Again, the Reverse example:

# def reverse(s: list) -> list:
def reverse(s):
    """Return `s` in reverse order.

    >>> reverse([4, 6, 2])
    [2, 6, 4]
    """
    if not s:   # Note: The False value of a list is an empty list
        return []   # if the list `s` is empty, just return the empty list
    return reverse(s[1:]) + [s[0]]

From the three options below, which correctly reverse?

(A) reverse(s[1:] + [s[0]])
- For (A), the problem is that we’re passing the entire list s[1:] + [s[0]] into reverse. If we look at the doctest, we would call reverse a [4, 6, 2], and then (A) would call reverse again with a list that has [6, 2, 4]. We’ve still got a list with three elements. So, (A) is going to run forever because it’s just going to keep reorganizing the elements within s. So the problem is that the last element [s[0]] should be outside the parentheses. It should be outside the call to reverse because we want to stick it on to the end only after we’ve reversed everything else.
(B) [s[-1 * i] for i in range(len(s))]
- If you see something like this, I think the thing that’s really helpful is to just start walking through an example. Let’s take the example again: reverse([4, 6, 2]). We’ll start with i = 0, and so the first element in our list (B) will be s[-1 * 0] which is s[0]. So the first thing on the list (B) will be that 4, and we know we don’t want four to be the first thing. We wanted them to be in reverse order.
(C) [s[-x + 1] for x in range(reverse(s))]
- One warning sign here is that the function signature def reverse(s): said reverse(s) and we’ve also got the same call reverse(s) in (C) to reverse s, so that’s a sign that our code is going to run forever because we haven’t made any progress. Also, even if there was something that returned to reverse(s) at some point, we’re taking the range of a list range(reverse(s)), and the argument that range takes is a number, an integer, like the length of the list, so this code would also error there. So, basically option (C) has a bunch of problems.

So, (A), (B), and (C) none of ‘em work at all.

Box-and-Pointer Notation

def f(s):
    x = s[0]
    return [x]

t = [3, [2 + 2, 5]]
u = [f(t[1]), t]
print(u)

Print Output: [[4], [3, [4, 5]]]

example: Double-Eights with a List

Implement double_eights, which takes a list s and returns whether two consecutive items are both 8.

VERSION 1: Using positions (indices)

def double_eights(s):
    """Return whether two consecutive items of list s are 8.
    
    >>> double_eights([1, 2, 8, 8])
    True
    >>> double_eights([8, 8, 0])
    True
    >>> double_eights([5, 3, 8, 8, 3, 5])
    True
    >>> double_eights([2, 8, 4, 6, 8, 2])
    False
    """
    for _______________________:
        if ___________________________:
            return True
    return False

The thing that I think is easiest to start with is to think about the case when we want to return True. We can fill the second blank in with something like s[i] == 8 and s[i + 1] == 8. This is going to check if there’s two things next to each other that are both eight. We’ve got to write a for loop. We definitely want to start at the beginning, but we’ve got to be careful not to go off the end of the list. If we end up at the last index, we’re going to check to see if the thing s[last index] is the same thing with s[last index + 1], then it’ll cause an error.

So, the way that we write the for loop is to write for i in range of len(s) - 1. This keeps us from falling off the the end. i in range(len(s) - 1).

    for i in range(len(s) - 1):
        if s[i] == 8 and s[i + 1] == 8:
            return True
    return False

But, what if s is an empty list? If s is an empty list, we would do range(0 - 1) which is range(-1). We need to know what happens if we do range(-1).

>>> list (range(-1))
[]

Because Python tries to make a range starting from 0 going up to -1, and then it doesn’t find anything, list (range(-1)) gives us an empty list []. So this does still work.

VERSION 2: Using slices

def double_eights(s):
    """Return whether two consecutive items of list s are 8.
    
    >>> double_eights([1, 2, 8, 8])
    True
    >>> double_eights([8, 8, 0])
    True
    >>> double_eights([5, 3, 8, 8, 3, 5])
    True
    >>> double_eights([2, 8, 4, 6, 8, 2])
    False
    """
    if _____ == [____]:
        return True
    elif len(s) < 2:
        return False
    else:
        return ___________________

The idea of this version is going to be that we’re going to try and find that chunk of the list where there’s those two 8s next to each other. One of hint in the structure here is that there’s no loop in the structure. The fact that there’s no loop is a good hint that we’re gonna need to write some recursive call somewhere in order to keep checking the rest of the list.

First thing is something that we’re gonna check for when we return True and the thing that we can check is the same as we did in VERSION1, just expressed differently.

if s[:2] == [8, 8]: >> We’re checking if the first two things in the list s are 8. If that matches, then we return True.

If len(s) < 2, then there’s definitely not an 88 left, so we can return False.

In the last blank, where we need to make a recursive call, we’re gonna check to see if the rest of s has any double 8s in it. >> double_eights(s[1:])

    if s[:2] == [8, 8]:
        return True
    elif len(s) < 2:
        return False
    else:
        return double_eights(s[1:])

Shouldn’t we have this check elif len(s) < 2 first to see if the length is less than two? Slices don’t return an error, they just return an empty list []. On the other hand, in general, list indexing is not generous. It’ll give us an error, but slicing will just return an empty list, without returning an error.

Processing Container values

Aggregation

Built-in functions take iterable arguments and aggregate them into a value:

sum(iterable[, start]) -> value

>>> sum(range(3))
3   # 0 + 1 + 2

>>> sum(range(3), 100)
103 # 100 + 0 + 1 + 2

def cube(k):
    return pow(k, 3)

def summation(n, term):
    """Sum the first n terms of a sequence.

    >>> summation(5, cube)
    225  # 1 + 8 + 27 + 64 + 125
    """
    total, k = 0, 1
    while k <= n:
        total, k = total + term(k), k + 1
    return total

Let’s rewrite summation to be much more concise using a aggregation func sum.

def summation2(n, term):
    return sum([term(x) for x in range(1, n + 1)])

[term(x) for x in range(1, n + 1)]: We’ve got a list comprehension here. The way that we create this list is we call term on x for every x in range(1, n + 1). So the first thing that we want in this range is 1. The last thing that we want in the range is n. So that’s why we pass an argument n + 1 because the last argument in range always tells us where to stop. We stop at one before that one.

max(iterable[, key = func]) -> value and max(a, b, c, ...[, key = func]) -> value

midterm_grades = [['Amy', 28], ['John', 35], ['Kay', 14], ['Apollo', 31]]

>>> midterm_grades
[['Amy', 28], ['John', 35], ['Kay', 14], ['Apollo', 31]]

>>> max(midterm_grades, key = lambda x: x[1])
['John', 35]

>>> max(range(3))
2
>>> max(0, 1, 2, 3, 4)
4

all(iterable) -> bool

Return True if bool(x) is True for all values x in the iterable.

Example

Definition: A prefix sum of a sequence of numbers is the sum of the first n elements for some positive length n.

"""Implement `prefix`, which takes a list of numbers `s` and returns a list of the prefix sums of `s` in increasing order of the length of the prefix."""

def prefix(s):
    """Return a list of all prefix sums of list s.

    >>> prefix([1, 2, 3, 0, 4, 5])
    [1, 3, 6, 6, 10, 15]
    >>> prefix([2, 2, 2, 0, -5, 5])
    [2, 4, 6, 6, 1, 6]
    """
    return [______________ for k in _____________]

In the first blank of the expression, we want to add more and more things into our sum. What we can do is k can be an index in range(len(s)). So, k will go 0, 1, 2, 3, … .

And the thing we would like to sum up is everything that includes s[k] and that’s why the second argument to slice should be k+1. >> sum(s[:k + 1]), the sum says we’re gonna sum up everything in s up until k + 1. So, here, what we should do is to check if those first and last things on the list look good.

    return [sum(s[:k + 1]) for k in range(len(s))]

Also, we could do this example recursively.

example: All Possible Sums

def sums(n: int) -> list[list[int]]:
    """Return a list of all of the possible lists of positive integers whose elements add up to n.

    >>> sums(3)
    [[1, 1, 1], [1, 2], [2, 1], [3]]
    """
    result = []
    for first in range(1, n):
        result += ____________________________________________
    return result + [[n]]

Let’s trace through what’s happening in that for loop. When we do for first in range(1, n):, we’re deciding what could be the first number in our list. For n = 3, that gives us 1 and 2 as possible first numbers.

Here’s where the recursive thinking kicks in. Let’s say I pick 1, then I need all the ways to make the remaining sum, which is n - first, or 3 - 1 = 2. So for each possible first number, I create a new list that starts with that first number, followed by each possible way to make the remaining sum.

So, the blank should be filled with [[first] + rest for rest in sums(n - first)].

Verify:

If first = 1, then sums(3 - 1) = sums(2) gives us [[1, 1], [2]]. So we get [1] + [1, 1] = [1, 1, 1] and [1] + [2] = [1, 2].
If first = 2, then sums(3 - 2) = sums(1) gives us [[1]]. So we get [2] + [1] = [2, 1].
Finally, we add [n] at the end to handle the case where the entire sum is just one number.

    result = []
    for first in range(1, n):
        result += [[first] + rest for rest in sums(n - first)]
    return result + [[n]]

Dictionaries

>>> {}
{}
>>> midterm_grades = {"Kay": 35, "John": 2}
>>> midterm_grades_list = [["Kay", 35], ["John", 2]]

The nice thing about the dictionary is I can look things up.

>>> midterm_grades["Kay"]
35

Just like we had the list comprehension to make a list, we can do a similar thing where we tell Python how to make a dictionary.

# Dictionary Comprehensions
#   {<key exp>  :   <value exp> for <name>  in     <iter exp>      if <filter exp>} 
>>> {grade[0]   :   grade[1]    for grade   in  midterm_grades_list}
{'Kay': 35, 'John': 2}
>>> {name:grade for name, grade in midterm_grades_list} # Unpacking
{'Kay': 35, 'John': 2}

This gives me a new dictionary where I’ve told Python iterate through everything in midterm_grades_list.

>>> midterm_grades
{"Kay": 35, "John": 2}
>>> type(midterm_grades)
<class 'dict'>
>>> len(midterm_grades)
2

midterm_grades is also a thing that’s iterable. That’s this word that we’ve been throwing around, but that means that we can iterate over all of the things in midterm_grades. I could write things like:

for x in midterm_grades:
    print(x)

Kay
John

This might not be what we expected. We got all of the names, but we didn’t get any of the values. So this is how dictionaries work, that the thing that’s iterable in a dictionary is just the key.

for x in midterm_grades:
    print(x, " got a grade of ", midterm_grades[x])

Kay got a grade of 35
John got a grade of 2

If you’d like all of the values:

>>> midterm_grades.values()
dict_values([35, 2])        # looks like a list, but it's not quite a list
>>> type(midterm_grades.values())
<class 'dict_values'>

>>> midterm_grades.values()[1]  # we can't index into it
# TypeError: 'dict_values' object is not subscriptable

But, it is iterable, which means that I can write a for loop or I can use the aggregation functions.

for grade in midterm_grades.values():
    print(grade)

35
2

We can pass it into some of the aggregation functions.

>>> min(midterm_grades.values())
2   # we can do the same thing with the `max` or the `sum`

But, we can also turn midterm_grades.values() into a list.

>>> list(midterm_grades.values())
[35, 2]

# FYI
>>> midterm_grades
{"Kay": 35, "John": 2}
>>> list(midterm_grades)
['Kay', 'John']

We can make a key with multiple items. But that does need to be a single value. We can’t just put without brackets.

>>> {"Kay": [35, 0, 89]}
{'Kay': [35, 0, 89]}

>>> {"Kay": 35, 0, 89}
# SyntaxError: invalid syntax

We could also make this a function.

def get_grade():
    return 30
"""-----------------------"""
>>> {get_grade():get_grade()}
{30: 30}

Dictionaries - Example 1: Multiples

Implement multiples, which takes two lists of positive numbers s and factors. It returns a dictionary in which each element of factors is a key, and the value for each key is a list of the elements of s that are multiples of the key.

def multiples(s, factors):
    """Create a dictionary where each factor is a key and each value is the elements of s that are multiples of the key.
    
    >>> multiples([3, 4, 5, 6, 7, 8], [2, 3])
    {2: [4, 6, 8], 3: [3, 6]}
    >>> multiples([1, 2, 3, 4, 5], [2, 5, 8])
    {2: [2, 4], 5: [5], 8: []}
    """
    return {d: [x for x in _ if __________] for d in _______}

When we look at the return statement, that is telling us that we’re going to make a bunch of dictionary entries that each have d as the key. I think it’s easiest to fill in the last blank first, because we can think of what do we want d to be. We want d to be each of the things in factors.

    return {d: [x for x in _ if __________] for d in factors}

Now, for each thing d in factors, we want the value to be a list. That’s the thing in square brackets: [x for x in ________ if ___________]

We want x to be all of the things in s for which d is a factor of them. We’re looping through all of the things in the list s and we’d like to keep them only if x % d == 0.

    return {d: [x for x in s if x % d == 0] for d in factors}

Recursion (again)

The core idea behind tree recursion is to make a really small choice, and then for each of those choices recurse.

For a lot of other problems, it’s gonna be helpful to think about what is the smallest choice that I can possibly make before punting the rest of the work to another recursive call.

Example 1 - Recursion and Strings

Definition: When parking vehicles in a row, a motorcycle takes up 1 parking spot and a car takes up 2 adjacent parking spots. A string of length n can represent n adjacent parking spots using % for a motorcycle, <> for a car, and . for an empty spot.

For example: ’.%%.<><>’ (Thanks to the Berkeley Math Circle for introducing this question.)

Implement count_park, which returns the number of ways that vehicles can be parked in n adjacent parking spots for positive integer n. Some or all spots can be empty.

def count_park(n):
    """Count the ways to park cars and motorcycles in n adjacent spots.
    >>> count_park(1) # '.' or '%'
    2
    >>> count_park(2) # '..', '.%', '%.', '%%', or '<>'
    5
    >>> count_park(4) # some examples: '<><>', '.%%.', '%<>%', '%.<>'
    29
    """

What’s the very first thing we can think about doing here? Let’s say we’re trying to fill three parking spaces, which means we have n == 3. We haven’t parked anything. How can we make just a tiny bit of progress? What’s the smallest possible progress that we can make? We can decide what to put in the first spot. Here’s the three choices. Two options(% and .) leave two spaces left, but the car(<>) option leaves only one space left.

Now, we’ve made those choices, what recursive call should we make?

Once we’ve decided to park a motorcycle(%), we’ve got two spaces left. We already filled one of them, so we can call count_park(n - 1) to decide how to fill the rest of those spaces.

Likewise, when we use an empty spot(.), we can call count_park(n - 1) to fill the remaining spaces.

Now, when we parked a car(<>), let’s just make a recursive call count_park(n - 2) without trying fancy thinking so that our lives will be much easier.

def count_park(n):
    """Count the ways to park cars and motorcycles in n adjacent spots.
    >>> count_park(1) # '.' or '%'
    2
    >>> count_park(2) # '..', '.%', '%.', '%%', or '<>'
    5
    >>> count_park(4) # some examples: '<><>', '.%%.', '%<>%', '%.<>'
    29
    """
    if n < 0:
        return _
    elif n == 0:
        return _
    else:
        return ________________________________________________________

Before we look at the base case, it’s always good to look at the recursive call first. Because the base cases for recursive calls are very very hard.

We know we need to make some recursive call here. The actual results that we want in the last blank is just to add all of those counts up.

        return count_park(n - 1) + count_park(n - 1) + count_park(n - 2)

In general, with tree recursion, we decide to make some choice.

Now let’s fill in those bases cases. The most helpful thing to do it is to try and think of which recursive calls will lead to the base cases. The best way to do that is just to do an simplest example on our scratch paper or something like that.

Back to the code, when n < 0, it means we parked too much. So we’re gonna return 0. There’s no valid ways to park in this direction.

If n == 0, we parked exactly the right amount of stuff, so that’s where we’re gonna return 1.

    if n < 0:
        return 0
    elif n == 0:
        return 1
    else:
        return count_park(n - 1) + count_park(n - 1) + count_park(n - 2)

Quick Review: Adding Lists & Strings

>>> x = 'cal'
>>> y = 'bears'
>>> u = [x]
>>> v = [y]

>>> x + y
'calbears'

>>> u + v
['cal', 'bears']

>>> ['go ' + z for z in [x, y]]
['go cal', 'go bears']

# this is very IMPORTANT below

>>> s = []  # Using a list that's totally empty
>>> ['cal' + x for x in s]  # `x` is never gonna get assigned to anything
[]  # So, any of the code will be executed, and end up with just an empty list

>>> s = ['']    # This is not an empty list. It's a list that has one item, empty string.
>>> ['cal' + x for x in s]  # we've got one thing to assign `x` to. It's an empty string.
['cal'] # and we get a list with just 'cal' back

Example 2 - Recursion and Strings

Implement park, which returns a list of all the ways, represented as strings, that vehicles can be parked in n adjacent parking spots for positive integer n. Spots can be empty.

def park(n):
    """Return the ways to park cars and motorcycles in `n` adjacent spots.
    >>> park(1)
    ['%', '.']
    >>> park(2)
    ['%%', '%.', '.%', '..', '<>']
    >>> len(park(4))    # some examples: '<><>', '.%%.', '%<>%', '%.<>'
    29
    """
    if n < 0:
        return __
    elif n == 0:
        return _____
    else:
        return _____________________________________________________________________________________________________

Example: park(3)

%%%
%%.
%.%     # motorcycle first
%..
%<>
------
.%%
.%.
..%     # nothing first
...
.<>
------
<>%     # car first
<>.

    else:
        return (motorcycle first                + nothing first                     + car first)

    else:
        return ['%' + s for s in park(n - 1)]   + ['.' + s for s in park(n - 1)]    + ['<>' + s for s in park(n - 2)]

What are the base cases?

When n < 0, we’ve got no valid ways of parking. We have an empty list []. There’s nothing to do.

    if n < 0:
        return []

When n == 0, that means we’ve filled up all of the spots. If we just returned an empty list, we would never stick something onto anything. We need something to iterate through so that we can create a string. So we don’t want to return an empty list []. That’s where we’ve got a list that just has one thing, an empty string [''], not an empty list [].

    elif n == 0:
        return ['']

Final Answer:

def park(n):
    if n < 0:
        return []
    elif n == 0:
        return ['']
    else:
        return ['%' + s for s in park(n - 1)]   + ['.' + s for s in park(n - 1)]    + ['<>' + s for s in park(n - 2)]

Assignments

Lab 03: Recursion, Python Lists

Q1: WWPD: Lists & Ranges

Q2: Print If

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

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

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

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 list is “zero-indexed”; the index of the first element is 0.)

# --------------------------
# Q3: Close
def close(s: list[int], k: int) -> int:
    """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 ***"
        if abs(s[i] - i) <= k:
            count += 1
    return count

Q4: WWPD: List Comprehensions

Q5: Close List

Implement close_list, which takes a list of integers s and a non-negative integer k. It returns a list of the elements of s that 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.

# Q5: Close List
def close_list(s: list[int], k: int) -> list[int]:
    """Return a list of the elements of s that are within k of their index.

    >>> t = [6, 2, 4, 3, 5]
    >>> close_list(t, 0)  # Only 3 is equal to its index
    [3]
    >>> close_list(t, 1)  # 2, 3, and 5 are within 1 of their index
    [2, 3, 5]
    >>> close_list(t, 2)  # 2, 3, 4, and 5 are all within 2 of their index
    [2, 4, 3, 5]
    """
    assert k >= 0
    return [s[i] for i in range(len(s)) if abs(s[i] - i) <= k]

Q6: 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)).)

# Q6: Squares Only
from math import sqrt

def squares(s: list[int]) -> list[int]:
    """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 [int(sqrt(n)) for n in s if sqrt(n) == round(sqrt(n))]
            # the reason why I use `int()` is to convert float `sqrt(n)` to integers

Q7: 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).

# Q7: Double Eights
def double_eights(n: int) -> bool:
    """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
    >>> # ban iteration
    >>> from construct_check import check
    >>> check(SOURCE_FILE, 'double_eights', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"
    # Base Case: if n is a single digit or less to contain "88", we need to stop
    if n < 10:
        return False
    # check the last two digits (using % 100) for the '88' pattern
    elif n % 100 == 88:
        return True
    # Recursive Step: remove the last digit then check the rest of the number
    else:
        return double_eights(n // 10)

Q8: Making Onions

Write a function make_onion that takes in two one-argument functions, f and g. It returns a function that takes in three arguments: x, y, and limit. The returned function returns True if it is possible to reach y from x using up to limit calls to f and g, and False otherwise. For example, if f adds 1 and g doubles, then it is possible to reach 25 from 5 in four calls: f(g(g(f(5)))).

# Q8: Making Onions
def make_onion(f, g):
    """Return a function can_reach(x, y, limit) that returns
    whether some call expression containing only f, g, and x with
    up to limit calls will give the result y.

    >>> up = lambda x: x + 1
    >>> double = lambda y: y * 2
    >>> can_reach = make_onion(up, double)
    >>> can_reach(5, 25, 4)      # 25 = up(double(double(up(5))))
    True
    >>> can_reach(5, 25, 3)      # Not possible
    False
    >>> can_reach(1, 1, 0)      # 1 = 1
    True
    >>> add_ing = lambda x: x + "ing"
    >>> add_end = lambda y: y + "end"
    >>> can_reach_string = make_onion(add_ing, add_end)
    >>> can_reach_string("cry", "crying", 1)      # "crying" = add_ing("cry")
    True
    >>> can_reach_string("un", "unending", 3)     # "unending" = add_ing(add_end("un"))
    True
    >>> can_reach_string("peach", "folding", 4)   # Not possible
    False
    """
    def can_reach(x, y, limit):
        if limit < 0:
            return False
        elif x == y:
            return True
        else:
            return can_reach(f(x), y, limit - 1) or can_reach(g(x), y, limit - 1)
    return can_reach

Wrapping up

You like squirrels? I do.

Hope you have a great upcoming week!

Thank you.

References

[1] J. DeNero, D. Klein, P. Abbeel, “2.3 Sequences,” in Composing Programs. [Online]. Available: https://www.composingprograms.com/pages/23-sequences.html. Accessed: Sep. 26, 2025. (Originally published 2016)

Sequences Containers Data Abstraction Python CS 61A Structure and Interpretation of Computer Programs

Sequences, Containers, Data Abstraction

Sequences, Containers, Data Abstraction

1. Sequences

List Indexing

for loops

range

List Comprehensions

Example 1: Evens

Example 2: Two Lists

Example 3: Promoted

Slices & Recursion

Example 1: Reverse

Example 2: Max Product

Example 3: Sum Fun

2. Containers

List review

Box-and-Pointer Notation

example: Double-Eights with a List

Processing Container values

Aggregation

Example

example: All Possible Sums

Dictionaries

Dictionaries - Example 1: Multiples

Recursion (again)

Example 1 - Recursion and Strings

Quick Review: Adding Lists & Strings

Example 2 - Recursion and Strings

Assignments

Lab 03: Recursion, Python Lists

Q1: WWPD: Lists & Ranges

Q2: Print If

Q3: Close

Q4: WWPD: List Comprehensions

Q5: Close List

Q6: Squares Only

Q7: Double Eights

Q8: Making Onions

Wrapping up

References

`for` loops

`range`