# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

import numpy as np
from itertools import product, permutations
import math


# +
# DFS
class Solution:
    def validWalkNum(self, origin, d, n, m):
        """
            Origin: list()
            d: int
            n: int
            m: int
        """
        # self.res = 0
        
        self.m_ = dict() # (point, leftsteps): Num of ways
            
        def backPropogation(curPos, d, n, leftStep):
            if leftStep == 0:
                return 1
            
            # if in memory
            if (str(curPos), leftStep) in self.m_:
                return self.m_[(str(curPos), leftStep)]
            
            res = 0
            for i in range(d):
                if curPos[i] == 0:
                    nextPos = curPos[:]
                    nextPos[i] += 1
                    res1 = backPropogation(nextPos, d, n, leftStep - 1)
                    self.m_[(str(nextPos), leftStep - 1)] = res1
                    res += res1
                    
                elif curPos[i] == n - 1:
                    nextPos = curPos[:]
                    nextPos[i] -= 1
                    res1 = backPropogation(nextPos, d, n, leftStep - 1)
                    self.m_[(str(nextPos), leftStep - 1)] = res1
                    res += res1
                    
                else:
                    nextPos1 = curPos[:]
                    nextPos1[i] -= 1
                    res1 = backPropogation(nextPos1, d, n, leftStep - 1)
                    self.m_[(str(nextPos1), leftStep - 1)] = res1
                    
                    nextPos2 = curPos[:]
                    nextPos2[i] += 1
                    res2 = backPropogation(nextPos2, d, n, leftStep - 1)
                    self.m_[(str(nextPos2), leftStep - 1)] = res2
                    
                    res += (res1 + res2)
            
            self.m_[(str(curPos), leftStep)] = res
            
            
            return res
        
        res = backPropogation(origin, d, n, m)
        return res

sol = Solution()


# -

# # Q1.1

# +
# Q1.1 and Q2.1: Consider the case where d=4, n=10, and m=10.
# How many valid walks start from the corner (0, 0, 0, 0)?

d = 4   # 4, 8
n = 10  # 10, 12
m = 10  # 10, 12
origin = [0] * d 

resQ11 = sol.validWalkNum(origin, d, n, m)

print(f"How many valid walks start from the corner {origin}?")
print("Answer:", resQ11)
# -

# # Q1.2

# +
# Q1.2: Consider the case where d=4, n=10, and m=10.
# Consider the count of valid walks associated with each possible starting position. What is the ratio of the highest count of valid walks to smallest count of valid walks?

dictQ12 = dict()

for position in product(range(n), repeat=d):
    
    position = list(position)
    if str(position) in dictQ12:
        continue
    numWays = sol.validWalkNum(position, d, n, m)
    dictQ12[str(position)] = numWays 
    
    
    # Other Symmetric Positions
    for newPos in product([position[0], n - 1 - position[0]], [position[1], n - 1 - position[1]],
                          [position[2], n - 1 - position[2]], [position[3], n - 1 - position[3]]):
        # newPos is a list
        for newPos2 in list(permutations(newPos)):
            # newPos2 is a tuple
            newPos2 = list(newPos2)
            if str(newPos2) in dictQ12:
                continue
            dictQ12[str(newPos2)] = numWays


            
values = list(dictQ12.values())

print("What is the ratio of the highest count of valid walks to smallest count of valid walks?")
print(max(values)/min(values))

# -

# # Q1.3

# +
# Q1.3 Consider the case where d=4, n=10, and m=10.
# Consider the count of valid walks associated with each possible starting position. 
# What is the ratio of the standard deviation of the number of valid walks to the mean of the number of valid walks?

print("What is the ratio of the standard deviation of the number of valid walks to the mean\
        of the number of valid walks?")
print(np.std(values)/np.mean(values))
# -

# # Q2.1

# +
# Q1.1 and Q2.1: Consider the case where d=4, n=10, and m=10.
# How many valid walks start from the corner (0, 0, 0, 0)?

d = 8   # 4, 8
n = 12  # 10, 12
m = 12  # 10, 12
origin = [0] * d 

resQ11 = sol.validWalkNum(origin, d, n, m)

print(f"How many valid walks start from the corner {origin}?")
print("Answer:", resQ11)
# -

# # Q2.2

# +
# Q2.2: Consider the case where d=8, n=12, and m=12.
# Consider the count of valid walks associated with each possible starting position. What is the ratio of the highest count of valid walks to smallest count of valid walks?
# Generate unique points

digitMax = n//2 - 1
uniqPoints = [[0]*d]
cur = [0] * d
while cur != [digitMax] * d:
    if cur[-1] < digitMax:
        cur[-1] += 1
        uniqPoints.append(cur[:])
    else:
        for pivot in reversed(range(d)):
            # print(pivot)
            # print(cur)
            if cur[pivot] < digitMax:
                cur[pivot] += 1
                cur[pivot+1:] = [cur[pivot]] * (d - pivot - 1)
                uniqPoints.append(cur[:])
                break
                
print(len(uniqPoints))  # list of lists


# +
# Each unique points can generate how many symmetry points
def removeDupUpToPerm(input):
    """
    input: list of tuples, each tuple is d dimensional coordinate in N-D Space
    """
    return set(tuple(sorted(x)) for x in input) 

uniquePointToNumSymPoints = dict()

