#! /usr/bin/python3

from math import sqrt

# ********************************************************
# CS 200b HW #1  DUE Monday, 9/25/2023 at 11:59 pm
#                via the submit system on the Zoo

# ********************************************************
# Name:
# Email address:
# ********************************************************

# This file may be opened in Python or run from the command line.
# Lines beginning with hash marks are comments.

# If you are asked to write a procedure, please make sure it has 
# the specified name, and the specified number and order of arguments.  
# The names of the formal arguments need not be the same
# as in the problem specification.

# For each problem, the intended inputs to your procedures
# are specified (for example, "positive integers") 
# and your procedures need not do anything reasonable 
# for other possible inputs.

# You may write auxiliary procedures in addition to
# the requested one(s) -- for each of your auxiliary 
# procedures, please include a comment explaining
# what it does, and giving an example or two.

# You may also use procedures you have written 
# elsewhere in this assignment or previous assignments.
# They only need to be defined once somewhere within this file.

# Reading: The Google Python course
# Optional: Learning Python, Python Cookbook, Essential Python

# ********************************************************
# ** problem 0 ** (1 easy point) 
# Replace the number 0 in the definition below to indicate
# the number of hours you spent doing this assignment
# Decimal numbers (eg, 6.237) are fine.  Exclude time
# spent reading.

def hours():
    return 0

# ********************************************************
# ** problem 1 ** (9 points)
# Write a procedure

# sum_digits(n)

# that takes a positive integer and returns the sum of the digits

# Examples
# sum_digits(13) => 4
# sum_digits(1000000) => 1
# sum_digits(123456789) => 45
# sum_digits(9) => 9

# ********************************************************
# Replace the pass statement with your definition
def sum_digits(n):
    pass

# ********************************************************
# ** problem 2 ** (10 points)
# Write a recursive procedure

# reduce(n)

# that takes a positive integer as input, and repeatedly
# sums the digits until the result is less than 10.
# Note: you probably want to call sum_digits from inside reduce

# You may wish to trace the recursive calls to reduce.
## see fib.py example
## THIS IS JUST FOR DEBUGGING.  Do not turn in code with trace turned on.

def trace(f):
    f.indent = 0
    def g(x):
        print('|  ' * f.indent + '|--', f.__name__, x)
        f.indent += 1
        value = f(x)
        print('|  ' * f.indent + '|--', 'return', repr(value))
        f.indent -= 1
        return value
    return g


# Examples

# reduce(123455667888) => 9
# reduce(9999) => 9
# reduce(8888) => 5
# reduce(10101010019999) => 5

# ********************************************************
def reduce(n):
    pass

# (Replace the pass statement with your procedure(s).)

# reduce = trace(reduce)

# ********************************************************
# ** problem 3 ** (10 points)
# Write a procedure

# largest_digit(n)

# which takes an integer n (base 10) and returns the largest digit in n

# Examples
# largest_digit(12345) => 5
# largest_digit(11111) => 1
# largest_digit(54321) => 5
# largest_digit(5432123456789123) => 9

# ********************************************************

# Replace the pass statement with your function.
def largest_digit(n):
    pass
    
# ********************************************************
# ** problem 4 ** (10 points)
# Write a procedure

# inflate(lst, value=1)

