# Import all the necessary libraries numpy, math, random, time
import numpy as np                                    
import math
import random
import time
seed = np.random.seed(0)

"""
 Define parameters
 n - Problem size in terms of input variables. Change it as per the problem size
 theta,delta,m1,m2 - Parameters defined in the algorithm
"""
n = 3              
theta = 0.5                # Theta and delta parameters, feel free to change
delta = 0.1

# Expression for m1 and m2

m1 = int((1/theta**2)*math.log2(n/(delta*theta**2))) 
m2 = int((1/theta**4)*math.log2(n*m1/(delta*theta**2)))


"""
    Values of m1 and m2 are usually restricted to be m1<=100 and m2 ,= 5/(theta**2)
"""

if(m1>=100):
    m1 = 100
m2_max = math.ceil(5/(theta**2))
if(m2>=m2_max):
    m2 = m2_max

print(m1,m2)

def f_val(x):
    f = [1,1,1,-1,1,1,1,-1]
    return f[x]

"""
    -Function to generate a random binary string of size l bits
"""
def generate_binary_string(l):
    bin_string = []
    for i in range(l):
        bin_string.append(random.randint(0,1))
    
    return bin_string

def bin_to_dec(b):
    n = 0
    for i in range(len(b)):
        n = n + (2**(i))*(b[i])
    return n

