def newBoard(n):
    if n > 0:
        return [0 for x in range(n)]
    else:
        print ("n doit etre plus grand que 0")
        exit(0)


def display(board, n):
    s = ""
    indexes = ""
    for i in range(0, n):
        if board[i] == 1:
            c = "X"
        elif board[i] == 2:
            c = "O"
        else:
            c = "."
        s += c + " "
        indexes += str(i + 1) + " "
    print (s)
    print (indexes)


def possible(board, n, player, removed, i):
    if player <= 0 or player > 2:
        return False
    if (board[i - 1] is not 0) or (i - 1 in removed) or (i > n):
        return False
    else:
        return True


def select(board, n, player, removed):
    while True:
        x = input("Player " + str(player) + " Entrer un nombre : ")
        if int(x) > n:
            pass
        if (board[x - 1] == 0) and (x not in removed):
            return x


def put(board, n, player, removed, i):
    if possible(board, n, player, removed, i):
        board[i - 1] = player
        removed = captured(board, n, i)
        print ("Removed: "), removed
        for j in range(len(removed)):
            board[removed[j] - 1] = 0


def again(board, n, player, removed):
    for i in range(n):
        if board[i] == 0:
            return True
    return False


def win(board, n):
    p1 = board.count(1)
    p2 = board.count(2)
    if p1 > p2:
        return "Player 1 gagne"
    elif p1 < p2:
        return "Player 2 gagne"
    else:
        return "Egalité"


def captured(board, n, i):
    capture = []
    # chercher les captures du cote droit
    if i < n:
        selected_player = board[i - 1]
        j = i
        while board[j] != selected_player and board[j] != 0:
            j += 1
            if j > n - 1:
                break

        if j >= n:
            # on a atteint le mur
            if board[n - 1] != selected_player and board[n - 1] != 0:
                for j in range(i, n):
                    capture.append(j + 1)
        else:
            # on a atteint une pose du meme joueur, donc une capture entre deux
            if board[j] == selected_player:
                for x in range(i, j):
                    capture.append(x + 1)

    # chercher les captures du cote gauche
    if i > 1:
        selected_player = board[i - 1]
        j = i - 2
        while board[j] != selected_player and board[j] != 0:
            j -= 1
            if j < 0:
                break

        if j <= 0:
            if board[0] != selected_player and board[0] != 0:
                for j in range(0, i - 1):
                    capture.append(j + 1)

        else:
            # on a atteint une pose du meme joueur, donc une capture entre deux
            if board[j] == selected_player:
                for x in range(j + 1, i - 1):
                    capture.append(x + 1)

    return capture


def alak(n):
    removed = []
    player = 1
    board = newBoard(n)
    while again(board, n, player, removed):
        display(board, n)
        i = select(board, n, player, removed)
        put(board, n, player, removed, i)
        if player == 1:
            player = 2
        elif player == 2:
            player = 1
    print (win(board, n))

alak(9)