Some objects in Python, such as lists and dictionaries, are mutable, meaning that their contents or state can be changed. Other objects, such as numeric types, tuples, and strings, are immutable, meaning they cannot be changed once they are created.

The two most common mutation operations for lists are item assignment and the append method.

>>> s = [1, 3, 4]
>>> t = s  # A second name for the same list
>>> t[0] = 2  # this changes the first element of the list to 2, affecting both s and t
>>> s
[2, 3, 4]
>>> s.append(5)  # this adds 5 to the end of the list, affecting both s and t
>>> t
[2, 3, 4, 5]

There are many other list mutation methods:

• append(elem): Add elem to the end of the list. Return None.
• extend(s): Add all elements of iterable s to the end of the list. Return None.
• insert(i, elem): Insert elem at index i. If i is greater than or equal to the length of the list, then elem is inserted at the end. This does not replace any existing elements, but only adds the new element elem. Return None.
• remove(elem): Remove the first occurrence of elem in list. Return None. Errors if elem is not in the list.
• pop(i): Remove and return the element at index i.
• pop(): Remove and return the last element.

Dictionaries also have item assignment (often used) and pop (rarely used).

>>> d = {2: 3, 4: 16}
>>> d[2] = 4
>>> d[3] = 9
>>> d
{2: 4, 4: 16, 3: 9}
>>> d.pop(4)
16
>>> d
{2: 4, 3: 9}

We can create our own custom iterators by writing a generator function, which returns a special type of iterator called a generator. Generator functions have yield statements within the body of the function instead of return statements. Calling a generator function will return a generator object and will not execute the body of the function.

For example, let's consider the following generator function:

def countdown(n):
    print("Beginning countdown!")
    while n >= 0:
        yield n
        n -= 1
    print("Blastoff!")

Calling countdown(k) will return a generator object that counts down from k to 0. Since generators are iterators, we can call iter on the resulting object, which will simply return the same object. Note that the body is not executed at this point; nothing is printed and no numbers are outputted.

>>> c = countdown(5)
>>> c
<generator object countdown ...>
>>> c is iter(c)
True

So how is the counting done? Again, since generators are iterators, we call next on them to get the next element! The first time next is called, execution begins at the first line of the function body and continues until the yield statement is reached. The result of evaluating the expression in the yield statement is returned. The following interactive session continues from the one above.

>>> next(c)
Beginning countdown!
5

Unlike functions we've seen before in this course, generator functions can remember their state. On any consecutive calls to next, execution picks up from the line after the yield statement that was previously executed. Like the first call to next, execution will continue until the next yield statement is reached. Note that because of this, Beginning countdown! doesn't get printed again.

>>> next(c)
4
>>> next(c)
3

The next 3 calls to next will continue to yield consecutive descending integers until 0. On the following call, a StopIteration error will be raised because there are no more values to yield (i.e. the end of the function body was reached before hitting a yield statement).

>>> next(c)
2
>>> next(c)
1
>>> next(c)
0
>>> next(c)
Blastoff!
StopIteration

Separate calls to countdown will create distinct generator objects with their own state. Usually, generators shouldn't restart. If you'd like to reset the sequence, create another generator object by calling the generator function again.

>>> c1, c2 = countdown(5), countdown(5)
>>> c1 is c2
False
>>> next(c1)
5
>>> next(c2)
5

Here is a summary of the above:

• A generator function has a yield statement and returns a generator object.
• Calling the iter function on a generator object returns the same object without modifying its current state.
• The body of a generator function is not evaluated until next is called on a resulting generator object. Calling the next function on a generator object computes and returns the next object in its sequence. If the sequence is exhausted, StopIteration is raised.

• A generator "remembers" its state for the next next call. Therefore,

  • the first next call works like this:

    1. Enter the function and run until the line with yield.
    2. Return the value in the yield statement, but remember the state of the function for future next calls.

  • And subsequent next calls work like this:

    1. Re-enter the function, start at the line after the yield statement that was previously executed, and run until the next yield statement.
    2. Return the value in the yield statement, but remember the state of the function for future next calls.
• Calling a generator function returns a brand new generator object (like calling iter on an iterable object).
• A generator should not restart unless it's defined that way. To start over from the first element in a generator, just call the generator function again to create a new generator.

Another useful tool for generators is the yield from statement. yield from will yield all values from an iterator or iterable.

>>> def gen_list(lst):
...     yield from lst
...
>>> g = gen_list([1, 2, 3, 4])
>>> next(g)
1
>>> next(g)
2
>>> next(g)
3
>>> next(g)
4
>>> next(g)
StopIteration

An iterable is an object whose elements we can go through one at a time. Iterables can be used in for loops and list comprehensions. Iterables can also be converted into lists using the list function. Examples of iterables we have seen so far in Python include strings, lists, tuples, and ranges.

