Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

The code checks many more conditions like the one below. I was thinking to memoize it, but I can't think about how (writers block). How else could I optimize this? I know it seems silly, but my code is spending the majority of the time in the function.

def has_three(p, board):
    """Checks if player p has three in a row"""
    # For every position on the board
    for i in xrange(6):
        for j in xrange(7):
            if board[i][j] == p:
                if i<=2 and board[i+1][j]==p and board[i+2][j]==p and board[i+3][j]==0:
                    return True
                if i>=3 and board[i-1][j]==p and board[i-2][j]==p and board[i-3][j]==0:
                    return True
                if j<=3 and board[i][j+1]==p and board[i][j+2]==p and board[i][j+3]==0:
                    return True
                if j>=3 and board[i][j-1]==p and board[i][j-2]==p and board[i][j-3]==0:
                    return True
                if i<=2 and j<=3 and board[i+1][j+1]==p and board[i+2][j+2]==p and board[i+3][j+3]==0:
                    return True
                if i<=2 and j>=3 and board[i+1][j-1]==p and board[i+2][j-2]==p and board[i+3][j-3]==0:
                    return True
                if i>=3 and j<=3 and board[i-1][j+1]==p and board[i-2][j+2]==p and board[i-3][j+3]==0:
                    return True
                if i>=3 and j>=3 and board[i-1][j-1]==p and board[i-2][j-2]==p and board[i-3][j-3]==0:
                    return True
    return False
share|improve this question
3  
Can you post the entire function and some input and expected output? Also, what the function is supposed to do? – Francis Avila Apr 26 at 21:13
1  
+1 for profiling your code. – Steven Rumbalski Apr 26 at 21:17
Can there be more than two players? – Steven Rumbalski Apr 26 at 22:23
nope, only two. and i'll call them 1 and 2 – angrymonkey Apr 26 at 22:32
1  
A board of 7x6 looks like "Connect Four", except that you check not 4 but 3 connected cells ("Connect Three"?). Is that what you are trying to do? – tokland Apr 27 at 8:46
show 2 more comments

2 Answers

up vote 1 down vote

We really need to know more about the game to help you properly. Also, why is your program spending so much time in this function? (Are you doing some kind of lookahead, with this function being part of the evaluation?)

If this is a game like gomoku, where players take turns, and in each turn a player places one piece on the board, and the first player to get n in a line wins, then the only way that the board can have a winning line is if that line includes the piece that was just played. Hence there's no point looking at other points in the board.

So in this case you'd write something like this:

DIRECTIONS = [(1,0),(1,1),(0,1),(-1,1)]

def legal_position(i, j, board):
    """Return True if position (i, j) is a legal position on 'board'."""
    return 0 <= i < len(board) and 0 <= j < len(board[0])

def winning_move(player, move, board, n = 3):
    """Return True if 'move' is part of a line of length 'n' or longer for 'player'."""
    for di, dj in DIRECTIONS:
        line = 0
        for sign in (-1, 1):
            i, j = move
            while legal_position(i, j, board) and board[i][j] == player:
                i += sign * di
                j += sign * dj
                line += 1
        if line > n: # move was counted twice
            return True
    return False

But without understanding the rules of your game, it's impossible for me to know if this approach makes any sense.

share|improve this answer
up vote 0 down vote

You can reduce the number of comparisons if you just loop through rows, columns and diagonals, and count the consecutive p's as you go along.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.