for uniqPoint in uniqPoints:
    # print(uniqPoint)
    
    # Step 1: generate symmetry points on each axis 

    allSymPoints = set()
    symmetryPoints = list(product([uniqPoint[0], n - 1 - uniqPoint[0]], [uniqPoint[1], n - 1 - uniqPoint[1]],
                          [uniqPoint[2], n - 1 - uniqPoint[2]], [uniqPoint[3], n - 1 - uniqPoint[3]],
                          [uniqPoint[4], n - 1 - uniqPoint[4]], [uniqPoint[5], n - 1 - uniqPoint[5]], 
                          [uniqPoint[6], n - 1 - uniqPoint[6]], [uniqPoint[7], n - 1 - uniqPoint[7]]))
    #print(symmetryPoints)  # list of tuple
    
    # Step 1.1: remove duplicates up to coordinate permutation
    # e.g. input = [(0,0,2), (0,4,2), (4,0,2), (4,4,2), (4,0,2), (0,4,2), (4,4,2)] 
    #      output: {(0, 2, 4), (0, 0, 2), (2, 4, 4)}
    symmetryPoints = removeDupUpToPerm(symmetryPoints)  # set of tuple
    
    # print("after remove")
    # print(symmetryPoints)
    
    # Step 2: for each symmetry points, further compute how many symmetry points it can generate
    # e.g. (0,0,2) has 3, they are (0,0,2), (0,2,0), (2,0,0)
    #      formula is 3!/2!
    # python: np.unique((1,1,2,2,3,3,3,4),return_counts=True), return (array([1, 2, 3, 4]), array([2, 2, 3, 1]))
    num = 0
    for symmetryPoint in symmetryPoints:
        _, denominator = np.unique(symmetryPoint, return_counts=True)
        num += math.factorial(d) / np.prod([math.factorial(i) for i in denominator])
        # print(num)
    uniquePointToNumSymPoints[tuple(uniqPoint)] = int(num)

print(uniquePointToNumSymPoints) # dict: {tuple: int}

# +
# # Single Core: 
# uniquePointToWays = dict()
# for i, uniqPoint in enumerate(uniqPoints):
#     print("Finish {:.2%}".format(i/len(uniqPoints)))
#     uniquePointToWays[tuple(uniqPoint)] = sol.validWalkNum(uniqPoint, d, n, m)
    
# # ###########################################
# Use All 6 cores
from multiprocessing import Process, Manager
import multiprocessing

def f(d, uniqPoints):
    for i, uniqPoint in enumerate(uniqPoints):
        # print(i, uniqPoint)
        print(f"{multiprocessing.current_process()} Finish {i/len(uniqPoints):.2%}")
        uniquePointToWays[tuple(uniqPoint)] = sol.validWalkNum(uniqPoint, d, n, m)


manager = Manager()

uniquePointToWays = manager.dict()

c1, c2, c3, c4, c5 = len(uniqPoints) // 6, 2*len(uniqPoints) // 6, 3* len(uniqPoints) // 6, \
                            4* len(uniqPoints) // 6, 5* len(uniqPoints) // 6 

p1 = Process(target=f, args=(d, uniqPoints[:c1]))
p2 = Process(target=f, args=(d, uniqPoints[c1:c2]))
p3 = Process(target=f, args=(d, uniqPoints[c2:c3]))
p4 = Process(target=f, args=(d, uniqPoints[c3:c4]))
p5 = Process(target=f, args=(d, uniqPoints[c4:c5]))
p6 = Process(target=f, args=(d, uniqPoints[c5:]))

p1.start()
p2.start()
p3.start()
p4.start()
p5.start()
p6.start()

p1.join()
p2.join()
p3.join()
p4.join()
p5.join()
p6.join()


resQ22 = []
for uniqPoint in uniqPoints:
    resQ22.append([uniquePointToWays[tuple(uniqPoint)]] * uniquePointToNumSymPoints[tuple(uniqPoint)])
    
print("What is the ratio of the standard deviation of the number of valid walks to the mean\
        of the number of valid walks?")
print(np.std(resQ22)/np.mean(resQ22))

# +
import pickle
file = open('res.pickle', 'rb')

# dump information to that file
data = pickle.load(file)
# close the file
file.close()

print(12**8)
print(sum(data.values()))

Q_sum = 0
for ways, symPoints in data.items():
    Q_sum += ways * symPoints

Q_mean = Q_sum/sum(data.values())
print("Mean no. of ways is", Q_mean)

up = 0

for ways, symPoints in data.items():
    up += np.abs(ways - Q_mean) **2 * symPoints

Q_std = np.sqrt(up/sum(data.values()))
print("Std no. of ways is", Q_std)

print(Q_std/Q_mean)
    


# -

# # Q2.3

# +
# Q2.3 Consider the case where d=8, n=12, and m=12.
# Consider the count of valid walks associated with each possible starting position. 
# What is the ratio of the standard deviation of the number of valid walks to the mean of the number of valid walks?
print("What is the ratio of the highest count of valid walks to smallest count of valid walks?")

up = sol.validWalkNum([5,5,5,5,5,5,5,5], d, n, m)
down = sol.validWalkNum([0,0,0,0,0,0,0,0], d, n, m)

print("max is", up)
print("min is", down)
print("ratio is", up/down)

# -













# +
data = (1, 2, 3, [[1,2,3],[4,5,6]], ['a','b','c'])
with open('data.pickle', 'wb') as f:
    pickle.dump(data, f)
    
infile = open("file.pkl", "rb")
tmp = pickle.load(infile)
infile.close()

# +
import numpy as np

a = np.array([[1,2,3,4,5,6,4,2,4,5]])
print(np.std(a))
print(np.sqrt(np.mean(abs(a - a.mean())**2)))
# -

a = {1:2, 2:3, 3:4}
b = {1:2, 2:3, 3:4}

np.inner(list(a.values()), list(b.values()))



StarcoderdataJupyterScriptsDedupFiltered