def displayTitle():
    print ''
    print '======================'
    print 'Welcome to Tic-Tac-Toe'
    print '======================'
    print ''
    return

def displayBoard(board_state):
    'given a board state, print it nicely'

    display_state = {} # Don't want to change board_state

    #convert 0,1,2 to letter, X, and O respectively
    for x in board_state.keys():
        if board_state[x]==0:
            display_state[x] = x
        elif board_state[x]==1:
            display_state[x] = 'X'
        elif board_state[x]==2:
            display_state[x] = 'O'
        else:
            display_state[x] = 'Z' #ERROR

    row1 = [display_state['a'],display_state['b'],display_state['c']]
    row2 = [display_state['d'],display_state['e'],display_state['f']]
    row3 = [display_state['g'],display_state['h'],display_state['i']]    
    
    spacer = ' --- | --- | ---'
    print ''
    print ' ',row1[0],' | ',row1[1], ' | ', row1[2]
    print spacer
    print ' ',row2[0],' | ',row2[1], ' | ', row2[2]
    print spacer
    print ' ',row3[0],' | ',row3[1], ' | ', row3[2]
    print ''


def winnerIs(board_state):
    "returns 0 if no winner, 1 for Player 1, 2 for Player 2, 3 for tie"
   
    row1 = [board_state['a'],board_state['b'],board_state['c']]
    row2 = [board_state['d'],board_state['e'],board_state['f']]
    row3 = [board_state['g'],board_state['h'],board_state['i']]
    col1 = [board_state['a'],board_state['d'],board_state['g']]
    col2 = [board_state['b'],board_state['e'],board_state['h']]
    col3 = [board_state['c'],board_state['f'],board_state['i']]
    dia1 = [board_state['a'],board_state['e'],board_state['i']]
    dia2 = [board_state['c'],board_state['e'],board_state['g']]
    
    checklist = [row1,row2,row3,col1,col2,col3,dia1,dia2]

    for x in checklist:
        if x[0]==x[1]==x[2]:
            return x[1] # we have a winner
        
    # No winner, check to see if board is full:
    for x in [row1,row2,row3]:
        if x[0] == 0  or  x[1] == 0  or  x[2] == 0:
            return 0 #board is not full, no winner
                
    return 3 #board is full, tie

def validTurn(player,letter,board_state):
    'returns 0 if turn is invalid, 1 if turn is valid'
    
    if letter in board_state:
        if board_state[letter] == 0:
            return 1
    else:
        return 0

def chooseLetter(player, board_state):
    'select a board location for the CPU to play,return letter'
    
    #just choose first open space
    for x in board_state.keys():
        if validTurn(player,x,board_state):
            return x
    print "MAJOR ERROR, CPU couldn't choose letter"

def decideCPUPlayer():
    'Returns 1 if a CPU opponent is needed, 0 otherwise'
    choice = 0
    while choice not in ['Y','N']:
        choice = raw_input('Do you want to play against the Computer?(Y/N)')
        
    if choice == 'Y':
        return 1
    else:
        return 0

    
    

board_state = dict( (x,0) for x in 'a b c d e f g h i'.split())

displayTitle()

displayBoard(board_state)

#Initialize variables
player = 1
letter = 'z'
winner = 0

cpu = decideCPUPlayer()

while winner == 0:

    if player == 1 or cpu == 0:
        while not validTurn(player,letter,board_state):
            print 'Player ',player,','
            letter = raw_input('Please choose a letter:')
    elif cpu == 1:
        letter = chooseLetter(2,board_state)
        print 'I am the computer and I choose: ',letter

    board_state[letter] = player
    
    if player == 1:
        player = 2
    else:
        player = 1
    
    displayBoard(board_state)

    winner = winnerIs(board_state)

if winner == 1:
    print 'Congratulations Player 1!'
elif winner == 2:
    print 'Congratulations Player 2!'
else:
    print 'Sorry, it\'s a tie!'