#! /usr/bin/env python3

"""Play a game of tic-tac-toe against a human opponent, or even
against a different computer algorithm.
"""

import random
import sys

def main():
    board = new_board()
    print_board(board)
    while True:
        ## ask the player for a move; note that this line could be
        ## replaced by one of the "play_computer..." functions below
        get_move(board, 'x')
        print_board(board)
        winner = find_winner(board)
        if winner != ' ' or board_is_full(board):
            break
        ## uncomment the line for the algorithm you want to use
        #play_computer_first_found(board, marker)
        #play_computer_random(board, marker)
        #play_computer_defensive(board, marker)
        play_computer_opportunistic(board, 'o')
        print_board(board)
        winner = find_winner(board)
        if winner != ' ' or board_is_full(board):
            break
    if winner == ' ':
        print('Tie!')
    else:
        print('winner is', winner)

def new_board():
    """create an empty tic-tac-toe board - all cells have blank spaces"""
    row0 = [' ', ' ', ' ']
    row1 = [' ', ' ', ' ']
    row2 = [' ', ' ', ' ']
    board = [row0, row1, row2]
    return board

def print_board(board):
    """print a representation of the board to the terminal"""
    print('-------')
    for row in board:
        for cell in row:
            print('|', end = "")
            print(cell, end = "")
        print('|')
        print('-------')

def set_cell(board, row, col,  marker):
    """sets the cell at coordinates (row, col) to the given marker"""
    # print("player '%s' set cell (%d, %d)" % (marker, row, col))
    board[row][col] = marker

def get_move(board, marker):
    """asks the player for a move; player types numbers 0, 1 or 2 for row
    and col"""
    valid = False
    while not valid:
        row, col = -1, -1
        while not row in [0, 1, 2]:
            row = int(input('row? '))
        while not col in [0, 1, 2]:
            col = int(input('col? '))
        if board [row][col] == ' ':
            valid = True
    set_cell(board, row, col, marker)

def next_marker(prev_marker):
    """returns the opposite marker from the one given"""
    if prev_marker=='x':
        return'o'
    else:
        return'x'

def play_computer_first_found(board, marker):
    """simplest computer algorithm: put your marker on the first empty
    cell you find"""
    for row in range(3):
        for col in range(3):
            if board[row][col]==' ':
                set_cell(board, row, col, marker)
                return

def play_computer_random(board, marker):
    """another simple computer algorithm: place your marker in a random
    empty location"""
    done=False
    while not done:
        row=random.randint(0, 2)
        col=random.randint(0, 2)
        if board[row][col]==' ':
            set_cell(board, row, col, marker)
            done = True

def play_computer_defensive(board, my_marker):
    """plays a defensive strategy: if there is a threat by the opponent,
    we plug it up; otherwise we play the random algorithm"""
    opp_marker = next_marker(my_marker)
    [row, col, win_candidate] = find_win_candidate(board, opp_marker)
    if win_candidate == opp_marker:
        set_cell(board, row, col, my_marker)
    else:
        play_computer_random(board, my_marker)

def play_computer_opportunistic(board, my_marker):
    """plays opportunistically: if we can win we put our marker in that
    slot; otherwise we play the defensive algorithm"""
    [row, col, win_candidate] = find_win_candidate(board, my_marker)
    if win_candidate == my_marker:
        set_cell(board, row, col, my_marker)
    else:
        play_computer_defensive(board, my_marker)

def find_winner(board):
    """returns 'x' if x is the winner, 'o' if o is the winer, or ' ' if
    there is no winner yet"""
    for row in board:
        winner = find_winner_row(row)
        if winner != ' ':
            return winner
    for col_no in range(3):
        col = extract_col(board, col_no)
        winner = find_winner_row(col)
        if winner != ' ':
            return winner
    winner = find_winner_row(extract_slash(board))
    if winner != ' ':
        return winner
    winner = find_winner_row(extract_backslash(board))
    if winner != ' ':
        return winner
    return ' '


def find_winner_row(row):
    """sees if the given row has a solid win.  note that a "row" is just a
    list of 3 cells, so if you pack a column or diagonal into this
    list it will also work to find column and diagonal winners
    """
    if row[0] == row[1] and row[1] == row[2]:
        if row [0] != ' ':
            return row[0]
    return ' '

def find_win_candidate(board, marker):
    """scan each cell on the board to see if the given marker could
    win on that cell.  returns a triplet (row, col, marker) if that
    marker could win; returns (None, None, None) if there is no 
    victory chance"""
    for row in range(3):
        for col in range(3):
            if board[row][col] == ' ':
                is_win = check_if_winning_move(board, row, col, marker)
                if is_win == marker:
                    print('CAND: %s at %d %d' % (marker, row, col))
                    return [row, col, is_win]
    return [None, None, None]

def check_if_winning_move(board, row, col, marker):
    """See if the given cell allows a win by the given marker.  Returns
    that winning marker if so, otherwise returns a space ' ' """
    assert(board[row][col] == ' ') # only call this on blank cells
    ## temporarily set the cell to this marker
    set_cell(board, row, col, marker)
    winner = find_winner(board)
    ## restore the cell to a space
    set_cell(board, row, col, ' ')
    ## see if there is a winner
    if winner == marker:
        return winner
    return ' '

def count(row, marker):
    """counts how many times the marker occurs in this list (which could
    be a row or a slash or backslash or column packed as a list);
    returns the count and one of the positions of that marker in the
    list"""
    count=0
    last_pos = -1
    for pos in range(3):
        if row[pos] == marker:
            count = count+1
            last_pos = pos
    return (count,  last_pos)

def extract_col(board, col_no):
    """packages the entries for the given column into a list"""
    col = [board[0][col_no], board[1][col_no], board[2][col_no]]
    return col

def extract_slash(board):
    """packages the entries for the "slash" diagonal into a list"""
    slash = [board[0][2], board[1][1], board[2][0]]
    return slash

def extract_backslash(board):
    """packages the entries for the "backslash" diagonal into a list"""
    blash=[board[0][0], board[1][1], board[2][2]]
    return blash

def board_is_full(board):
    """returns True if the board is full, False otherwise"""
    for row in board:
        for cell in row:
            if cell==' ':
                return False
    return True

if __name__=='__main__':
    main()