<reponame>s-cork/BIO<gh_stars>0
# this is a graph to represent the moves that can be made
graph = {0: tuple(range(1,9))} # all moves available from the centre (putahi)
for i in range(1,9): # generates all moves available from each kawai 
    before = i-1 if i-1!=0 else 8
    after  = i+1 if i+1!=9 else 1
    graph[i] = (0,before,after)

def get_middle(board,player):
    ''' returns index of the middle piece(s)
    we know there can't be more than 2 middle pieces so it does a left and a right find 
    if no middle pieces found returns an empty tuple'''
    temp_board = ' '+''.join(board[1:])
    if 3*player in temp_board:
        return (temp_board.find(3*player)+1, temp_board.rfind(3*player)+1)
    else:
        return () 

def get_moves(board,player):
    ''' first gets any middle pieces
    then iterates over the pieces that are not 'middle pieces' and sees if there is a move available
    yields tuples of available moves 
    '''
    player = 'O' if player==0 else 'X'
    middle = get_middle(board,player)
    for i,piece in enumerate(board):
        if piece is player and i not in middle:
            for j in graph[i]:
                if board[j] is 'E':
                    yield (i,j)

def make_move(board,move):
    '''board is current board, move is a tuple (i,j)
    swaps board[i] and board[j] and returns it 
    note I created a copy of the board so as not to manipulate the original list object'''
    i,j = move
    temp_board = board[:]
    temp_board[i], temp_board[j] = temp_board[j], temp_board[i]
    return temp_board

def can_win(board,player):
    '''checks if a move is a winning move, i.e. the other player can't move on their next turn'''
    for move in get_moves(board,player):
        temp_board = make_move(board,move)
        if not list(get_moves(temp_board, (player+1)%2)):
            return move  #this will be the left most move

def opponent_can_win(board,player):
    ''' yields moves to be avoided which would lead to opponent being able to win'''
    for move in get_moves(board,player):
        temp_board = make_move(board,move)
        if can_win(temp_board, (player+1)%2) is not None:
            yield move


def play_game(board):
    ''' plays the game and returns the board and winner as a tuple'''
    instruction = input()
    player = 0
    max = 1000
    
    if next(get_moves(board,player), None) is None: # checks if a first move is available
        return board, 2 #player 2 is the winner

    for _ in range(max):
        # checks rule 1
        winning_move = can_win(board,player)
        if winning_move is not None:
            board = make_move(board,winning_move)
            return board, player+1
        # checks rule 2
        avoid = list(opponent_can_win(board,player))
        for move in get_moves(board,player):
            if move not in avoid:
                # this will satisfy both rules 2 and 3
                board = make_move(board,move)
                break
        else:
            # no break means there is no move that will prevent opponenent winning 
            board = make_move(board,avoid[0])

        player = (player+1)%2
        if instruction is 'n':
            print(''.join(board))
            instruction = input()
    # if we've done max iterations then no winner
    return board, None
    

initial_board = list(input().upper())
final_board, winner = play_game(initial_board)

if winner is None:
    print('Draw')
else:
    print(''.join(final_board))
    print('Player {} wins'.format(winner))
# this is a graph to represent the moves that can be made
graph = {0: tuple(range(1,9))} # all moves available from the centre (putahi)
for i in range(1,9): # generates all moves available from each kawai 
    before = i-1 if i-1!=0 else 8
    after  = i+1 if i+1!=9 else 1
    graph[i] = (0,before,after)

def get_middle(board,player):
    ''' returns index of the middle piece(s)
    we know there can't be more than 2 middle pieces so it does a left and a right find 
    if no middle pieces found returns an empty tuple'''
    temp_board = ' '+''.join(board[1:])
    if 3*player in temp_board:
        return (temp_board.find(3*player)+1, temp_board.rfind(3*player)+1)
    else:
        return () 

def get_moves(board,player):
    ''' first gets any middle pieces
    then iterates over the pieces that are not 'middle pieces' and sees if there is a move available
    yields tuples of available moves 
    '''
    player = 'O' if player==0 else 'X'
    middle = get_middle(board,player)
    for i,piece in enumerate(board):
        if piece is player and i not in middle:
            for j in graph[i]:
                if board[j] is 'E':
                    yield (i,j)

def make_move(board,move):
    '''board is current board, move is a tuple (i,j)
    swaps board[i] and board[j] and returns it 
    note I created a copy of the board so as not to manipulate the original list object'''
    i,j = move
    temp_board = board[:]
    temp_board[i], temp_board[j] = temp_board[j], temp_board[i]
    return temp_board

def can_win(board,player):
    '''checks if a move is a winning move, i.e. the other player can't move on their next turn'''
    for move in get_moves(board,player):
        temp_board = make_move(board,move)
        if not list(get_moves(temp_board, (player+1)%2)):
            return move  #this will be the left most move

def opponent_can_win(board,player):
    ''' yields moves to be avoided which would lead to opponent being able to win'''
    for move in get_moves(board,player):
        temp_board = make_move(board,move)
        if can_win(temp_board, (player+1)%2) is not None:
            yield move


def play_game(board):
    ''' plays the game and returns the board and winner as a tuple'''
    instruction = input()
    player = 0
    max = 1000
    
    if next(get_moves(board,player), None) is None: # checks if a first move is available
        return board, 2 #player 2 is the winner

    for _ in range(max):
        # checks rule 1
        winning_move = can_win(board,player)
        if winning_move is not None:
            board = make_move(board,winning_move)
            return board, player+1
        # checks rule 2
        avoid = list(opponent_can_win(board,player))
        for move in get_moves(board,player):
            if move not in avoid:
                # this will satisfy both rules 2 and 3
                board = make_move(board,move)
                break
        else:
            # no break means there is no move that will prevent opponenent winning 
            board = make_move(board,avoid[0])

        player = (player+1)%2
        if instruction is 'n':
            print(''.join(board))
            instruction = input()
    # if we've done max iterations then no winner
    return board, None
    

initial_board = list(input().upper())
final_board, winner = play_game(initial_board)

if winner is None:
    print('Draw')
else:
    print(''.join(final_board))
    print('Player {} wins'.format(winner))
# this is a graph to represent the moves that can be made # all moves available from the centre (putahi) # generates all moves available from each kawai returns index of the middle piece(s)     we know there can't be more than 2 middle pieces so it does a left and a right find      if no middle pieces found returns an empty tuple first gets any middle pieces     then iterates over the pieces that are not 'middle pieces' and sees if there is a move available     yields tuples of available moves board is current board, move is a tuple (i,j)     swaps board[i] and board[j] and returns it      note I created a copy of the board so as not to manipulate the original list object checks if a move is a winning move, i.e. the other player can't move on their next turn #this will be the left most move yields moves to be avoided which would lead to opponent being able to win plays the game and returns the board and winner as a tuple # checks if a first move is available #player 2 is the winner # checks rule 1 # checks rule 2 # this will satisfy both rules 2 and 3 # no break means there is no move that will prevent opponenent winning # if we've done max iterations then no winner