Design Tic tac toe game

Question

Today I had an interview, where I was asked to solve this question:

Design Tic tac toe game

Game rules:

Design a simple tic tac game with 2 modes for 3*3 matrix. At the beginning, ask if single player or two player mode has to be played (more details on the mode below).

The players input position on matrix by inputting 2 integers, like:

0,0    0,1    0,2

1,0    1,1    1,2

2,0    2,1    2,2

If anywhere player gives incorrect input, he has to be prompted to give the right value again.

Print the updated matrix after every input. Example: after 3 moves, one game might look like

1    1    _

2    _    _

_     _    _

Single player mode

In this mode, player plays against the computer. You’ve to first assign 0’s or X’s to the Player. X’s play first. The computer can randomly place its assigned symbol at any available position within the matrix.

Two player mode

In this mode, two players play against each other.

The game ends when either player wins, or there are no moves left (draw). At the end of game, print the final result Ask if the player wants to play another game, and start a new game/end the game accordingly.

I got the feedback that complexity could be improved, How to improve it? and how to make it more readable

Code goes below:

def get_input(mat, player):
    input_value = map(int, raw_input().split(','))
    while(validate_input(mat, input_value) == False):
        print "not correct input"
        input_value = map(int,raw_input().split(','))
    mat[input_value[0]][input_value[1]] = player
    return input_value

def validate_input(mat, input_value):
    x = input_value[0]
    y = input_value[1]
    if x not in [0,1,2] or y not in [0,1,2]:
        return False
    if mat[x][y]:
        return False
    return True

def switch_play(player):
    player = 2 if player==1 else 1
    return player

def print_game(mat):
    print mat

def get_random(mat):
    input_value = [random.randint(0,2)] *2
    while(validate_input(mat, input_value) == False):
        print "not correct input"
        input_value = [random.randint(0,2)] *2

    mat[input_value[0]][input_value[1]] = 2
    return input_value 


def game_completed(mat):
    if not game_won(mat):
        for i in xrange(3):
            for j in xrange(3):
                if not mat[i][j]:
                    return False

    return True

def game_won(mat):
    for i in xrange(3):
        row = mat[i]
        if len(set(mat[i])) == 1 and set(mat[i]) != {0}: 
            print 'won the game:player', mat[i][0]
            return True
    for i in xrange(3):
        col = [row[i] for row in mat]
        if len(set(col)) == 1 and set(col)!={0}:
            print 'won the game:player', mat[0][i]
            return True
        dia1 = [mat[i][i] for i in xrange(3)]
        dia2 = [mat[2-i][i] for i in xrange(3)]
        if (len(set(dia1)) == 1 and set(dia1)!={0}):
                print 'won game: player', mat[0][0]
                return True
        if (len(set(dia2)) == 1 and set(dia2)!={0}):
                print 'won game: player', mat[2][2]
                return True
        return False            



print "hoose player 1 your type, X or O?"
p1 = raw_input()
p2 = 'O' if p1=='X' else 'X'
player = 1
mat = [[0,0,0], [0,0,0], [0,0,0]]
computer_playing = False
while True:
    if computer_playing and player==2:
        get_random(mat, player)
    else:
        get_input(mat, player)
    print_game(mat)
    if game_completed(mat):
        print "game is completed"
        break
    player = switch_play(player)

Answer 1

I think your interviewer meant that you can improve checking the winning situation and do it in \$O(1)\$ time by keeping track of the scores in rows, columns and both diagonals (total 8 variables for 3x3 board):

[row1, row2, row3, column1, column2, column3, diagonal, anti-diagonal]

Then, you can increment these value by 1 in case of "player 1" and decrement by one in case of "player 2". This will lead to only checking these 8 values (or you can also use the fact that you know where the last move took place) for 3 or -3 for a winning situation. You can find out more about this idea here.

Or, you can go over all the possible winning combinations like suggested here or here.