import os


class TicTacToeBoard:
    """
    Since the value for X and O is arbitrary. It behooves us to make an
    effort to never hardcode these values.
    """

    X = True
    O = False
    _ = None

    _d8 = [
        lambda x: TicTacToeBoard._rotation(x, 0),
        lambda x: TicTacToeBoard._rotation(x, 1),
        lambda x: TicTacToeBoard._rotation(x, 2),
        lambda x: TicTacToeBoard._rotation(x, 3),
        lambda x: TicTacToeBoard._reflection(TicTacToeBoard._rotation(x, 0)),
        lambda x: TicTacToeBoard._reflection(TicTacToeBoard._rotation(x, 1)),
        lambda x: TicTacToeBoard._reflection(TicTacToeBoard._rotation(x, 2)),
        lambda x: TicTacToeBoard._reflection(TicTacToeBoard._rotation(x, 3)),
    ]

    def __init__(self, board):
        # Dihedral group on 8 objects. Used for symmetries between boards.

        if type(board) == int:
            self._boardAsNumber = board
            self._boardAsArray = self._numberToBoard(board)
        else:
            self._boardAsNumber = self._boardToNumber(board)
            self._boardAsArray = board

    def __int__(self):
        return self._boardAsNumber

    def __getitem__(self, key):
        return self._boardAsArray[key]

    def __setitem__(self, key, value):
        self._boardAsArray[key] = value
        self._boardAsNumber = self._boardToNumber(self._boardAsArray)

    def __str__(self):
        valueToString = {
            self.X: "X",
            self.O: "O",
            self._: "_"
        }
        board = [valueToString[i] for i in self._boardAsArray]
        board.insert(6, os.linesep)
        board.insert(3, os.linesep)
        return ''.join(board)

    def _boardToNumber(self, boardObject):
        """
        There are three states of a nine squares, so a board can be described
        by a 9 digit trinary number.

        I could hardcode this, but I think the loop is more intuitive.
        Hopefully the interpreter is smart enough to optimize it.
        """
        trinaryValue = {
            self.X: 2,
            self.O: 1,
            self._: 0
        }
        theNumber = 0
        for x in range(9):
            # We want the first element to be the most significant,
            # so we use 9 - x
            # The loop offset requires the x - 1
            theNumber += trinaryValue[boardObject[x]] * 3 ** (9 - x - 1)
        return theNumber

    def _numberToBoard(self, theNumber):
        boardValue = {
            2: self.X,
            1: self.O,
            0: self._
        }
        theBoard = []
        for x in range(9):
            trinaryDigit = int(theNumber / 3 ** (9 - x - 1))
            theBoard.append(boardValue[trinaryDigit])
            theNumber -= trinaryDigit * 3 ** (9 - x - 1)
        return theBoard

    # Dihedral group operations. Since this implementation is tic-tac-toe
    # specific, we don't have a separate DihedralGroup class.
    @staticmethod
    def _reflection(board):
        return [
            board[2], board[1], board[0],
            board[5], board[4], board[3],
            board[8], board[7], board[6]
        ]

    @staticmethod
    def _rotation(board, steps):
        octogon = [
            board[0],
            board[1],
            board[2],
            board[5],
            board[8],
            board[7],
            board[6],
            board[3]
        ]
        rotatedOctogon = [octogon[(x + steps*2) % 8] for x in range(8)]
        rotatedBoard = [
            rotatedOctogon[0], rotatedOctogon[1], rotatedOctogon[2],
            rotatedOctogon[7],          board[4], rotatedOctogon[3],
            rotatedOctogon[6], rotatedOctogon[5], rotatedOctogon[4]
        ]
        return rotatedBoard

    def getWhoseTurn(self):
        """
        Count the number of X's and O's and figure out whose turn it is.
        """
        numberOfXs = sum([1 for i in self._boardAsArray if i == self.X])
        numberOfOs = sum([1 for i in self._boardAsArray if i == self.O])
        if numberOfXs == numberOfOs:
            return self.X
        else:
            return self.O

    def getUniqueRepresentation(self):
        """
        This returns the normalized board.
        See README.md for normalizing and why we do it.
        """
        board = self._boardAsArray
        minBoard = self._boardAsNumber
        operation = 0
        for x in range(1, len(self._d8)):
            boardPrime = self._boardToNumber(self._d8[x](board))
            if boardPrime < minBoard:
                minBoard = boardPrime
                operation = x

        return minBoard, operation

    def getWhoWon(self):
        waysToWin = [
            [0, 1, 2],
            [3, 4, 5],
            [6, 7, 8],
            [0, 3, 6],
            [1, 4, 7],
            [2, 5, 8],
            [0, 4, 8],
            [6, 4, 2]
        ]
        board = self._boardAsArray
        for x in waysToWin:
            if board[x[0]] == board[x[1]] == board[x[2]]:
                return board[x[0]]
        return None

    def createNextStep(self):
        """
        Returns TicTacToeBoard Objects
        """
        startingState = self._boardAsArray
        whoseTurn = self.getWhoseTurn()

        nextStates = []
        for square in range(9):  # For each square
            if startingState[square] is None:
                newState = list(startingState)
                newState[square] = whoseTurn
                nextStates += [TicTacToeBoard(newState)]

        return nextStates

if __name__ == "__main__":
    X = TicTacToeBoard.X
    O = TicTacToeBoard.O
    _ = TicTacToeBoard._

    #  trinary 222, 110, 000 == decimal 19278
    boardArray = [
        X, X, X,
        O, O, _,
        _, _, _
    ]
    boardNumber = 19278

    board = TicTacToeBoard(boardArray)
    board2 = TicTacToeBoard(boardNumber)
    assert int(board) == int(board2) == boardNumber
    assert list(board) == list(board2) == boardArray

    assert TicTacToeBoard._d8[0](board) == [
        X, X, X,
        O, O, _,
        _, _, _
    ]
    assert TicTacToeBoard._d8[1](board) == [
        X, _, _,
        X, O, _,
        X, O, _
    ]
    assert TicTacToeBoard._d8[2](board) == [
        _, _, _,
        _, O, O,
        X, X, X
    ]
    assert TicTacToeBoard._d8[3](board) == [
        _, O, X,
        _, O, X,
        _, _, X
    ]
    assert TicTacToeBoard._d8[4](board) == [
        X, X, X,
        _, O, O,
        _, _, _
    ]
    assert TicTacToeBoard._d8[5](board) == [
        _, _, X,
        _, O, X,
        _, O, X
    ]
    assert TicTacToeBoard._d8[6](board) == [
        _, _, _,
        O, O, _,
        X, X, X
    ]
    assert TicTacToeBoard._d8[7](board) == [
        X, O, _,
        X, O, _,
        X, _, _
    ]

    assert board.getWhoseTurn() == O
    board[5] = O
    assert board.getWhoseTurn() == X
    board[5] = _

    newline = os.linesep
    assert str(board) == "XXX" + newline + "OO_" + newline + "___"
    print "Tests pass."
