CS61A: Lecture 12

Manipulating Lists

• Making a list with a list literal
• Get a certain element using item selection
• Get a portion of the list using slicing
• Make a longer list using addition

s = [4, 7, 9, 11]
print(s[0])
print(s[1:])
print([3] + s)

4
[7, 9, 11]
[3, 4, 7, 9, 11]

Max Product

• Write a function that takes in a list and returns the maximum product that can be formed using non-consecutive elemnts of the list. All numbers in the input list are greater than or equal to 1.

def max_product(s):
    """Return the maximum product that can be formed using non-consecutive elements in the list.
    """
    if len(s) == 0:
        return 1
    elif len(s) == 1:
        return s[0]
    return max(s[0] * max_product(s[2:]), s[1] * max_product(s[3:]))
    # return max(s[0] * max_product(s[2:], max_product(s[1:]))) <--- Denero's solution

max_product([])

1

Sums Fun

Implement sums(n, m), which takes a total n and maximium m. It returns a list of all lists: - That sums to n, - That contain only positive numbers up to m, and - in which no two adjacent numbers are the same

def sums(n, m):
    if n < 0:
        return []
    if n == 0:
        sums_to_zero = []
        return [sums_to_zero]
    result = []
    for k in range(1, m+1):
        # if rest == [] checks to make sure that we are not accessing an index out of bounds error.
        result = result + [ [k]+rest for rest in sums(n-k,m) if rest == [] or k != rest[0]]
    return result

sums(5,5)

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

xs = range(-10, 11)
ys = [x*x - 2*x + 1 for x in xs]
def x_corresponding_to_min_y():
    return xs[ys.index(min(ys))]

x_corresponding_to_min_y()

1

• We can also pass in a function into the min function to get the key.

xs = range(-10, 11)
ys = [x*x - 2*x + 1 for x in xs]
def x_corresponding_to_min_y():
    return xs[min(range(len(ys)), key=lambda i : ys[i])]

x_corresponding_to_min_y()

1

• If there are multiple minimums, then

Slicing Practice

• Implement prefix, which takes a list of numbers s and returns a list of the prefix sums of s in in creasing order of the length of the prefix.

def prefix(s):
    """Return a list of all prefix sums of list s."""
    return [sum(s[:k+1]) for k in range(len(s))]

prefix([1,2,3,0,4,5])

[1, 3, 6, 6, 10, 15]

• make a function park that prints out all the ways of arranging a parking lot.

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

['%%%%',
 '%%%.',
 '%%.%',
 '%%..',
 '%%<>',
 '%.%%',
 '%.%.',
 '%..%',
 '%...',
 '%.<>',
 '%<>%',
 '%<>.',
 '.%%%',
 '.%%.',
 '.%.%',
 '.%..',
 '.%<>',
 '..%%',
 '..%.',
 '...%',
 '....',
 '..<>',
 '.<>%',
 '.<>.',
 '<>%%',
 '<>%.',
 '<>.%',
 '<>..',
 '<><>']