'''
which returns a list with all the top level numeric values in the
original list incremented by the optional value, which defaults to 1.
Numeric types include int, float, and complex.
Non-numeric values are unchanged.

 Examples

inflate([1,2,3]) => [2, 3, 4]
inflate([1]) => [2]
inflate([]) => []
inflate(["a", "b", "c", 2, 3, 4,]) => ['a', 'b', 'c', 3, 4, 5]
inflate([[1], [2], [3]]) => [[1], [2], [3]]

inflate([1,2,3], 2) => [3, 4, 5]
inflate([1,2,3], 0) => [1, 2, 3]
inflate([1,2,3], -1) => [0, 1, 2]
inflate([1,2,3], 100) => [101, 102, 103]
inflate(["a", "b", "c", 2, 3, 4,], 5) => ['a', 'b', 'c', 7, 8, 9]

inflate([1.1,2.2,3+3j], 2) => [3.1, 4.2, (5+3j)]
inflate([1.1,2.2,3+3j], 2.5) => [3.6, 4.7, (5.5+3j)]
inflate([1.1,2.2,3+3j], 2+5j) => [(3.1+5j), (4.2+5j), (5+8j)]

Also, write inflate as a list comprehension which has the same behavior as inflate.

lcinflate(lst, value=1)

 Examples

lcinflate([1,2,3]) => [2, 3, 4]
lcinflate([1]) => [2]
lcinflate([]) => []
lcinflate(["a", "b", "c", 2, 3, 4,]) => ['a', 'b', 'c', 3, 4, 5]
lcinflate([[1], [2], [3]]) => [[1], [2], [3]]

lcinflate([1,2,3], 2) => [3, 4, 5]
lcinflate([1,2,3], 0) => [1, 2, 3]
lcinflate([1,2,3], -1) => [0, 1, 2]
lcinflate([1,2,3], 100) => [101, 102, 103]
lcinflate(["a", "b", "c", 2, 3, 4,], 5) => ['a', 'b', 'c', 7, 8, 9]

lcinflate([1.1,2.2,3+3j], 2) => [3.1, 4.2, (5+3j)]
lcinflate([1.1,2.2,3+3j], 2.5) => [3.6, 4.7, (5.5+3j)]
lcinflate([1.1,2.2,3+3j], 2+5j) => [(3.1+5j), (4.2+5j), (5+8j)]

'''

# ********************************************************

def inflate(lst, value=1):
    pass

# (Replace the pass statement with your procedure(s).)

def lcinflate(lst, value=1):
    pass

# ********************************************************
# ** problem 5 ** (10 points)
# Write a procedure

# removep(lst,pred)

# that takes a list lst and returns that list minus 
# any elements that satisfy the given predicate pred.

# Examples:

# removep([1,2,3,4,5,6], lambda x: x % 2 == 0) => [1,3,5]
# removep([1,2,3,4,5,6], lambda x: x % 2) => [2,4,6]
# removep([1,2,3,4,5,6], lambda a: a > 3) => [1,2,3]
# removep([1,2,3,4,5,6], lambda a: a < 3) => [3,4,5,6]

# ********************************************************
def removep(lst, pred):
    pass
    
# Replace the pass statement with your procedure(s).

## Write the same function using a list comprehension.
def lcremovep(lst, pred):
    pass

# ********************************************************
# ** problem 6 ** (10 points)

'''

evenout(lst)

Define a Python procedure (evenout lst) that increments every
top-level item of lst that is an odd integer.

Examples: 
evenout([1,2,3,4]) => [2, 2, 4, 4]
evenout(['a','b','c']) => ['a', 'b', 'c']
evenout([1,[2],[3],[4]]) => [2, [2], [3], [4]]
evenout([]) => []
evenout(['hello','world']) => ['hello', 'world']

'''
# ********************************************************
def evenout(lst):
    pass

## write the same function using a list comprehansion
def lcevenout(lst):
    pass

# ********************************************************
# ** problem 7 ** (10 points)
# Write two procedures

'''
double_factor(factor, lst)

Define a Python procedure double_factor(factor, lst) that doubles
every top-level item of lst that is an integer multiple of factor.You
may assume the lst contains only integers.

Examples: 
double_factor(2,[1,2,3,4,5,6]) => [1, 4, 3, 8, 5, 12]
double_factor(3,[1,2,3,4,5,6]) => [1, 2, 6, 4, 5, 12]
double_factor(3,[]) => []
double_factor(100,[1,2,3,4,5,6]) => [1, 2, 3, 4, 5, 6]
double_factor(2, [-1,-2,-3,-4,-5,-6]) => [-1, -4, -3, -8, -5, -12]

'''

# ********************************************************

def double_factor(factor, l):
    pass

## Write the same function as a list comprehension.

def lcdouble_factor(factor, l):
    pass

# ********************************************************
# ** problem 8 (10 points)

'''
Write two procedures:

primes(n) which generates a list of all prime numbers less than n

prime_factors(n)  which generates a list of all prime factors of
the positive integer n.

Examples:

primes(20) => [2, 3, 5, 7, 11, 13, 17, 19]
primes(100) => [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]

prime_factors(20) => [2, 2, 5]
prime_factors(32) => [2, 2, 2, 2, 2]
prime_factors(97) => [97]
prime_factors(1000) => [2, 2, 2, 5, 5, 5]
prime_factors(30030) => [2, 3, 5, 7, 11, 13]

'''

