#######################
#### NRP3finder.py ####
### Thomas Lam 2018 ###
#######################

import copy
from pprint import pprint

class Alg():  # An algorithm and corresponding effect
    def __init__(self, *args):
        if len(args) == 1:
            self.board = makeBoard(args[0])
            self.moveType = 'x'  # RotX or RotY next?
            self.moveList = []

        if len(args) == 3:
            self.board = copy.deepcopy(args[0])
            self.moveType = args[1]
            self.moveList = args[2][:]

    def move(self, turns):
        if self.moveType == 'x':
            self.board = rotX(self.board, turns)
            self.moveType = 'y'

        elif self.moveType == 'y':
            self.board = rotY(self.board, turns)
            self.moveType = 'x'

        self.moveList.append(turns)

    def executeMoves(self, moves):  # Execute a list of moves in sequence.  Syntax:  [1,2,3,1,2,1,3, etc.]
        for m in moves:
            self.move(m)

    def cloneMove(self, turns):  # Clone the algorithm and advance the clone by one move
        newAlg = Alg(self.board, self.moveType, self.moveList)
        newAlg.move(turns)
        return newAlg

    def permCycleLens(self):  # Compute the lengths of all cycles in the algorithm permutation and toss into an array
        return cycleLens(collapseBoard(self.board))

    def has3Cycle(self):  # Does it contain a 3 cycle?
        return 3 in self.permCycleLens()

    def hasUnique3Cycle(self):  # Does it have a unique 3 cycle?
        has3 = False  # Does it have a pure 3 cycle?
        num3 = 0  # Number of cycles of order divisible by 3
        for num in self.permCycleLens():
            if num == 3:
                has3 = True

            if num % 3 == 0:
                num3 += 1

        return has3 and num3 == 1

    def getUnique3Cycle(self):
        assert self.hasUnique3Cycle
        for cycle in cycleDecompose(collapseBoard(self.board)):
            if len(cycle) == 3:
                return cycle

    def getCycles(self):
        print cycleDecompose(collapseBoard(self.board))

def ppprint(x):
    pprint(x, width=40)

def makeBoard(b):   # Make b+1 x b NRP board
    board = []
    num = 0
    for i in range(b):
        row = []
        for j in range(b+1):
            row.append(num)
            num += 1
        board.append(row)

    return board

def collapseBoard(board):  # List out elements into a 1D array
    out = []
    for row in board:
        for i in row:
            out.append(i)

    return out

def cycleLens(arr):
    remaining = set(arr)
    output = []
    while len(remaining) > 0:
        length = 1
        num = remaining.pop()
        while 1:
            num = arr[num]
            if num not in remaining:
                break

            remaining.remove(num)
            length += 1

        output.append(length)

    return output

def cycleDecompose(arr):
    remaining = set(arr)
    output = []
    while len(remaining) > 0:
        num = remaining.pop()
        cycle = [num]
        while 1:
            num = arr[num]
            if num not in remaining:
                break

            remaining.remove(num)
            cycle.append(num)

        output.append(cycle)

    return output

def rotX(board, turns = 1):
    b = len(board)
    newBoard = copy.deepcopy(board)
    for i in range(b):
        for j in range(b):
            if turns == 1:
                newBoard[i][j] = board[j][b-1-i]

            elif turns == 2:
                newBoard[i][j] = board[b-1-i][b-1-j]

            elif turns == 3:
                newBoard[i][j] = board[b-1-j][i]

    return newBoard

def rotY(board, turns = 1):
    b = len(board)
    newBoard = copy.deepcopy(board)
    for i in range(b):
        for j in range(1,b+1):
            if turns == 1:
                newBoard[i][j] = board[j-1][b-i]

            elif turns == 2:
                newBoard[i][j] = board[b-1-i][b+1-j]

            elif turns == 3:
                newBoard[i][j] = board[b-j][i+1]

    return newBoard

# Testing

testAlg = Alg(3)
testAlg.executeMoves([1,1,1,3,1])

assert testAlg.has3Cycle()
assert not testAlg.hasUnique3Cycle()

testAlg = Alg(4)
testAlg.move(1)
assert not testAlg.has3Cycle()

print 'Congrats!  You didn't mess up!  Starting search...'

# Testing

b = int(raw_input('Board size: '))

algList = [Alg(b)]

found3Cycle = False
foundUnique3Cycle = False

while not foundUnique3Cycle:
    # Advance all algorithms
    newAlgList = []
    for alg in algList:
        newAlgList.append(alg.cloneMove(1))
        newAlgList.append(alg.cloneMove(2))
        newAlgList.append(alg.cloneMove(3))

    algList = copy.deepcopy(newAlgList)

    # Search for 3-cycles

    for alg in algList:
        if alg.has3Cycle() and not found3Cycle:
            print 'Found 3-cycle.'
            print alg.moveList
            found3Cycle = True

        if alg.hasUnique3Cycle() and not foundUnique3Cycle:
            print 'Found unique 3-cycle.'
            print 'Algorithm:',
            print alg.moveList
            print '3-cycle:',
            print alg.getUnique3Cycle()
            print 'All cycles:',
            print alg.getCycles()
            foundUnique3Cycle = True