#!/usr/bin/env python
# coding: utf-8

# # Classical bits in Deutcsh Jozsa algorithm
# 
# ***

# <br>
# 
# ## Preliminarys
# 
# ***

# In[1]:


# Returning functions.
def power(e):
    """Returns a single argument function that raises the argument to e."""
    # Define the function f. It is local to the function power.
    def f(x):
        # This is f's return value. Note it uses power's e variable.
        return x**e
    # This is power's return value. It's the function f.
    # Note that in some sense f will live longer than power even though it's "local".
    return f


# In[2]:


# Call the power function, square is a function.
square = power(2)


# In[3]:


# Call square.
square(5)


# <br>
# 
# ## Constant Boolean functions
# 
# ***

# In[4]:


# A constant function.
def bitstobit(x0, x1, x2):
    return 1


# In[5]:


# Always returns 1.
bitstobit(1, 0, 1)


# In[6]:


# Always returns 1.
bitstobit(0, 0, 0)


# In[7]:


# Print all possible inputs/outputs.
print("  x0   x1   x2    f")
for x0 in [0, 1]:
    for x1 in [0, 1]:
        for x2 in [0, 1]:
            print(f"{x0:4d} {x1:4d} {x2:4d} {bitstobit(x0, x1, x2):4d}")


# <br>
# 
# ## Balanced Boolean functions
# 
# ***

# $
# 000 \rightarrow (0 \times 2^0) + (0 \times 2^1) + (0 \times 2^2) = 0 \\
# 001 \rightarrow (0 \times 2^0) + (0 \times 2^1) + (1 \times 2^2) = 1 \\
# 010 \rightarrow (0 \times 2^0) + (1 \times 2^1) + (0 \times 2^2) = 2 \\
# 011 \rightarrow (0 \times 2^0) + (1 \times 2^1) + (1 \times 2^2) = 3 \\
# 100 \rightarrow (1 \times 2^0) + (0 \times 2^1) + (0 \times 2^2) = 4 \\
# 101 \rightarrow (1 \times 2^0) + (0 \times 2^1) + (1 \times 2^2) = 5 \\
# 110 \rightarrow (1 \times 2^0) + (1 \times 2^1) + (0 \times 2^2) = 6 \\
# 111 \rightarrow (1 \times 2^0) + (1 \times 2^1) + (1 \times 2^2) = 7 \\
# $

# In[8]:


# A balanced function.
def bitstobit(x0, x1, x2):
    # Return values.
    vals = [0, 1, 0, 1, 0, 1, 0, 1]
    # Get the retun value's index in vals.
    # e.g. 010 -> (0 x 2^0) + (1 x 2^1) + (0 x 2^2)
    i = x0 * 2**0 + x1 * 2**1 + x2 * 2**2
    # Return the correct value.
    return vals[i]


# In[9]:


bitstobit(1, 0, 0)


# In[10]:


bitstobit(1, 1, 1)


# In[11]:


# Print all possible inputs/outputs.
print("  x0   x1   x2    f")
for x0 in [0, 1]:
    for x1 in [0, 1]:
        for x2 in [0, 1]:
            print(f"{x0:4d} {x1:4d} {x2:4d} {bitstobit(x0, x1, x2):4d}")


# <br>
# 
# ## All the functions
# 
# ***

# In[12]:


import itertools as it

# No of bits in input.
nobits = 2

# Generate all length four binary tuples, then transpose.
funcs = list(zip(*it.product([0,1], repeat=2**nobits)))

# Generate all possible values of two bits.
bits = list(it.product([0,1], repeat=nobits))

# Print a header.
th = [f"x{i}" for i in range(nobits)] + [f"f{i}" for i in range(2**2**nobits)]
print("   ".join([("    " + h)[-5:] for h in th] ))

# Print the functions.
for i in range(len(bits)):
    print("   ".join([f"{j:5d}" for j in bits[i]] + [f"{j:>5d}" for j in funcs[i]]))


# <br>
# 
# ## Random function
# 
# ***

# In[13]:


import random

