hw7.py (plain text)


"""CS 61A HW 07
Name:
Login:
TA:
Section:
"""


from bst import *


#### Core Questions
#### Q1
def bst_gen_find(b, item, compare_fn):
    """Return True if item is in BST b and False otherwise.

    In this version, instead of using the built-in comparison operations, we
    instead use the given compare_fn to compare items in the tree against each
    other.

    >>> def weird_comparison(a, b):
    ...     if sum(a) < sum(b):
    ...         return -1
    ...     elif sum(a) > sum(b):
    ...         return 1
    ...     return 0
    ...
    >>> #Correct General BST Given above definition
    >>> test_bst = make_bst((0, 0),
    ...                     left=make_bst((-1, -3),
    ...                                   left=make_bst((-2, -1, -3)),
    ...                                   right=make_bst((-2, -1, 1))),
    ...                     right=make_bst((4,),
    ...                                    left=make_bst((1, 0, -3, 4)),
    ...                                    right=make_bst((4, 2))))
    >>> print(bst_str(test_bst))
    (0, 0)
    |
    +-(-1, -3)
    | |
    | +-(-2, -1, -3)
    | |
    | +-(-2, -1, 1)
    |
    +-(4,)
      |
      +-(1, 0, -3, 4)
      |
      +-(4, 2)
    >>> # The example below is not EXACTLY in the tree, but technically
    >>> # it is equal to another item in the sequence according to
    >>> # weird_comparison.
    >>> bst_gen_find(test_bst, (-1, -1), weird_comparison)
    True
    >>> # But this is not in the tree.
    >>> bst_gen_find(test_bst, (-1, -1, -1), weird_comparison)
    False
    """
    "*** YOUR CODE HERE ***"


def bst_gen_insert(b, item, compare_fn):
    """Insert an item into the BST b (if it is not already in the tree).

    In this version, instead of using the built-in comparison operations, we
    instead use the given compare_fn to compare items in the tree against each
    other.

    >>> def weird_comparison(a, b):
    ...     if sum(a) < sum(b):
    ...         return -1
    ...     elif sum(a) > sum(b):
    ...         return 1
    ...     return 0
    ...
    >>> # Correct general BST, given the above definition of
    >>> # a comparison function.
    >>> test_bst = make_bst((0, 0),
    ...                     left=make_bst((-1, -3),
    ...                                   left=make_bst((-2, -1, -3)),
    ...                                   right=make_bst((-2, -1, 1))),
    ...                     right=make_bst((4,),
    ...                                    left=make_bst((1, 0, -3, 4)),
    ...                                    right=make_bst((4, 2))))
    >>> print(bst_str(test_bst))
    (0, 0)
    |
    +-(-1, -3)
    | |
    | +-(-2, -1, -3)
    | |
    | +-(-2, -1, 1)
    |
    +-(4,)
      |
      +-(1, 0, -3, 4)
      |
      +-(4, 2)
    >>> test_bst = bst_gen_insert(test_bst, (-1, -1, -1), weird_comparison)
    >>> print(bst_str(test_bst))
    (0, 0)
    |
    +-(-1, -3)
    | |
    | +-(-2, -1, -3)
    | |
    | +-(-2, -1, 1)
    |   |
    |   +-(-1, -1, -1)
    |   |
    |   +-empty_bst
    |
    +-(4,)
      |
      +-(1, 0, -3, 4)
      |
      +-(4, 2)
    >>> # The item below is already "in" the tree, according to weird_comparison.
    >>> test_bst = bst_gen_insert(test_bst, (-1, -1), weird_comparison)
    >>> print(bst_str(test_bst))
    (0, 0)
    |
    +-(-1, -3)
    | |
    | +-(-2, -1, -3)
    | |
    | +-(-2, -1, 1)
    |   |
    |   +-(-1, -1, -1)
    |   |
    |   +-empty_bst
    |
    +-(4,)
      |
      +-(1, 0, -3, 4)
      |
      +-(4, 2)
    """
    if b == empty_bst:
        return make_bst(item)
    elif compare_fn(bst_datum(b), item) == 0:
        return b        # Do not insert duplicates.
    elif compare_fn(item, bst_datum(b)) == -1:
        return make_bst(bst_datum(b),
                        bst_gen_insert(bst_left(b), item, compare_fn),
                        bst_right(b))
    return make_bst(bst_datum(b),
                    bst_left(b),
                    bst_gen_insert(bst_right(b), item, compare_fn))


