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


from functools import reduce


def str_interval(x):
    """Return a string representation of interval x.

    >>> str_interval(make_interval(-1, 2))
    '-1 to 2'
    """
    return '{0} to {1}'.format(lower_bound(x), upper_bound(x))


def add_interval(x, y):
    """Return an interval that contains the sum of any value in interval x and
    any value in interval y.

    >>> str_interval(add_interval(make_interval(-1, 2), make_interval(4, 8)))
    '3 to 10'
    """
    lower = lower_bound(x) + lower_bound(y)
    upper = upper_bound(x) + upper_bound(y)
    return make_interval(lower, upper)


def mul_interval(x, y):
    """Return the interval that contains the product of any value in x and any
    value in y.

    >>> str_interval(mul_interval(make_interval(-1, 2), make_interval(4, 8)))
    '-8 to 16'
    """
    p1 = lower_bound(x) * lower_bound(y)
    p2 = lower_bound(x) * upper_bound(y)
    p3 = upper_bound(x) * lower_bound(y)
    p4 = upper_bound(x) * upper_bound(y)
    return make_interval(min(p1, p2, p3, p4), max(p1, p2, p3, p4))


#### Q1
def make_interval(a, b):
    """Construct an interval ADT, spanning from a to b."""
    "*** YOUR CODE HERE ***"


def lower_bound(x):
    """Return the lower bound of the interval x."""
    "*** YOUR CODE HERE ***"


def upper_bound(x):
    """Return the upper bound of the interval x."""
    "*** YOUR CODE HERE ***"


#### Q2
def sum_intervals(seq):
    """Returns the sum of all of intervals in the sequence seq.

    >>> a = make_interval(-1, 2)
    >>> b = make_interval(-4, 3)
    >>> c = make_interval(-4, -3)
    >>> str_interval(sum_intervals((a, b, c)))
    '-9 to 2'
    """
    "*** YOUR CODE HERE ***"


#### Q3
def div_interval(x, y):
    """Return the interval that contains the quotient of any value in
    x divided by any value in y.

    Division is implemented as the multiplication of x by the reciprocal
    of y.

    >>> str_interval(div_interval(make_interval(-1, 2), make_interval(4, 8)))
    '-0.25 to 0.5'
    """
    "*** YOUR CODE HERE ***"
    reciprocal_y = make_interval(1/upper_bound(y), 1/lower_bound(y))
    return mul_interval(x, reciprocal_y)


#### Q4
def sub_interval(x, y):
    """Return the interval that contains the difference of any value in x
    minus any value in y.

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


#### Q5
def make_center_width(c, w):
    """Construct an interval from center and width."""
    return make_interval(c - w, c + w)


def center(x):
    """Return the center of interval x."""
    return (upper_bound(x) + lower_bound(x)) / 2


def width(x):
    """Return the width of interval x."""
    return (upper_bound(x) - lower_bound(x)) / 2


def make_center_percent(c, p):
    """Construct an interval from center and percentage tolerance.

    Percentage is given where 100 would mean 100% of tolerance.
    
    >>> str_interval(make_center_percent(3, 50))
    '1.5 to 4.5'
    >>> str_interval(make_center_percent(3, 100))
    '0.0 to 6.0'
    """
    "*** YOUR CODE HERE ***"


def percent(x):
    """Return the percentage tolerance of the interval x."""
    "*** YOUR CODE HERE ***"


#### Q6
def quadratic(x, a, b, c):
    """Return the interval of all results f(t) where t is a value from the
    interval x and f(t) = a * t * t + b * t + c.

    This is the less accurate version which treats each instance of t as a
    different value from the interval.  See the extra for experts question for
    exploring why this is not _really_ correct and to write a more precise
    version.

    >>> str_interval(quadratic(make_interval(0, 2), -2, 3, -1))
    '-9 to 5'
    >>> str_interval(quadratic(make_interval(1, 3), 2, -3, 1))
    '-6 to 16'
    """
    "*** YOUR CODE HERE ***"


#### Q7
def one(n):
    return n


one_running_time = "Theta(YOUR ANSWER HERE)"


def two(n):
    if n > 10 or n < 0:
        return n
    return two(n+1)


two_running_time = "Theta(YOUR ANSWER HERE)"


def three(n):
    if n <= 0:
        return 0
    elif n % 2 == 0:
        return 2 + three(n/2)
    else:
        return 1 + three(n-1)


three_running_time = "Theta(YOUR ANSWER HERE)"


def four(n):
    if n == 0:
        return 0
    else:
        return two(n) + four(n-1)


four_running_time = "Theta(YOUR ANSWER HERE)"


def five(n):
    if n == 0:
        return 0
    else:
        return three(n) + five(n-1)

five_running_time = "Theta(YOUR ANSWER HERE)"


def six(n):
    total = 0
    while n >= 0:
        total = total + four(n)
        n = n-1
    return total


six_running_time = "Theta(YOUR ANSWER HERE)"


#### Extra for Experts
#### Q8
def par1(r1, r2):
    return div_interval(mul_interval(r1, r2), add_interval(r1, r2))

def par2(r1, r2):
    one = make_interval(1, 1)
    rep_r1 = div_interval(one, r1)
    rep_r2 = div_interval(one, r2)
    return div_interval(one, add_interval(rep_r1, rep_r2))


def demonstrate_lem_prob():
    """Returns False when comparing the two different versions of par Lem wrote
    using intervals int1 and int2.

    You are encouraged to try other expressions to get better insight as to
    what's going on.

    >>> demonstrate_lem_prob()
    False
    """
    def eq_interval(x, y):
        """Checks if the intervals x and y are the same."""
        lower_same = lower_bound(x) == lower_bound(y)
        upper_same = upper_bound(x) == upper_bound(y)
        return lower_same and upper_same
    int1, int2 = "*** YOUR CODE", " HERE ***"
    return eq_interval(par1(int1, int2), par2(int1, int2))


#### Q9
explanation = """*** EXPLAIN HERE***"""


#### Q10
def accurate_quadratic(x, a, b, c):
    """Calculate the interval of values that can result from applying the
    quadratic function f(t) = a * t * t + b * t + c to any value from the
    interval x.

    >>> str_interval(accurate_quadratic(make_interval(0, 2), -2, 3, -1))
    '-3 to 0.125'
    >>> str_interval(accurate_quadratic(make_interval(1, 3), 2, -3, 1))
    '0 to 10'
    """
    "*** YOUR CODE HERE ***"


#### Q11
def polynomial(x, c):
    """Return the interval that is the range the polynomial defined by
    coefficients c, for domain interval x.

    >>> str_interval(polynomial(make_interval(0, 2), (-1, 2, -2)))
    '-5 to -0.5'
    >>> str_interval(polynomial(make_interval(1, 3), (1, -3, 2)))
    '0 to 10'
    >>> r = polynomial(make_interval(0.5, 2.25), (10, 24, -6, -8, 3))
    >>> round(lower_bound(r), 5)
    18.0
    >>> round(upper_bound(r), 5)
    23.0
    """
    "*** YOUR CODE HERE ***"