def f_bitstobit():
    """Creates a function mapping three bits to 1.
       The function is randomly either constant or balanced."""
    
    # Randomly decide if we're balanced or constant.
    if random.random() < 0.5:
        # List of eight bits, four 0's and four 1's.
        vals = [0, 1] * 4
    else:
        # Pick 0 half the time, 1 half the time.
        if random.random() < 0.5:
            # Eight 1 bits.
            vals = [1] * 8
        else:
            # Eight 0 bits.
            vals = [0] * 8
    
    # Randiomly shuffle the values.
    random.shuffle(vals)
    
    # Construct the function. Note this is a function within a function.
    def f(x0, x1, x2):
        # Get the retun value's index in vals.
        i = x0 * 2**0 + x1 * 2**1 + x2 * 2**2
        # Return the correct value.
        return vals[i]
    
    # Return the function f. Note it will live on beyond this function.
    return f


# In[14]:


# Create the function. We don't know if its constant of balanced.
bitstobit = f_bitstobit()


# In[15]:


# Do a test run of the function.
bitstobit(1, 0, 1)


# <br>
# 
# #### Questions
# 
# 1. In the best case scenario, what is the minimum number of times we need to call `bitstobit` to determine if it is constant or balanced?
# 2. In the worst case scenario, what is the minimum number of times we need to call `bitstobit` to determine if it is constant or balanced?
# 3. If we get the same return value from four different calls to `bitsttobit`, what is the probability it is balanced?
# 
# #### Exercise 1
# 
# Write a function called `isbalanced` that takes a `bitstobit` function as an input and returns True if it is definitely balanced and False otherwise.

# In[16]:


def isbalanced(bitstobit):
    """Returns True if bitstobit is balanced, False otherwise."""
    # Make this function work here.
    return True


# In[17]:


# This is how the above function will be called.
# Create a new random bitstobit function.
bitstobit = f_bitstobit()
# Check if it's balanced.
isbalanced(bitstobit)


# In[18]:


# This should check that it works.
# Print all possible inputs/outputs.
print("  x0   x1   x2    f")
for x0 in [0, 1]:
    for x1 in [0, 1]:
        for x2 in [0, 1]:
            print(f"{x0:4d} {x1:4d} {x2:4d} {bitstobit(x0, x1, x2):4d}")


# <br>
# 
# ## General number of bits
# 
# ***

# In[19]:


def f_bitstobit(k=3):
    """Creates a function mapping k bits to 1.
       The function is randomly either constant or balanced."""
    
    # Randomly decide if we're constant or balanced.
    if random.random() < 0.5:
        # List of 2^k bits, 2^(k-1) 0's and 2^(k-1) 1's.
        vals = [0, 1] * (2**(k-1))
    else:
        # Pick 0 half the time, 1 half the time.
        if random.random() < 0.5:
            # 2^k 1's.
            vals = [1] * (2**k)
        else:
            # 2^k 0's.
            vals = [0]  * (2**k)
    
    # Shuffle the values.
    random.shuffle(vals)
    
    # Construct the function.
    def f(xs):
        # Get the retun value's index in vals.
        i = sum([(xs[i] * 2**i) for i in range(len(xs))])
        # Return the correct value.
        return vals[i]
    
    # Return f.
    return f


# In[20]:


# Number of inputs bits.
k = 4


# In[21]:


bitstobit = f_bitstobit(k)


# In[22]:


# Make sure the bits are in a list or tuple.
t = [random.choice([0,1]) for i in range(k)]
t


# In[23]:


# Example of calling bitstobit.
bitstobit(t)


# In[24]:


import itertools

print("".join([f"  x{i}" for i in range(k)]) + "   f")
for x in itertools.product([0,1], repeat=k):
    print("".join([f"{i:4d}" for i in x]) + f"   {bitstobit(x)}")


# <br>
# 
# #### Questions
# 
# 1. In the worst case, if there are 100 input bits, how many times does bitstobit have to be called to determine if the function if balanced?
# 2. How long will that take on the machine you're running this on?
# 3. How many input bits will make the number of calls required greater than the number of known atoms in the universe?
# 
# ***

# In[25]:


import timeit


# In[26]:


timeit.timeit(lambda: bitstobit([random.choice([0,1]) for i in range(k)]))


# ***
# 
# ## End