>>> for x in "cat":
...     print(x)
c
a
t
>>> [x*2 for x in (1, 2, 3)]
[2, 4, 6]
>>> list(range(4))
[0, 1, 2, 3]

Note the abstraction present here: given some iterable object, we have a set of defined actions that we can take with it. In this discussion, we will peak below the abstraction barrier and examine how iterables are implemented "under the hood".

In Python, iterables are formally implemented as objects that can be passed into the built-in iter function to produce an iterator. An iterator is another type of object that can produce elements one at a time with the next function.

• iter(iterable): Returns an iterator over the elements of the given iterable.
• next(iterator): Returns the next element in an iterator, or raises a StopIteration exception if there are no elements left.

For example, a list of numbers is an iterable, since iter gives us an iterator over the given sequence, which we can navigate using the next function:

>>> lst = [1, 2, 3]
>>> lst_iter = iter(lst)
>>> lst_iter
<list_iterator object ...>
>>> next(lst)
1
>>> next(lst)
2
>>> next(lst)
3
>>> next(lst)
StopIteration

Iterators are very simple. There is only a mechanism to get the next element in the iterator: next. There is no way to index into an iterator and there is no way to go backward. Once an iterator has produced an element, there is no way for us to get that element again unless we store it.

Note that iterators themselves are iterables: calling iter on an iterator simply returns the same iterator object.

For example, we can see what happens when we use iter and next with a list:

>>> lst = [1, 2, 3]
>>> next(lst)             # Calling next on an iterable
TypeError: 'list' object is not an iterator
>>> list_iter = iter(lst) # Creates an iterator for the list
>>> next(list_iter)       # Calling next on an iterator
1
>>> next(iter(list_iter)) # Calling iter on an iterator returns itself
2
>>> for e in list_iter:   # Exhausts remainder of list_iter
...     print(e)
3
>>> next(list_iter)       # No elements left!
StopIteration
>>> lst                   # Original iterable is unaffected
[1, 2, 3]

The map and filter functions we learned earlier in class return iterator objects.

A tree is a data structure that represents a hierarchy of information. A file system is a good example of a tree structure. For example, within your cs61a folder, you have folders separating your projects, lab assignments, and homework. The next level is folders that separate different assignments, hw01, lab01, hog, etc., and inside those are the files themselves, including the starter files and ok. Below is an incomplete diagram of what your cs61a directory might look like.

As you can see, unlike trees in nature, the tree abstract data type is drawn with the root at the top and the leaves at the bottom.

For a tree t:

• Its root label can be any value, and label(t) returns it.
• Its branches are trees, and branches(t) returns a list of branches.
• An identical tree can be constructed with tree(label(t), branches(t)).
• You can call functions that take trees as arguments, such as is_leaf(t).
• That's how you work with trees. No t == x or t[0] or x in t or list(t), etc.
• There's no way to change a tree (that doesn't violate an abstraction barrier).

Here's an example tree t1, for which its branch branches(t1)[1] is t2.

t2 = tree(5, [tree(6), tree(7)])
t1 = tree(3, [tree(4), t2])

A path is a sequence of trees in which each is the parent of the next.

items may be the SAME list object as inventory. Try to think about what happens if you loop over items while inventory (the same list) is being mutated underneath you, and what happens if you remove multiple matching elements from a list while iterating through it.

def inventory_pickup(inventory: list, items: list, capacity: int) -> list:
    """Simulate picking up every item in items and add them, one at a time, to the inventory IN PLACE.
    The function should return the mutated inventory.

    >>> inv = [1, 2, 1, 3, 1]
    >>> inv_test = inventory_pickup(inv, [1, 4], 10)
    >>> inv_test
    [2, 3, 1, 4]

    >>> inv2 = [11, 12, 13]
    >>> inv2_test = inventory_pickup(inv2, inv2, 7)
    >>> inv2_test
    [11, 12, 13]

    >>> inv3 = [1, 2, 1, 3, 1]
    >>> check_mutation = inv3
    >>> inv3_test = inventory_pickup(inv3, inv3, 3)
    >>> inv3_test
    [2, 3, 1]
    >>> check_mutation is inv3_test
    True

    >>> inv4 = [1, 2, 3, 4]
    >>> inv4_test = inventory_pickup(inv4, [5, 6, 7, 8, 9, 10], 10)
    >>> inv4_test
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

    >>> inv5 = [1, 2, 3, 4]
    >>> inv5_test = inventory_pickup(inv5, [5, 6, 7, 8], 6)
    >>> inv5_test
    [3, 4, 5, 6, 7, 8]

    >>> inv6 = ['hello', 'world']
    >>> inv6_test = inventory_pickup(inv6, ['hi', 'hello'], 4)
    >>> inv6_test
    ['world', 'hi', 'hello']
    """
    "*** YOUR CODE HERE ***"