#### Q2
class VendingMachine(object):
    """A vending machine that vends some product for some price.
    
    >>> v = VendingMachine('iPod', 100)
    >>> v.vend()
    'Machine is out of stock.'
    >>> v.restock(2)
    'Current iPod stock: 2'
    >>> v.vend()
    'You must deposit $100 more.'
    >>> v.deposit(70)
    'Current balance: $70'
    >>> v.vend()
    'You must deposit $30 more.'
    >>> v.deposit(50)
    'Current balance: $120'
    >>> v.vend()
    'Here is your iPod and $20 change.'
    >>> v.deposit(100)
    'Current balance: $100'
    >>> v.vend()
    'Here is your iPod.'
    >>> v.deposit(150)
    'Machine is out of stock. Here is your $150.'
    """
    def __init__(self, product, price):
        "*** YOUR CODE HERE ***"

    def restock(self, count):
        """Add count more of the product to the vending machine."""
        "*** YOUR CODE HERE ***"

    def deposit(self, amt):
        """Deposit amt more money to the vending machine."""
        "*** YOUR CODE HERE ***"

    def vend(self):
        """Vend an item if there is enough money in the machine."""
        "*** YOUR CODE HERE ***"


#### Reinforcement
#### Q3
from gst import *
from random import Random
from math import sqrt


def make_random_gst(L, randoms = Random()):
    """Return a general search tree, T, containing the items of L, assuming
    it is ordered. The numbers of keys in each subtree is decided randomly
    according to randoms, an instance of random.Random.

    Do not worry about understanding this code.
    """
    if len(L) == 0:
        return empty_gst
    else:
        arity = randoms.randint(1, int(sqrt(len(L))))
        key_indices = randoms.sample(range(0, len(L)), arity)
        key_indices.sort()
        keys = tuple(L[i] for i in key_indices)
        children = (make_random_gst(L[0:key_indices[0]], randoms),) \
            + tuple(make_random_gst(L[key_indices[i]+1:key_indices[i+1]],
                                    randoms) \
                    for i in range(0, len(key_indices)-1) ) \
            + (make_random_gst(L[key_indices[-1]+1:], randoms),)
        return make_gst(keys, children)


PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
          59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
          127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
          191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
          257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
          331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
          401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
          467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557,
          563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619,
          631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
          709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787,
          797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
          877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953,
          967, 971, 977, 983, 991, 997 )


PRIME_GENERAL_TREE = make_random_gst(PRIMES)


def gst_find(g, item):
    """Return True if item is in gst g.

    >>> gst_find(PRIME_GENERAL_TREE, 5)
    True
    >>> gst_find(PRIME_GENERAL_TREE, 0)
    False
    >>> gst_find(PRIME_GENERAL_TREE, 27)
    False
    >>> gst_find(PRIME_GENERAL_TREE, 929)
    True
    >>> gst_find(PRIME_GENERAL_TREE, 989)
    False
    """
    "*** YOUR CODE HERE ***"


#### Extra for Experts
#### Q4
def bst_remove(b, item):
    """Remove an item from BST b and return the resulting tree.
    If the item was not already in the tree, return an unmodified tree.
    
    >>> test_bst = make_bst(3,
    ...                     left=make_bst(1,
    ...                                   left=make_bst(0)),
    ...                     right=make_bst(5,
    ...                                    right=make_bst(6,
    ...                                                   right=make_bst(7))))
    >>> print(bst_str(test_bst))
    3
    |
    +-1
    | |
    | +-0
    | |
    | +-empty_bst
    |
    +-5
      |
      +-empty_bst
      |
      +-6
        |
        +-empty_bst
        |
        +-7
    >>> print(bst_str(bst_remove(test_bst, 7)))
    3
    |
    +-1
    | |
    | +-0
    | |
    | +-empty_bst
    |
    +-5
      |
      +-empty_bst
      |
      +-6
    >>> print(bst_str(bst_remove(test_bst, 5)))
    3
    |
    +-1
    | |
    | +-0
    | |
    | +-empty_bst
    |
    +-6
      |
      +-empty_bst
      |
      +-7
    >>> print(bst_str(bst_remove(test_bst, 3)))
    1
    |
    +-0
    |
    +-5
      |
      +-empty_bst
      |
      +-6
        |
        +-empty_bst
        |
        +-7
    """
    "*** YOUR CODE HERE ***"