import math, pickle

#A(n) is the sequence of nimbers for n linked squares at the bottom vertex
#B(n) is the sequence of nimbers for n linked squares at the bottom vertex with a P(3) tail at the end
#C(n) is the sequence of nimbers for n linked squares at the bottom vertex with P(3) tails at both ends

def mex(list):
    m=0
    while m in list:
        m+=1
    return(m)


def A(n):
    global cFourNimbersDict, bFourNimbersDict, aFourNimbersDict

    if n in aFourNimbersDict:
        return aFourNimbersDict[n]

    subgraphs = [A(n - 1), B(n - 3), B(n - 2) ^ 1]

    for i in range(n - 2):
        subgraphs.append(A(n - 2 - i) ^ B(i))

    for i in range(math.floor((n - 4) / 2) + 1):
        subgraphs.append(B(n - 4 - i) ^ B(i))

    aN = (mex(subgraphs))
    aFourNimbersDict[n] = aN
    return aN



def B(n):
    global cFourNimbersDict, bFourNimbersDict, aFourNimbersDict

    if n in bFourNimbersDict:
        return bFourNimbersDict[n]

    subgraphs = [A(n), A(n - 1)^1, B(n - 1), B(n - 2), C(n - 2)^1, C(n - 3), A(1)^C(n - 3), B(n - 3)^1, B(n - 4)^C(0)]

    for i in range(n - 3):
        subgraphs.append(A(n - 2 - i) ^ C(i))

    for i in range(n - 1 - math.floor((n - 1)/(2))):
        subgraphs.append(B(n - 2 - i) ^ B(i))

    for i in range(n - 4):
        subgraphs.append(B(i)^C(n - 4 - i))

    bN =  (mex(subgraphs))
    bFourNimbersDict[n] = bN
    return bN

def C(n):
    global cFourNimbersDict, bFourNimbersDict, aFourNimbersDict
    if n in cFourNimbersDict:
        return cFourNimbersDict[n]

    subgraphs=[C(n - 2), B(n - 1)^1, B(n), C(n - 1)]

    for i in range(n - 1 - math.floor(n/2)):
        subgraphs.append(B(n-2-i)^C(i))

    for i in range(math.floor((n-2)/2)+1):
        subgraphs.append(B(i)^C(n - 2 - i))

    for i in range(n - 2 - math.floor((n - 3)/2)): #should it be a 2 here?
        subgraphs.append(C(n - 3 - i)^C(i - 1))

    cN = (mex(subgraphs))
    cFourNimbersDict[n] = cN
    return cN


# you can use the following 6 functions to implement a pickle file

def dumpcFourDict(cFourNimbers):
    pickle_out = open("cFourNimbers.pickle", "wb")
    pickle.dump(cFourNimbers, pickle_out)
    pickle_out.close()


def getcFourDict():
    pickle_in = open("cFourNimbers.pickle", "rb")
    ret = pickle.load( pickle_in )
    pickle_in.close()
    return ret

def dumpaFourDict(aFourNimbers):
    pickle_out = open("aFourNimbers.pickle", "wb")
    pickle.dump(aFourNimbers, pickle_out)
    pickle_out.close()


def getaFourDict():
    pickle_in = open("aFourNimbers.pickle", "rb")
    ret = pickle.load( pickle_in )
    pickle_in.close()
    return ret

def dumpbFourDict(bFourNimbers):
    pickle_out = open("bFourNimbers.pickle", "wb")
    pickle.dump(bFourNimbers, pickle_out)
    pickle_out.close()


def getbFourDict():
    pickle_in = open("bFourNimbers.pickle", "rb")
    ret = pickle.load( pickle_in )
    pickle_in.close()
    return ret


if __name__ == "__main__":
    aFourNimbersDict = {0:0, 1:0, 2:1, 3:3, 4:4, 5:2} #Dont Touch
    bFourNimbersDict = {0:2, 1:1, 2:3, 3:2, 4:5, 5:3} #Dont Touch
    cFourNimbersDict = {-1:1, 0:3, 1:0, 2:2, 3:1, 4:4, 5:0} #Dont Touch

    for i in range(101):
        print(i, A(i)) # prints the sprague-grundy value a(i)