def exponent(a,b):
    if a == 0:
        return 1
    elif a == 1:
        return b
    elif a % 2 == 0:
        n = exponent(a//2 , b)
        return n*n
    else:
        n = exponent(a//2, b)
        return (n*n)*b

def dot(a,b):
    length = len(a)
    norm = 0
    for i in range(length):
        norm = norm + a[i]*b[i]
        
    return norm


"""
    - SUBROUTINE Approx(alpha,k)
    - Returns an estimate of the significance of the fourier coefficient whose prefix is alpha, where length of alpha is k. 
"""
def approx(alpha, k):
    """
        - Special case: k==n; # for k==n case, there is no list of x_i s
        - Generate yij_list. This has two cases, 2**(k)<=m2 and 2**(k)>m2. We chose the length of yij to be min of either. 
        - Compute A_i by iterating of yij and beta_alpha (Recall that there is only one i in this case)
    """
    min1 = min(m1, exponent(n-k,2))
    min2 = min(m2, exponent(k,2))
    if(k==n):
        ## Write your code here for the case when k==n
        yi = []
        for j in range(min2):
            yij = generate_binary_string(n)
            yi.append(yij)
        A_i = 0
        for j in range(min2):
            # value of sum f(yij) xhi_alpha(yij)
            A_i = (f_val(bin_to_dec(yi[j])))*((-1)**(dot(alpha, yi[j]))) + A_i 
        A_i = A_i/min2 # approximated value of f_alpha(xi)
        return [A_i**2, A_i] # keeps track of the expected fourier coefficient when n==k
    else:
        """
            1. Generate xi_list. This has two cases, 2**(n-k)<=m1 and 2**(n-k)>m1. We chose the length of xi to be min of either.
            2. Generate yij_list. This has two cases, 2**(k)<=m2 and 2**(k)>m2. We chose the length of yij to be min of either.
            3. Iterate over x_i and y_ij and compute A_i and finally beta_alpha
        """
        # Part-1: Write a code to Generate random Xi string
        beta_alpha = 0
        A = []
        for i in range(min1):
            xi = generate_binary_string(n-k)
            yi = []
        # -----------------------------------------------------------------------
        # Part -2 :  Write a code to Generate random Yi string
            for j in range(min2):
                yij = generate_binary_string(k)
                yi.append(yij)
            
        #------------------------------------------------------------
        # Part 3: Iterate over xi and yj and compute Ai and beta_alpha
            A_i = 0
            for j in range(min2):
                # value of sum f(yij xi) xhi_alpha(yij)
                A_i = (f_val(bin_to_dec(xi+yi[j])))*((-1)**(dot(alpha, yi[j]))) + A_i
            A_i = A_i/min2 # value of f_alpha(xi)
            A.append(A_i)
        for i in range(min1):
            beta_alpha = beta_alpha + (A[i]**2)
        beta_alpha = beta_alpha/min1
        return [beta_alpha, beta_alpha] # keeps track of the expected fourier coefficient

"""
    SUBROUTINE Coef(alpha,k)
    Input: alpha value, k - Size of alpha
    Output: Set of binary strings corresponding to the monomials with largest fourier coefficients 
    This function is called recursively call till k==n by extending the prefix with both '0' and '1' 
    and pruned as needed (refer to the algorithm).
"""

def Coef(alpha,k, list):
    # Compute B_alpha for each value of alpha and keep those alpha values for which B_alpha> threshold
    # Write your code here
    B_alpha_list = approx(alpha, k)
    if B_alpha_list[0] >= (theta**2)/2:
        if k == n:  
            list.append([alpha, B_alpha_list[1]])  
        else:
            Coef(alpha+[0], k+1, list)   
            Coef(alpha+[1], k+1, list)
    
            

if __name__ == '__main__':
    k=1
    alpha = [0]
    coephs = []
    Coef([], 0, coephs)  # starting with 0 then we will recurse on adding new bits
    print(coephs)

# Using the alpha values and the corresponding fourier estimates, create the fourier expansion of the majority function
# You can output the expression as a string and print below
def bin_to_coefficient(lst):
    strg = ""
    flag = True
    for i in range(len(lst)):
        if lst[i] == 1:
            strg = strg + "x_" + str(len(lst)-i)
            flag = False
    if flag:
        strg = strg + '1'
        return strg
    return strg
to_print = []       
for coefficient in coephs:
    if coefficient[1] < 0:
        to_print.append('(')
        to_print.append(str(coefficient[1]))
        to_print.append(')')
    else:
        to_print.append(str(coefficient[1]))
        
    to_print.append('*')
    to_print.append(bin_to_coefficient(coefficient[0]))
    to_print.append(' + ')
for item in to_print[:-1]:
    print(item, end="")

"""
    Ex. 5: Generate a random function f
"""  
n = 5
N = 2**n
f = []
for i in range(N):
    f.append((-1)**np.random.randint(0,2))
#print(f)
#for i in range(len(f)):
#    f[i] = (-1)**np.random.randint(0,2)
print(f)
def f_val(a_int):
    a = a_int % N
    return f[a]

# Generate a random function. One example is shown below
#f = (x32 © x8 © x34 © x13) AND (x33 © x20 © x9 © x1 © x15 © x39) OR (x24 © x10 © x27 © x6 © x34)
# f = f1 and f2 or f3
n = 40

# Hardcode the f1,f2,f3 lists as 
f1_list = [32,8,34,13]
f2_list = [33,20,9,1,15,39]
f3_list = [24,10,27,6,34]
f_list = set(f1_list + f2_list + f3_list )

# OR Generate f1_list, f2_list, f3_list randomly as below

f1_l1 = 7
f2_l2 = 5
f3_l3 = 8
f4_l4 = 4
f1_list,f2_list,f3_list,f4_list = [],[],[],[]
f = []
i=0
while(i<f1_l1):
    r=random.randint(1,n)
    if r not in f1_list:
        f1_list.append(r)
        i = i+1
    else:
        pass

# Write similar code for f2_l2, f3_l3, f4_l4
f_list = set(f1_list + f2_list + f3_list + f4_list)
print(f' f1_list data is {f1_list}')
print(f' f2_list data is {f2_list}')
print(f' f3_list data is {f3_list}')
print(f' f4_list data is {f4_list}')
print(f' f_list data is {f_list}')


def count(f_bits):
    f_ = f_bits.count(1)
    if (f_%2==0):
        return 0
    else:
        return 1
    
    
def f_val(a_int):
    a = bin(a_int)[2:].zfill(n)
    f1_bits = []
    f2_bits = []
    f3_bits = []
    f4_bits = []
    for i in f1_list:
        f1_bits.append(int(a[n-i]))
    for i in f2_list:
        f2_bits.append(int(a[n-i]))
    for i in f3_list:
        f3_bits.append(int(a[n-i]))
    for i in f4_list:
        f4_bits.append(int(a[n-i]))
    #print(f1_bits)
    #print(f2_bits)
    #print(f3_bits)
    #print(f4_bits)
    f1 = count(f1_bits)
    f2 = count(f2_bits)
    f3 = count(f3_bits)
    f4 = count(f4_bits)
    f = f1 and f2 or f3

    return (-1)**f

# Write a code to compute fourier coefficients and final alpha values as explained

# Verify your end result for following 3 points by compairing it with elements present in the original function 
# 1. Check for Elements correctly retrieved
# 2. Elements retrieved but not present in the original function 
# 3. Elements present in the original function but not retrieved

# Write your code here

# Compare total execution times of both and accuracy of the KM

"""
    Ex.3 (4 variables), Ex. Ref. 1 sec. 2.3.1  page no 8
    f(x1,x2,x3,x4) = x1 AND x3 (x1 is lsb and x4 is msb, x=x4, y=x3, z=x2, w=x1)
    f = [1,1,1,1,1,-1,1,-1,1,1,1,1,1,-1,1,-1]
"""
def f_val(a_int):
    a = bin(a_int)[2:].zfill(n)
    f = int(a[1]) and int(a[3])
    return (-1)**f

"""
    Ex. 4 (40 variables), Ref. 1, sec. 3.1 page no 15
    f = (x32 © x8 © x34 © x13) AND (x33 © x20 © x9 © x1 © x15 © x39) OR (x24 © x10 © x27 © x6 © x34)
          
"""
def f_val(a_int):
    a = bin(a_int)[2:].zfill(n)
    f1 = int(a[40-32])^int(a[40-8])^int(a[40-34])^int(a[40-13])
    f2 = int(a[40-33])^int(a[40-20])^int(a[40-9])^int(a[40-39])
    f3 = int(a[40-24])^int(a[40-10])^int(a[40-27])^int(a[40-34])
    f = f1 and f2 or f3

    return (-1)**f

















