2
\$\begingroup\$

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
\$\endgroup\$
5
  • 4
    \$\begingroup\$ Can you post the entire function and some input and expected output? Also, what the function is supposed to do? \$\endgroup\$ Commented Apr 26, 2013 at 21:13
  • \$\begingroup\$ Can there be more than two players? \$\endgroup\$ Commented Apr 26, 2013 at 22:23
  • \$\begingroup\$ nope, only two. and i'll call them 1 and 2 \$\endgroup\$
    – mergesort
    Commented Apr 26, 2013 at 22:32
  • 2
    \$\begingroup\$ 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? \$\endgroup\$
    – tokland
    Commented Apr 27, 2013 at 8:46
  • \$\begingroup\$ Even not knowing the game, I wonder if the checks for ==0 are correct here. \$\endgroup\$ Commented Apr 28, 2013 at 9:25

2 Answers 2

1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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