import random


class Board:
    """A data type representing a Connect-4 board
       with an arbitrary number of rows and columns.
    """

    def __init__(self, width, height):
        """Construct objects of type Board, with the given width and height."""
        self.width = width
        self.height = height
        self.data = [[' ']*width for row in range(height)]

    def __repr__(self):
        """This method returns a string representation
           for an object of type Board.
        """
        s = ''
        for row in range(0, self.height):
            s += '|'
            for col in range(0, self.width):
                s += self.data[row][col] + '|'
            s += '\n'

        s += (2*self.width + 1) * '-'
        s += "\n"
        for i in range(0, self.width):
            s += " " + str(i)


        return s

    def addMove(self, col, ox):
        """Adds a checker (O or X) to the column indicated by col.
        """
        H = self.height
        for row in range(0, H):
            if self.data[row][col] != ' ':
                self.data[row - 1][col] = ox
                return
        self.data[H - 1][col] = ox

    def setBoard(self, moveString):
        """Accepts a string of columns and places
           alternating checkers in those columns,
           starting with 'X'.

           For example, call b.setBoard('012345')
           to see 'X's and 'O's alternate on the
           bottom row, or b.setBoard('000000') to
           see them alternate in the left column.

           moveString must be a string of one-digit integers.
        """
        nextChecker = 'X'
        for colChar in moveString:
            col = int(colChar)
            if 0 <= col <= self.width:
                self.addMove(col, nextChecker)
            if nextChecker == 'X':
                nextChecker = 'O'
            else:
                nextChecker = 'X'

    def clear(self):
        """Clears the board of all x's amd o's.
        """
        W = self.width
        H = self.height
        self.data = [[' ']*W for row in range(H)]

    def allowsMove(self, c):
        """ returns true if the board allows a move in the column (c) specified and returns false if the column is full or not in the board range.
        """
        H = self.height
        W = self.width
        D = self.data

        if c >= W or c < 0:
            return False
        elif D[0][c] != ' ':
            return False
        else:
            return True

    def isFull(self):
        """ returns true if the board is full of checkers and false if it has open spaces.
        """
        for i in range(self.width):
            if self.allowsMove(i) == True:
                return False
        return True

    def delMove(self, c):
        """removes the top checker from the column c and does nothing if this space is empty.
        """
        H = self.height
        for row in range(0, H):
            if self.data[row][c] != ' ':
                self.data[row][c] = ' '
                return

    def winsFor(self, ox):
        """Returns true if there are four checkers of type ox in a row on the board and returns false otherwise.
        """
        H = self.height
        W = self.width
        D = self.data

        for row in range(0, H):
            for col in range(0, W - 3):
                if D[row][col] == ox and \
                   D[row][col + 1] == ox and \
                   D[row][col + 2] == ox and \
                   D[row][col + 3] == ox:
                    return True
        for col in range(0, W):
            for row in range(0, H - 3):
                if D[row][col] == ox and \
                   D[row + 1][col] == ox and \
                   D[row + 2][col] == ox and \
                   D[row + 3][col] == ox:
                    return True
        for row in range(0, H - 3):
            for col in range(0, W - 3):
                if D[row][col] == ox and \
                   D[row + 1][col + 1] == ox and \
                   D[row + 2][col + 2] == ox and \
                   D[row + 3][col + 3] == ox:
                    return True
        for row in range(0, H - 3):
            for col in range(0, W):
                if D[row][col] == ox and \
                   D[row + 1][col - 1] == ox and \
                   D[row + 2][col - 2] == ox and \
                   D[row + 3][col - 3] == ox:
                    return True

    def colsToWin(self, ox):
        """Returns a list of columns in numeric order where the checker "ox" can move in the next turn in order to win the game, only looking ahead one turn.
        """
        W = self.width
        win = []
        for c in range(W):
            if self.allowsMove(c) == True:
                self.addMove(c, ox)
                if self.winsFor(ox) == True:
                    win += [c]
                self.delMove(c)
        return win


    def aiMove(self, ox):
        """Returns an integer of what column to move into for the checker "ox" which will be the column that allows ox to win or block the other player if possible or move randomly otherwise.
        """
        if ox == 'O':
            xo = 'X'
        else:
            xo = 'O'
        oxcol = self.colsToWin(ox)
        xocol = self.colsToWin(xo)
        ALL = [ e for e in range( self.width ) if self.allowsMove( e ) ]

        if len(oxcol) != 0:
            return oxcol[ 0 ]
        elif len(xocol) != 0:
            return xocol[ 0 ]
        else:
            return random.choice(range(self.width))


    def hostGame(self):
        """Hosts a game of connect-four, alternating turns between X's and O's (always goes second) and asks the user to select a column number for each move.
        """
        print(self)
        while True:
            x_turn = int(input('Enter your column number for X: '))
            while self.allowsMove(x_turn) ==  False:
                x_turn = int(input("Enter your column number for X: "))
            self.addMove(x_turn, 'X')
            print(self)
            if self.winsFor('X') == True:
                print("X wins!")
                break

            y_turn = self.aiMove("O")
            self.addMove(y_turn, 'O')
            print(self)
            if self.winsFor('O') == True:
                print("O wins!")
                break