## calulate primes below 100
noprimes = [j for i in range(2, 8) for j in range(i*2, 100, i)]
yesprimes = [x for x in range(2, 100) if x not in noprimes]

## look at sorted(noprimes)

## change [] to {} to get set
noprimeset = {j for i in range(2, 8) for j in range(i*2, 100, i)}

def primes(n):
    pass

def prime_factors(n):
    pass

# ********************************************************
# ** problem 9 (10 points)
# Write 

# power_set(lst)

# which treats the lst as a set and returns a list of all possible
# subsets

'''
Examples:

power_set([]) => [[]]
power_set([1]) => [[], [1]]
power_set([1,2]) => [[], [2], [1], [1,2]]
power_set([1,2,3]) => [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
power_set([1,2,3,4]) => 
[[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]]
power_set([2,2]) => [[], [2], [2], [2, 2]]

toppings = ['onion','peppers','bacon','sausage','mushroom']
power_set(toppings) => 

[[], ['bacon'], ['bacon', 'mushroom'], ['bacon', 'sausage'], ['bacon',
'sausage', 'mushroom'], ['mushroom'], ['onion'], ['onion', 'bacon'],
['onion', 'bacon', 'mushroom'], ['onion', 'bacon', 'sausage'],
['onion', 'bacon', 'sausage', 'mushroom'], ['onion', 'mushroom'],
['onion', 'peppers'], ['onion', 'peppers', 'bacon'], ['onion',
'peppers', 'bacon', 'mushroom'], ['onion', 'peppers', 'bacon',
'sausage'], ['onion', 'peppers', 'bacon', 'sausage', 'mushroom'],
['onion', 'peppers', 'mushroom'], ['onion', 'peppers', 'sausage'],
['onion', 'peppers', 'sausage', 'mushroom'], ['onion', 'sausage'],
['onion', 'sausage', 'mushroom'], ['peppers'], ['peppers', 'bacon'],
['peppers', 'bacon', 'mushroom'], ['peppers', 'bacon', 'sausage'],
['peppers', 'bacon', 'sausage', 'mushroom'], ['peppers', 'mushroom'],
['peppers', 'sausage'], ['peppers', 'sausage', 'mushroom'],
['sausage'], ['sausage', 'mushroom']]
'''

# ********************************************************
## it is NOT OK to use itertools module.
## 

def power_set(lst):
    pass

# ********************************************************
# ** problem 10 (10 points)

'''
Write the following procedure:

all_factors(n) which generates a list of all the factors for
the positive integer n, without duplicates.

Hint: the factors of a positive number can be obtained from the
power set of the number's prime factors.

Examples:

all_factors(20) => [1, 2, 4, 5, 10, 20]
all_factors(32) => [1, 2, 4, 8, 16, 32]
all_factors(97) => [1, 97]
all_factors(1000) => [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000]
all_factors(30030) => [1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 21, 22, 26, 30, 33, 35, 39, 42, 55, 65, 66, 70, 77, 78, 91, 105, 110, 130, 143, 154, 165, 182, 195, 210, 231, 273, 286, 330, 385, 390, 429, 455, 462, 546, 715, 770, 858, 910, 1001, 1155, 1365, 1430, 2002, 2145, 2310, 2730, 3003, 4290, 5005, 6006, 10010, 15015, 30030]

'''

# ********************************************************
# Replace the pass statement with your code

def all_factors(n):
    pass

### test function from google python course
### =======================================
# Provided simple test() function used in main() to print
# what each function returns vs. what it's supposed to return.
def test(got, expected):
    if (hasattr(expected, '__call__')):
        OK = expected(got)
    else:
        OK = (got == expected)
    if OK:
        prefix = ' OK '
    else:
        prefix = '  X '
    print ('%s got: %s expected: %s' % (prefix, repr(got), repr(expected)))


