Determining three in a row in Python 2d array

I'm working on a tic-tac-toe game with a M x N board in Python. I'm trying to find an efficient way to determine if a player has won (3 in a row either vertical, horizontal, or diagonal direction.) Most 3x3 implementations of the game just check for all possible winning comb开发者_JS百科inations after each turn. This seems a little extreme with a massive board.

4x4 example: (using 1s and 2s instead of Xs and Os)

board = ([1,0,2,1], [0,0,0,1], [2,2,0,0], [1,0,0,1])
for row in board:
    print row

Thanks- Jonathan

---

Although this approach has a certain appeal, it's probably not especially fast.

# A bogus game with wins in several directions.
board = (
    [1,1,2,1],
    [0,2,1,1],
    [2,2,2,1],
    [1,0,0,1],
)

# A few convenience variables.    
n_rows = len(board)    
lft = [ [0] * i for i in range(n_rows) ]  # [[], [0], [0, 0], [0, 0, 0]]
rgt = list(reversed(lft))

# Create transpositions of the board to check for wins in various directions.
transpositions = {
    'horizontal' : board,
    'vertical'   : zip(*board),
    'diag_forw'  : zip(* [lft[i] + board[i] + rgt[i] for i in range(n_rows)] ),
    'diag_back'  : zip(* [rgt[i] + board[i] + lft[i] for i in range(n_rows)] ),
}

# Apply Jonathan's horizontal-win check to all of the transpositions.
for direction, transp in transpositions.iteritems():
    for row in transp:
        s = ''.join( map(str, row) )
        for player in range(1,3):
            if s.find(str(player) * 3) >= 0:
                print 'player={0} direction={1}'.format(player, direction)

Output:

player=1 direction=diag_back
player=2 direction=diag_forw
player=2 direction=horizontal
player=1 direction=vertical

The idea behind the diagonal transpositions is to shift the rows, using lft and rgt for left and right padding. For example, the diag_forw list looks like this after the padding is added (pad characters are shown as periods, even though zeroes are used in the actual code).

1 1 2 1 . . .
. 0 2 1 1 . .
. . 2 2 2 1 .
. . . 1 0 0 1 

Then we simply transpose that array, using zip(*foo), which allows us to use Jonathan's good idea for finding horizontal wins.

---

You can look if the player's move closed the game (looking on that row, that column and the 2 diagonals if they ar x checks consecutively), it's o(x) complexity. Let's say you're looking o that row to see if he won. Look to the left how many consecutively checks are and to the right. If the sum of them excedes x he won. You'll do the same on the columns and on the diagonals.

---

Check for horizontal win

for row in board:
    rowString = ''.join(row)
    if(rowString.count('111') > 2 or rowString.count('222') > 2):
        print "Somebody won"

Check for vertical win

for col in xrange(len(board[0])):
    colString = ""
    for row in board:
        colString = colString.append(row[col])
    if(colString.count('111') > 2 or colString.count('222') > 2):
        print "Somebody won"

Still stumped on diagonals...

---

If you have a board set up as follows:

board = 
([1,0,2,0],
 [0,1,2,0],
 [0,0,0,0],
 [0,0,0,0])

You can imagine it as x and y coordinates, starting from the upper left hand corner, having downward movement as positive y and rightward movement as positive x. A move at board[3][3] by either player would be a winning move. Using Teodor Pripoae process, we can construct the horizontal, vertical and diagonals around the last move. The horizontal case is easy.

def horizontal(board, y_coord):
    return board[y_coord]

The vertical case requires us to select the x_coord from each row:

def vertical(board, x_coord):
    return [row[x_coord] for row in board]

The diagonal case is a bit trickier. For this first function, it's computing the diagonal that goes from left to right as it goes top to bottom. Distance basically represents the horizontal distance from zero, when y is equal to zero.

def diagonal1(board, x_coord, y_coord):
    length = len(board[0])
    distance = x_coord - y_coord
    if distance >= 0:
        return [y[x] for x, y in enumerate(board) if distance + x <= length]
    else:
        return [y[x] for x, y in enumerate(board) if x - distance >= 0 and x - distance <= length]

