# A function that prints the game board as it currently stands
def make_grid(board):
    print("\t       GAME        \t\t        KEY         \n")
    print("\t  {}  |   {}  |  {}   \t\t  1  |   2  |  3  ".format(board['1'], board['2'], board['3']))

    lineA = "\t_____|______|_____\t\t_____|______|_____"
    lineB = "\t     |      |     \t\t     |      |     "

    print(lineA)
    print(lineB)
    print("\t  {}  |   {}  |  {}  \t\t  4  |   5  |  6  ".format(board['4'], board['5'], board['6']))
    print(lineA)
    print(lineB)
    print("\t  {}  |   {}  |  {}  \t\t  7  |   8  |  9  ".format(board['7'], board['8'], board['9']))

# A function that prompts the player for a valid move
def get_move(turn,board):
    # Find out which player's turn it is
    if turn % 2 == 1:
        player = "Player 1"
    else:
        player = "Player 2"
    # Set up the prompt statement
    prompt = player + ", what is your move? "


    # Until we get a valid move, keep asking for one.
    # Find out which spots are unoccupied.
    free = [idx for idx in board if board[idx] == " "]
    occupied =[idx for idx in board if not board[idx] == " "]
    valid_move = 0
    while valid_move == 0:
        move = input(prompt)

        if move in free:
            valid_move = 1
        elif move in occupied:
            print("Invalid move! That space is occupied.")
        else:
            print("Invalid move! Please enter a number 1-9.")

    # Return a string containing the move
    return(move)

# A function that initializes the game board
def initialize_board():
    board = {'1': " ",'2': " ",'3': " ", '4':" ",
          '5':" ",'6':" ",'7':" ",'8':" ",'9':" "}
    return(board)

# A function to update the game board
def update_board(move, turn):
    # Find out which marker we're using
    if turn % 2 == 1:
        marker = "X"
    else:
        marker = "O"

    # Update the board
    board[move] = marker
    return(board)

# A function that takes the game board in its current state and looks for a winner
def check_for_win(board):

    # Horizontal wins
    h1 = [board['1'], board['2'], board['3']]
    h2 = [board['4'], board['5'], board['6']]
    h3 = [board['7'], board['8'], board['9']]

    # Vertical wins
    v1 = [board['1'], board['4'], board['7']]
    v2 = [board['2'], board['5'], board['8']]
    v3 = [board['3'], board['6'], board['9']]

    # diagonal wins
    d1 = [board['1'], board['5'], board['9']]
    d2 = [board['3'], board['5'], board['7']]

    # Loop over all the possible winning strategies to check if they're on the board
    wins =  [h1,h2,h3,v1,v2,v3,d1,d2]
    for w in wins:
        if list(set(w)) == ["X"]:
            the_winner = "Player 1"
            break
        elif list(set(w)) == ["O"]:
            the_winner = "Player 2"
            break
        else:
            the_winner = "nobody"
    return(the_winner)


if __name__== "__main__":
    board = initialize_board()

    turn = 1 # intialize the turn counter
    winner = "nobody" # intialize the winner as....nobody!

    while winner == "nobody" and turn < 10: # can't have more than 9 turns
        make_grid(board)
        move = get_move(turn, board)
        update_board(move,turn)
        winner = check_for_win(board)
        turn += 1

    # Display the winning board and a pronounement of victory
    make_grid(board)
    print("The winner is " + winner + "!!!")