# Provided main() calls the above functions with interesting inputs,
# using test() to check if each result is correct or not.
def main():
  print ('hours')
  print('# is it greater than 0?')
  test(hours(), lambda x: x > 0)

  print ('sum_digits')
  test(sum_digits(10), 1)
  test(sum_digits(13), 4)
  test(sum_digits(1000000),1)
  test(sum_digits(123456789), 45)
  test(sum_digits(9),9)

  print
  print ('reduce')
  test(reduce(123455667888),9)
  test(reduce(9999),9)
  test(reduce(8888),5)
  test(reduce(10101010019999),5)

  print
  print ('largest_digit')
  test(largest_digit(12345),5)
  test(largest_digit(11111),1)
  test(largest_digit(54321),5)
  test(largest_digit(5432123456789123),9)

  print
  print ('inflate')
  
  test(inflate([1,2,3]), [2, 3, 4])
  test(inflate([1]), [2])
  test(inflate([]), [])
  test(inflate(["a", "b", "c", 2, 3, 4,]), ['a', 'b', 'c', 3, 4, 5])
  test(inflate([[1], [2], [3]]), [[1], [2], [3]])
            
  test(inflate([1,2,3], 2), [3, 4, 5])
  test(inflate([1,2,3], 0), [1, 2, 3])
  test(inflate([1,2,3], -1), [0, 1, 2])
  test(inflate([1,2,3], 100), [101, 102, 103])
  test(inflate(["a", "b", "c", 2, 3, 4,], 5), ['a', 'b', 'c', 7, 8, 9])

  test(inflate([1.1,2.2,3+3j], 2), [3.1, 4.2, (5+3j)])
  test(inflate([1.1,2.2,3+3j], 2.5), [3.6, 4.7, (5.5+3j)])
  test(inflate([1.1,2.2,3+3j], 2+5j), [(3.1+5j), (4.2+5j), (5+8j)])

  print ('lcinflate')
  test(lcinflate([1,2,3]), [2, 3, 4])
  test(lcinflate([1]), [2])
  test(lcinflate([]), [])
  test(lcinflate(["a", "b", "c", 2, 3, 4,]), ['a', 'b', 'c', 3, 4, 5])
  test(lcinflate([[1], [2], [3]]), [[1], [2], [3]])
            
  test(lcinflate([1,2,3], 2), [3, 4, 5])
  test(lcinflate([1,2,3], 0), [1, 2, 3])
  test(lcinflate([1,2,3], -1), [0, 1, 2])
  test(lcinflate([1,2,3], 100), [101, 102, 103])
  test(lcinflate(["a", "b", "c", 2, 3, 4,], 5), ['a', 'b', 'c', 7, 8, 9])

  test(lcinflate([1.1,2.2,3+3j], 2), [3.1, 4.2, (5+3j)])
  test(lcinflate([1.1,2.2,3+3j], 2.5), [3.6, 4.7, (5.5+3j)])
  test(lcinflate([1.1,2.2,3+3j], 2+5j), [(3.1+5j), (4.2+5j), (5+8j)])

  print
  print ('removep')
  test(removep(range(7), lambda x: x % 2 == 0),[1,3,5])
  test(removep(range(7), lambda x: x % 2),[0,2,4,6])
  test(removep(range(7), lambda x: x > 3),[0,1,2,3])
  test(removep(range(7), lambda x: x < 3),[3,4,5,6])

  print
  print ('lcremovep')
  test(lcremovep(range(7), lambda x: x % 2 == 0),[1,3,5])
  test(lcremovep(range(7), lambda x: x % 2),[0,2,4,6])
  test(lcremovep(range(7), lambda x: x > 3),[0,1,2,3])
  test(lcremovep(range(7), lambda x: x < 3),[3,4,5,6])

  print
  print ('evenout')
  test(evenout([1,2,3,4]), [2, 2, 4, 4])
  test(evenout(['a','b','c']), ['a', 'b', 'c'])
  test(evenout([1,[2],[3],[4]]), [2, [2], [3], [4]])
  test(evenout([]), [])
  test(evenout(['hello','world']), ['hello', 'world'])

  print ('lcevenout')
  test(lcevenout([1,2,3,4]), [2, 2, 4, 4])
  test(lcevenout(['a','b','c']), ['a', 'b', 'c'])
  test(lcevenout([1,[2],[3],[4]]), [2, [2], [3], [4]])
  test(lcevenout([]), [])
  test(lcevenout(['hello','world']), ['hello', 'world'])

  print
  print("double_factor")
  test(double_factor(2,[1,2,3,4,5,6]), [1, 4, 3, 8, 5, 12])
  test(double_factor(3,[1,2,3,4,5,6]), [1, 2, 6, 4, 5, 12])
  test(double_factor(3,[]), [])
  test(double_factor(100,[1,2,3,4,5,6]), [1, 2, 3, 4, 5, 6])
  test(double_factor(2, [-1,-2,-3,-4,-5,-6]), [-1, -4, -3, -8, -5, -12])

  print
  print("lcdouble_factor")
  test(lcdouble_factor(2,[1,2,3,4,5,6]), [1, 4, 3, 8, 5, 12])
  test(lcdouble_factor(3,[1,2,3,4,5,6]), [1, 2, 6, 4, 5, 12])
  test(lcdouble_factor(3,[]), [])
  test(lcdouble_factor(100,[1,2,3,4,5,6]), [1, 2, 3, 4, 5, 6])
  test(lcdouble_factor(2, [-1,-2,-3,-4,-5,-6]), [-1, -4, -3, -8, -5, -12])

  print ('primes')
  test(primes(20), [2, 3, 5, 7, 11, 13, 17, 19])
  test(primes(100), [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])


  print
  print ('prime_factors')
  test(prime_factors(20), [2, 2, 5])
  test(prime_factors(32), [2, 2, 2, 2, 2])
  test(prime_factors(97), [97])
  test(prime_factors(1000), [2, 2, 2, 5, 5, 5])
  test(prime_factors(30030), [2, 3, 5, 7, 11, 13])

  print
  print ('power_set')
  test(power_set([]), [[]])
  test(power_set([1]), [[], [1]])
  test(sorted(power_set([1,2])), 
       sorted([[], [2], [1], [1,2]]))
  test(sorted(power_set([1,2,3])), 
       sorted([[],[3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]))
  test(power_set([1,2,3,4]), 
       [[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]])
  test(power_set([2,2]), [[], [2], [2], [2, 2]])

  toppings = ['onion','peppers','bacon','sausage','mushroom']

  test(power_set(toppings),
       [[], ['bacon'], ['bacon', 'mushroom'], ['bacon', 'sausage'], ['bacon', 'sausage', 'mushroom'], ['mushroom'], ['onion'], ['onion', 'bacon'], ['onion', 'bacon', 'mushroom'], ['onion', 'bacon', 'sausage'], ['onion', 'bacon', 'sausage', 'mushroom'], ['onion', 'mushroom'], ['onion', 'peppers'], ['onion', 'peppers', 'bacon'], ['onion', 'peppers', 'bacon', 'mushroom'], ['onion', 'peppers', 'bacon', 'sausage'], ['onion', 'peppers', 'bacon', 'sausage', 'mushroom'], ['onion', 'peppers', 'mushroom'], ['onion', 'peppers', 'sausage'], ['onion', 'peppers', 'sausage', 'mushroom'], ['onion', 'sausage'], ['onion', 'sausage', 'mushroom'], ['peppers'], ['peppers', 'bacon'], ['peppers', 'bacon', 'mushroom'], ['peppers', 'bacon', 'sausage'], ['peppers', 'bacon', 'sausage', 'mushroom'], ['peppers', 'mushroom'], ['peppers', 'sausage'], ['peppers', 'sausage', 'mushroom'], ['sausage'], ['sausage', 'mushroom']])

  print
  print ('all_factors')
  test(all_factors(20), [1, 2, 4, 5, 10, 20])
  test(all_factors(32), [1, 2, 4, 8, 16, 32])
  test(all_factors(97), [1, 97])
  test(all_factors(1000), [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000])
  test(all_factors(30030), [1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 21, 22, 26, 30, 33, 35, 39, 42, 55, 65, 66, 70, 77, 78, 91, 105, 110, 130, 143, 154, 165, 182, 195, 210, 231, 273, 286, 330, 385, 390, 429, 455, 462, 546, 715, 770, 858, 910, 1001, 1155, 1365, 1430, 2002, 2145, 2310, 2730, 3003, 4290, 5005, 6006, 10010, 15015, 30030])


# Standard boilerplate to call the main() function.
if __name__ == '__main__':
  main()

# ********************************************************
# **** end of hw #1
# ********************************************************