python3 ok -q inventory_pickup
Copy
✂️

def berry_finder(t):
    """Returns True if t contains a node with the value 'berry' and 
    False otherwise.

    >>> scrat = tree('berry')
    >>> berry_finder(scrat)
    True
    >>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('berry')]), tree('branch2')])
    >>> berry_finder(sproul)
    True
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> berry_finder(numbers)
    False
    >>> t = tree(1, [tree('berry',[tree('not berry')])])
    >>> berry_finder(t)
    True
    """
    "*** YOUR CODE HERE ***"

python3 ok -q berry_finder
Copy
✂️

def size_of_tree(t):
    """Return the number of entries in the tree.
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> size_of_tree(numbers)
    7
    """
    "*** YOUR CODE HERE ***"

python3 ok -q size_of_tree
Copy
✂️

def make_path(t, p):
    """Return a tree with all of the nodes of t and a path with labels p.

    >>> t2 = tree(5, [tree(6), tree(7)])
    >>> t1 = tree(3, [tree(4), t2])
    >>> make_path(t1, [3, 5, 7]) == t1
    True
    >>> print_tree(make_path(t1, [3, 8, 9, 1]))
    3
      4
      5
        6
        7
      8
        9
          1
    >>> print_tree(make_path(t1, [3, 4, 8, 9]))
    3
      4
        8
          9
      5
        6
        7
    >>> print_tree(make_path(tree(2, [tree(1), t1]), [2, 3, 5, 6, 8]))
    2
      1
      3
        4
        5
          6
            8
          7
    """
    assert p[0] == label(t), 'It is not possible to make this path'
    if len(p) == 1:
        return ____
    new_branches = []
    found_p1 = False
    for b in branches(t):
        if ____:
            "*** YOUR CODE HERE ***"
        else:
            new_branches.append(b)
    if not found_p1:
        new_branches.append(make_path(____, ____))
    return tree(____, new_branches)

What recursive calls will you make?

make_path(b, p[1:]) can only be called on a b whose label is p[1]. You either find such a branch or make one with tree(p[1]).

What type of values do they return?

The recursive call returns a tree that contains a path with labels p[1:].

What do the possible return values mean?

This return value is a branch of the tree returned by make_path(t, p).

How can you use those return values to complete your implementation?

Place the return value in the list of new_branches.

Since you've already asserted that p[0] == label(t), if p has length 1 then t contains a path with labels p, so you can just return t.

If p[1] is a label of a branch, then a path should be made through that branch. Otherwise, a new branch must be made.

Search through each branch to find one whose label is p[1], then append the result of a recursive call on that branch to new_branches.

In the case that no branch has label p[1], create a new branch with tree(p[1]), use make_path to build the rest of the branch, and append that result to new_branches.

python3 ok -q make_path
Copy
✂️

def merge(incr_a, incr_b):
    """Yield the elements of strictly increasing iterables incr_a and incr_b, removing
    repeats. Assume that incr_a and incr_b have no repeats. incr_a or incr_b may or may not
    be infinite sequences.

    >>> m = merge([0, 2, 4, 6, 8, 10, 12, 14], [0, 3, 6, 9, 12, 15])
    >>> type(m)
    <class 'generator'>
    >>> list(m)
    [0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
    >>> def big(n):
    ...    k = 0
    ...    while True: yield k; k += n
    >>> m = merge(big(2), big(3))
    >>> [next(m) for _ in range(11)]
    [0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
    """
    iter_a, iter_b = iter(incr_a), iter(incr_b)
    next_a, next_b = next(iter_a, None), next(iter_b, None)
    "*** YOUR CODE HERE ***"

python3 ok -q merge
Copy
✂️

def yield_paths(t, target):
    """
    Yields all possible paths from the root of t to a node with the label
    target as a list.

    >>> t1 = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
    >>> print_tree(t1)
    1
      2
        3
        4
          6
        5
      5
    >>> next(yield_paths(t1, 6))
    [1, 2, 4, 6]
    >>> path_to_5 = yield_paths(t1, 5)
    >>> sorted(list(path_to_5))
    [[1, 2, 5], [1, 5]]

    >>> t2 = tree(0, [tree(2, [t1])])
    >>> print_tree(t2)
    0
      2
        1
          2
            3
            4
              6
            5
          5
    >>> path_to_2 = yield_paths(t2, 2)
    >>> sorted(list(path_to_2))
    [[0, 2], [0, 2, 1, 2]]
    """
    if label(t) == target:
        yield ____
    for b in branches(t):
        for ____ in ____:
            yield ____

python3 ok -q yield_paths
Copy
✂️

python3 ok -q midsem_survey
Copy
✂️

python3 ok --score