#Skeleton file for HW2 - Winter 2020 - 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
############

# 1d
def reverse_dict_in_place(d):
    pass #replace with your code


############
# QUESTION 2
############

# 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

# 2c
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 % 4 == 0:
            #result = (_________________) % c
            #a = (_________________) % c
        #if b % 4 == 1:
            #result = (_________________) % c
            #a = (_________________) % c
        #if b % 4 == 2:
            #result = (_________________) % c
            #a = (_________________) % c
        #if b % 4 == 3:
            #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

# 3d
def sub(bin1, bin2):
    pass #replace this with your code

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

# 4a
def has_repeat1(s, k):
    pass #replace this with your code

# 4b
def has_repeat2(s, k):
    pass #replace this with your code
    
############
# QUESTION 5
############

# 5a
def sum_divisors(n):
    pass #replace this with your code

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

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

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

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

# 6d1
def check_goldbach_for_num_stats(n, primes_set):
    pass #replace this with your code

# 6d2    
def check_goldbach_stats(limit, primes_set):
    pass #replace this with your code

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

def test():
    d = {'a': 1, 'b': 2, 'c': 3, 'd': 4}
    d_ans = {1: 'a', 2: 'b', 3: 'c', 4: 'd'}

    d_id = id(d)
    reverse_dict_in_place(d)
    if d != d_ans or id(d) != d_id:
        print("error in reverse_dict_in_place()")
    
    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("10") != "1" or \
       dec("110") != "101" or \
       dec("1000") != "111" or \
       dec(dec("1001")) != "111":
        print("error in dec()")
        
    if sub("0", "0") != "0" or \
       sub("1000", "0") != "1000" or \
       sub("1000", "1000") != "0" or \
       sub("1000", "1") != "111" or \
       sub("101", "100") != "1":
        print("error in sub()")

    if not has_repeat1("ababa", 3) or \
       has_repeat1("ababa", 4) or \
       not has_repeat1("aba",1):
        print("error in has_repeat1()")

    if not has_repeat2("ababa", 3) or \
       has_repeat2("ababa", 4) or \
       not has_repeat2("aba",1):
        print("error in has_repeat2()")
                
    if sum_divisors(6) != 6 or \
       sum_divisors(4) != 3:        
        print("error in sum_divisors()")

    primes_set = parse_primes("primes.txt")
    if primes_set == None or not 104729 in primes_set or 6 in primes_set:
        print("error in parse_primes()")

    if not check_goldbach_for_num(10, {2, 3, 5, 7}):
        print("error in check_goldbach_for_num()")

    if check_goldbach_for_num(10, {2, 3}):
        print("error in check_goldbach_for_num()")

    if not check_goldbach_for_range(20, {2, 3, 5, 7, 11}):
        print("error in check_goldbach_for_range()")

    if check_goldbach_for_range(21, {2, 3, 5, 7, 11}):
        print("error in check_goldbach_for_range()")
        
    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()")