This second function computes the diagonal that goes right to left as it goes top to bottom. In this function distance represents the vertical distance from zero as the horizontal distance is at zero.

def diagonal2(board, x_coord, y_coord):
    length = len(board[0])
    distance = y_coord + x_coord
    return [y[distance - x] for x, y in enumerate(board) if distance - x <= length]

Once you have these defined, you just need a way to check if a player has won. Something like this might do:

def game_over(direction, number_to_win, player_number):
    count = 0
    for i in direction:
        if i == player_number:
            count += 1
            if count = number_to_win:
                return True
        else:
            count = 0
    return False

Having written all of this, it seems like this is overkill, unless you have quite large M and N. While it may be more efficient than checking every victory condition, it does construct the entire horizontal, vertical and diagonal directions, rather than just those coordinates surrounding the last move, it isn't as efficient as it could be.

Maybe this is helpful, but it seems like Brian's suggestion to simply remove x's might be better.

---

I've been using a variant of this question in software developer interviews, so I've thought about the problem a fair bit. Here's a better answer: it handles any number of players, any square tic-tac-toe grid, and any "run size". The approach is fairly simple, provides info about all of the sequences found, and is O(N) where N is the number of cells.

# Given a square tic-tac-toe grid of any size, with any number of players, find
# all sequences (horizontal, vertical, diagonal) of some minimum size.

def main():
    raw_grid = [
        [1, 1, 2, 1, 0],  # Zero means open spot.
        [0, 2, 1, 1, 1],
        [2, 2, 2, 1, 2],
        [1, 0, 1, 1, 2],
        [1, 0, 0, 0, 2],
    ]
    for run in get_runs(raw_grid, 3):
        print run

def get_runs(raw_grid, run_size):
    # Offsets to find the previous cell in all four directions.
    offsets = {
        'h' : ( 0, -1), # _
        'v' : (-1,  0), # |
        'f' : (-1,  1), # /
        'b' : (-1, -1), # \
    }

    # Helpers to check for valid array bounds and to return a new cell dict.
    size      = len(raw_grid)
    in_bounds = lambda r, c: r >= 0 and c >= 0 and r < size and c < size
    new_cell  = lambda i, j, p: dict(h=1, v=1, f=1, b=1, i=i, j=j, player=p)

    # Use the raw grid to create a grid of cell dicts.
    grid = []
    for i, row in enumerate(raw_grid):
        grid.append([])
        for j, player in enumerate(row):
            # Add a cell dict to the grid (or None for empty spots).
            cell = new_cell(i, j, player) if player else None
            grid[i].append(cell)
            if not cell: continue

            # For each direction, look to the previous cell. If it matches the
            # current player, we can extend the run in that direction.
            for d, offset in offsets.iteritems():
                r, c = (i + offset[0], j + offset[1])
                if in_bounds(r, c):
                    prev = grid[r][c]
                    if prev and prev['player'] == cell['player']:
                        # We have a match, so the run size is one bigger,
                        # and we will track that run in the current cell,
                        # not the previous one.
                        cell[d] = prev[d] + 1
                        prev[d] = None

    # For all non-None cells, yield run info for any runs that are big enough.
    for cell in (c for row in grid for c in row if c):
        for d in offsets:
            if cell[d] and cell[d] >= run_size:
                yield dict(
                    player    = cell['player'],
                    endpoint  = (cell['i'], cell['j']),
                    direction = d,
                    run_size  = cell[d],
                )

main()

Output:

{'player': 1, 'direction': 'h', 'endpoint': (1, 4), 'run_size': 3}
{'player': 2, 'direction': 'f', 'endpoint': (2, 0), 'run_size': 3}
{'player': 2, 'direction': 'h', 'endpoint': (2, 2), 'run_size': 3}
{'player': 1, 'direction': 'b', 'endpoint': (2, 3), 'run_size': 3}
{'player': 1, 'direction': 'f', 'endpoint': (3, 2), 'run_size': 3}
{'player': 1, 'direction': 'v', 'endpoint': (3, 3), 'run_size': 4}
{'player': 2, 'direction': 'v', 'endpoint': (4, 4), 'run_size': 3}