Lab 5 - Sequences, Trees

A bit more challenging than Lab 4 - use recursion in all 3 questions.

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

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

Q1: Merge

We've provided you with an implementation of the function merge. merge takes 2 sorted lists lst1 and lst2, and returns a new list that contains all the elements in the two lists in sorted order.

A list is sorted if the elements appear in nondecreasing order. [1, 2, 3] is a sorted list, but [3, 1, 2] is not.

This solution does not pass the doctests. It is your job to figure out what is wrong with the implementation and correct the error.

def merge(lst1, lst2):
    """Merges two sorted lists.
    >>> merge([1], [2])
    [1, 2]
    >>> merge([2], [1])
    [1, 2]
    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    if not lst1 or not lst2:
        return []
    elif lst1[0] < lst2[0]:
        return [lst1[0]] + merge(lst1[1:], lst2)
    else:
        return [lst2[0]] + merge(lst1, lst2[1:])

Q1: Solution

def merge(lst1, lst2):
    """Merges two sorted lists.
    >>> merge([1], [2])
    [1, 2]
    >>> merge([2], [1])
    [1, 2]
    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    if not lst1:
        return lst2
    elif not lst2:
        return lst1
    elif lst1[0] < lst2[0]:
        return [lst1[0]] + merge(lst1[1:], lst2)
    else:
        return [lst2[0]] + merge(lst1, lst2[1:])

Q2: Add Characters

Given two words, w1 and w2, we say w1 is a subsequence of w2 if all the letters in w1 appear in w2 in the same order (but not necessarily all together). That is, you can add letters to any position in w1 to get w2. For example, "sing" is a substring of "absorbing" and "cat" is a substring of "contrast".

Implement add_chars, which takes in w1 and w2, where w1 is a substring of w2. It should return a string containing the characters you need to add to w1 to get w2. Your solution must use recursion.

In the example above, you need to add the characters "aborb" to "sing" to get "absorbing", and you need to add "ontrs" to "cat" to get "contrast".

The letters in the string you return should be in the order you have to add them from left to right. If there are multiple characters in the w2 that could correspond to characters in w1, use the leftmost one. For example, add_words("coy", "cacophony") should return "acphon", not "caphon" because the first "c" in "coy" corresponds to the first "c" in "cacophony".

def add_chars(w1, w2):
    """
    Return a string containing the characters you need to add to w1 to get w2.

    You may assume that w1 is a subsequence of w2.

    >>> add_chars("owl", "howl")
    'h'
    >>> add_chars("want", "wanton")
    'on'
    >>> add_chars("rat", "radiate")
    'diae'
    >>> add_chars("a", "prepare")
    'prepre'
    >>> add_chars("resin", "recursion")
    'curo'
    >>> add_chars("fin", "effusion")
    'efuso'
    >>> add_chars("coy", "cacophony")
    'acphon'
    >>> from construct_check import check
    >>> check(LAB_SOURCE_FILE, 'add_chars',
    ...       ['For', 'While', 'Set', 'SetComp']) # Must use recursion
    True
    """
    "*** YOUR CODE HERE ***"

Q2: Solution

def add_chars(w1, w2):
    """
    Return a string containing the characters you need to add to w1 to get w2.

    You may assume that w1 is a subsequence of w2.

    >>> add_chars("owl", "howl")
    'h'
    >>> add_chars("want", "wanton")
    'on'
    >>> add_chars("rat", "radiate")
    'diae'
    >>> add_chars("a", "prepare")
    'prepre'
    >>> add_chars("resin", "recursion")
    'curo'
    >>> add_chars("fin", "effusion")
    'efuso'
    >>> add_chars("coy", "cacophony")
    'acphon'
    >>> from construct_check import check
    >>> check(LAB_SOURCE_FILE, 'add_chars',
    ...       ['For', 'While', 'Set', 'SetComp']) # Must use recursion
    True
    """
    "*** YOUR CODE HERE ***"
    missing_chars = ''
    if len(w1) == 0:
        return w2
    elif w1[0] == w2[0]:
        return add_chars(w1[1:], w2[1:])
    else:
        missing_chars += w2[0] + add_chars(w1, w2[1:])
        return missing_chars

Q3: Acorn Finder

The squirrels on campus need your help! There are a lot of trees on campus and the squirrels would like to know which ones contain acorns. Define the function acorn_finder, which takes in a tree and returns True if the tree contains a node with the value 'acorn' and False otherwise.

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

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

Q3: Solution

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

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

    for b in branches(t):
        is_acorn = is_acorn or acorn_finder(b)
    return is_acorn