# lab08.py
# YOUR NAME AND NETID HERE
# THE DATE COMPLETED HERE
"""Lab 8: Recursive Functions"""

# IMPLEMENT ALL OF THESE FUNCTIONS

def numberof(thelist, v):
    """Returns: number of times v occurs in thelist.
    
    Precondition: thelist is a list of ints
                  v is an int"""
    return 0 # Stub return.  Replace this.


def replace(thelist,a,b):
    """Returns: a COPY of thelist but with all occurrences of a replaced by b. 
    
        Example: replace([1,2,3,1], 1, 4) = [4,2,3,4].
    
        Tip: operator + can concantenate lists, like this:
            [1,2,3] + [6,5,4] # this is the same as [1,2,3,6,5,4]
        
            Making a copy of a list is this easy:
            lcopy = l[:]
    
    Precondition: thelist is a list of ints
                  a and b are ints"""
    return [] # Stub return.  Replace this.


def remove_dups(thelist):
    """Returns: a COPY of thelist with adjacent duplicates removed.
    
        Example: for thelist = [1,2,2,3,3,3,4,5,1,1,1],
        the answer is [1,2,3,4,5,1]
    
    Precondition: thelist is a list of ints"""
    return [] # Stub return.  Replace this.


def print_nested_list(input):
    """Prints out every single string in input, one per line.
    
    Example:
    print_nested_list(['this', ['is', 'a'], 'list', ['list', 'list' ]])
    should result in the following printout
       this
       is
       a
       list
       list
       list
    
    Precondition: input is a string, or a potentially nested
    non-empty list of strings. no component list can be empty
        
    Note : it's OK to remove some preconditions and solve a more general
    case if you want. For example, you can allow empty inputs - '[]'."""
    pass


# OPTIONAL EXERCISES

def number_not(thelist, v):
    """Returns: number of elements in thelist that are NOT v.
    
    Precondition: thelist is a list of ints
                  v is an int"""
    return 0 # Stub return.  Replace this.


def remove_first(thelist, v):
    """Returns: a COPY of thelist but with the FIRST occurrence of v
    removed (if present).

    Note: This can be done easily using index. Don't do that.
    Do it recursively.
    
    Precondition: thelist is a list of ints
                  v is an int"""
    return [] # Stub return.  Replace this.


def reverse1(thelist):
    """Returns: a COPY of thelist that is the reverse of the list.
    
        Example: the reverse of [1,2,3] is [3,2,1]
    
    Do not use the method reverse().  That alters the list thelist.
    Instead, implement this function with the following idea:
    The reverse of thelist with at least one element is the
    reverse of thelist[1:] catenated with (a list with the element)
    thelist[0].

    Precondition: thelist is a list of ints"""
    return [] # Stub return.  Replace this.


def reverse2(thelist):
    """Returns: a COPY of thelist that is the reverse of the list.
    
        Example: the reverse of [1,2,3] is [3,2,1]
    
    Do not use the method reverse().  That alters the list thelist.
    Instead, implement this method with the following idea:
    To reverse a list thelist with at least two elements, switch
    the first and last ones and reverse the middle.

    Precondition: thelist is a list of ints"""
    return [] # Stub return.  Replace this.


def sum_list(thelist):
    """Returns: the sum of the integers in list l.
    
        Example: sum_list([34]) is 34
        Example: sum_list([7,34,1,2,2]) is 46
    
    Precondition: thelist is a list of ints"""
    return 0 # Stub return.  Replace this.


def sum_to(n):
    """Returns: sum of numbers 1 to n.
    
        Example: sum_to(3) = 1+2+3 = 6, 
        Example: sum_to(5) = 1+2+3+4+5 = 15
    
    Precondition: n >= 1 is an int."""
    return 0 # Stub return.  Replace this.


def num_digits(n):
    """Yields: number of the digits in the decimal representation of n.

        Example: num_digits(0) = 1
        Example: num_digits(3) = 1
        Example: num_digits(34) = 2
        Example: num_digits(1356) = 4
    
    Precondition: n >= 0 is an int"""
    return 0 # Stub return.  Replace this.


def sum_digits(n):
    """Returns: sum of the digits in the decimal representation of n.
    
        Example: sum_digits(0) = 0
        Example: sum_digits(3) = 3
        Example: sum_digits(34) = 7
        Example: sum_digits(345) = 12
    
    Precondition: n >= 0 is an int."""
    return 0 # Stub return.  Replace this.


def number2(n):
    """Returns: the number of 2's in the decimal representation of n.
    
        Example: number2(0) = 0
        Example: number2(2) = 1
        Example: number2(234252) = 3
        
    Precondition: n >= 0 is an int."""
    return 0 # Stub return.  Replace this.


def into(n, c):
    """Returns: The number of times that c divides n,
    
        Example: into(5,3) = 0 because 3 does not divide 5.
        Example: into(3*3*3*3*7,3) = 4.
    
    Precondition: n >= 1 and c > 1 are ints."""
    return 0 # Stub return.  Replace this.


def exp(b, c):
    """Returns: b ** c, i.e. b multiplied by itself c times.
    
    Also called b "to the power" c.
    Hints: b ** 0 = 1.
    if c is even, b**c == (b*b) ** (c/2)
    if c > 0, b**c =  b * (b ** (c-1)).
    
    Precondition: c >= 0 is an int"""
    return 0 # Stub return.  Replace this.


def embed(input):
    """Returns: depth of embedding in input.
    
    This function is covered in the Lecture 12.
        
    Precondition: input is a string, or a potentially nested
    list of strings. no component list can be empty"""
    pass


def sum_nested_list(input):
    """Returns: Summation of all the number in the nested list input
    
    Example:
    sum_nested_list([0, [2, 5], 8, [-10, -1]]) should be  4
    
    Precondition: input is an integer, or a potentially nested
    non-empty list of integers. no component list can be empty"""
    pass

def flatten_nested_list(input):
    """Flatten every items in the input into a list with depth 1.
    
    Example:
    flatten_nested_list(['this', ['is', 'a'], 'list', ['list', 'list' ]])
    should be ['this', 'is', 'a', 'list', 'list', 'list']
    
    Precondition: input is a string, or a potentially nested
    non-empty list of strings. no component list can be empty"""
    pass


def max_nested_list(input):
    """Returns: The item with the largest value in the nested list input
    
    Example:
    sum_nested_list([0, [2, 5], 8, [-10, -1]]) should be  8
    
    Precondition: input is an integer, or a potentially nested
    non-empty list of integers. no component list can be empty"""
    pass