#Skeleton file for HW2 - Fall 2019 - extended intro to CS

#Add your implementation to this file

#you may NOT change the signature of the existing functions.

#Change the name of the file to include your ID number (hw2_ID.py).


import time

############
# QUESTION 1
############

# 1c
def reverse_dict(d):
    pass #replace with 1 line of code: return {__ for x in d}

# 1e
##def build_dict(keys, vals):
##    d = {}
##    for key in keys:
##        for val in vals:
##            if keys.index(key) == vals.index(val):
##                d[key] = val
##    return d
##
##def build_dict2(keys, vals):
##    d = {}
##    for i in range(len(keys)):
##        d[keys[i]] = vals[i]
##    return d


##keys = [i for i in range(1000)]
##vals = [i for i in range(1000)]
##
##start = time.time()
##build_dict(keys, vals)
##end = time.time()
##print("build_dict time: ", end - start)
##
##start = time.time()
##build_dict2(keys, vals)
##end = time.time()
##print("build_dict2 time: ", end - start)


############
# QUESTION 2b
############

def power_new(a,b):
    """ computes a**b using iterated squaring """
    result = 1
    b_bin = bin(b)[2:]
    reverse_b_bin = b_bin[: :-1]
    for bit in reverse_b_bin: 
        pass #replace these three "pass" commands with three lines
        pass
        pass
    return result

def modpower_new(a, b, c):
    """ computes a**b mod c using iterated squaring
        assumes b is nonnegative integer  """

    pass #remove this command, and uncomment the code below 

    #result = 1 # a**0
    #while b > 0:
        #if b % 3 == 0:
            #result = (_________________) % c
            #a = (_________________) % c
        #if b % 3 == 1:
            #result = (_________________) % c
            #a = (_________________) % c
        #if b % 3 == 2:
            #result = (_________________) % c
            #a = (_________________) % c
        #b = b // ___________________
    #return result


############
# QUESTION 3
############

#3b
def inc(binary):
    pass #replace this with your code

#3c
def dec(binary):
    pass #replace this with your code

############
# QUESTION 4
############

def ternary_search(key,lst):
    pass #replace this with your code


############
# QUESTION 5
############

#5a
def parse_primes(filename):
    pass #replace this with your code

#5b
def check_goldbach_for_num(n, primes_set):
    pass #replace this with your code

#5c
def check_goldbach_for_range(limit, primes_set):
    pass #replace this with your code

#5d
def check_goldbach_for_num_stats(n, primes_set):
    pass #replace this with your code
    
def check_goldbach_stats(limit, primes_set):
    pass #replace this with your code



############
# QUESTION 6
############

#6a
def square_digit_chain(n):
    pass #replace this with your code

#6b
def count_nums_89(limit):
    pass #replace this with your code

#6d
def pow_digit_chain(n, p):
    pass #replace this with your code

#6e
def count_ends(limit, p):
    pass #replace this with your code

#6f

def swap(lst, i, j):
    tmp = lst[i]
    lst[i] = lst[j]
    lst[j] = tmp

def selection_sort(lst):
    ''' sort lst (in-place) '''
    n = len(lst)
    for i in range(n):
        m_index = i
        for j in range(i+1,n):
            if lst[m_index] > lst[j]:
                m_index = j
        swap(lst, i, m_index)
    return None

def sorted_ends(limit, p):
    d = count_ends(limit, p)
    lst = [(key, d[key]) for key in d]
    #fill in the next line
    #lst_to_sort = ______________________________
    selection_sort(lst_to_sort)
    #fill in the next line
    #return [_____________ for (a, b) in lst_to_sort]


########
# Tester
########

def test():
    d = {'a': 1, 'b': 2, 'c': 3, 'd': 4}
    d_ans = {1: 'a', 2: 'b', 3: 'c', 4: 'd'}
    if reverse_dict(d) != d_ans:
        print("error in reverse_dict()")

    if power_new(2, 3) != 8:
        print("error in power_new()")

    if modpower_new(3, 4, 5) != pow(3, 4, 5) or \
       modpower_new(5, 4, 2) != pow(5, 4, 2):
        print("error in modpower_new()")
        
    if inc("0") != "1" or \
       inc("1") != "10" or \
       inc("101") != "110" or \
       inc("111") != "1000" or \
       inc(inc("111")) != "1001":
        print("error in inc()")

    if dec("1") != "0" or \
       dec("101") != "100" or \
       dec("100") != "11" or \
       dec(dec("11")) != "1":
        print("error in dec()")

    lst = [1,2,3,4,5]
    if ternary_search(1,lst) != 0 or \
       ternary_search(3,lst) != 2 or \
       ternary_search(1,[1]) != 0 or \
       ternary_search(0,[1]) != None:
        print("error in ternary_search()")


    primes_set = parse_primes("primes.txt")
    if primes_set == None:
        print("error in parse_primes()")

    if check_goldbach_for_num_stats(20, primes_set) != 2:
        print("error in check_goldbach_for_num_stats()")

    if check_goldbach_for_num_stats(10, primes_set) != 2:
        print("error in check_goldbach_for_num_stats()")

    if check_goldbach_stats(11, primes_set) != {1: 3, 2: 1}:
        print("error in check_goldbach_stats()")

    
    
    if square_digit_chain(44) != 1 or \
       square_digit_chain(85) != 89 or \
       square_digit_chain(135) != 89:
        print("error in square_digit_chain()")

    if count_nums_89(50) != 38:
        print("error in count_nums_89()")

    if pow_digit_chain(50, 7) != 5221343 or \
       pow_digit_chain(50, 3) != 371:
        print("error in pow_digit_chain()")

    if count_ends(79, 3) != {1: 2, 55: 1, 133: 9, 153: 26, 217: 3, 370: 10, 371: 23, 407: 3, 1459: 1} or \
       count_ends(44, 3) != {1: 2, 133: 6, 153: 14, 217: 2, 370: 5, 371: 14}:
        print("error in count_ends()")

    if sorted_ends(79, 3) != [55, 1459, 1, 217, 407, 133, 370, 371, 153] or \
       sorted_ends(44, 3) != [1, 217, 370, 133, 153, 371]:
        print("error in sorted_ends()")

    
test()