Lab 7 - Midterm review

HOF, Recursion, Trees, Sequences & Mutability

Q1, Q2 & Q6 are non-coding (ENV Diagrams/What Would Python Do?)

I remember spending a long time, banging my head against the wall on Q4. 😇

Instructions: https://inst.eecs.berkeley.edu/~cs61a/su19/lab/lab07/

Solution: https://github.com/tomthestrom/cs61a/blob/master/lab/lab07/lab07.py

Q3: Insect Combinatorics

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and wants to end up at the top right corner, (M-1, N-1). The insect is only capable of moving right or up. Write a function paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal. (There is a closed-form solution to this problem, but try to answer it procedurally using recursion.)

def paths(m, n):
    """Return the number of paths from one corner of an
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    "*** YOUR CODE HERE ***"

Q3: Solution

def paths(m, n):
    """Return the number of paths from one corner of an
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    "*** YOUR CODE HERE ***"
    if m == 1 or n == 1:
        return 1
    else:
        move_left = paths(m - 1, n) 
        move_down = paths(m, n - 1)

        return move_left + move_down

Q4: Number of Trees

How many different possible full binary tree (each node has two branches or 0, but never 1) structures exist that have exactly n leaves?

For those interested in combinatorics, this problem does have a closed form solution):

def num_trees(n):
    """How many full binary trees have exactly n leaves? E.g.,

    1   2        3       3    ...
    *   *        *       *
       / \      / \     / \
      *   *    *   *   *   *
              / \         / \
             *   *       *   *

    >>> num_trees(1)
    1
    >>> num_trees(2)
    1
    >>> num_trees(3)
    2
    >>> num_trees(8)
    429

    """
    "*** YOUR CODE HERE ***"

Q4: Solution

def build_fbt(nodes):
    if nodes == 0:
        return [tree('LEAF')]
    else:
        trees = []
        """
        Begins with 0 for the left and "nodes - 0 - 1(the root node)" for the right - so we start building the trees from the right side
        """
        for left_range in range(nodes):
            right_range = nodes - left_range - 1
            left_branch = build_fbt(left_range) 
            right_branch = build_fbt(right_range)
            for right_trees in right_branch:
                for left_trees in left_branch:
                    trees.append(tree('NODE', [left_trees, right_trees]))
        return trees
    
def num_trees(n):
    """How many full binary trees have exactly n leaves? E.g.,

    1   2        3       3    ...
    *   *        *       *
       / \      / \     / \
      *   *    *   *   *   *
              / \         / \
             *   *       *   *

    >>> num_trees(1)
    1
    >>> num_trees(2)
    1
    >>> num_trees(3)
    2
    >>> num_trees(8)
    429

    """
    "*** YOUR CODE HERE ***"
    return len(build_fbt(n-1))

Q5: Pruning Leaves

Define a function prune_leaves that given a tree t and a tuple of values vals, produces a version of t with all its leaves that are in vals removed. Do not attempt to try to remove non-leaf nodes and do not remove leaves that do not match any of the items in vals. Return None if pruning the tree results in there being no nodes left in the tree.

def prune_leaves(t, vals):
    """Return a modified copy of t with all leaves that have a label
    that appears in vals removed.  Return None if the entire tree is
    pruned away.

    >>> t = tree(2)
    >>> print(prune_leaves(t, (1, 2)))
    None
    >>> 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
    >>> print_tree(prune_leaves(numbers, (3, 4, 6, 7)))
    1
      2
      3
        5
      6
    """
    "*** YOUR CODE HERE ***"

Q5: Solution

def prune_leaves(t, vals):
    """Return a modified copy of t with all leaves that have a label
    that appears in vals removed.  Return None if the entire tree is
    pruned away.

    >>> t = tree(2)
    >>> print(prune_leaves(t, (1, 2)))
    None
    >>> 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
    >>> print_tree(prune_leaves(numbers, (3, 4, 6, 7)))
    1
      2
      3
        5
      6
    """
    "*** YOUR CODE HERE ***"
    def is_leaf_to_remove(t, vals):
        return is_leaf(t) and label(t) in vals
    
    #case we get a leaf as input and it's value in vals
    if is_leaf_to_remove(t, vals):
        return None
            
    if is_leaf(t):
        return tree(label(t))
    else:
        new_branches = []
        for branch in branches(t):
            if is_leaf_to_remove(branch, vals):
                continue
            new_branches += [prune_leaves(branch, vals)]
    
        return tree(label(t), new_branches)