6
\$\begingroup\$

Problem:

For a given board, judge who had complete a continuously line (could be horizontal, vertical or diagonal) of 5 pieces. Input is a 15×15 chess board, could be white (1), black (2) or empty (0). Return if white win, if black win, if both win or if none of them win.

My specific questions are:

  1. I enumerate each direction one by one, and the code looks very long. Are there any elegant ways to handle directions (I mean direction of horizontal, vertical or diagonal)?
  2. I incrementally count # of black, # of white, to reduce redundant counting. I'm wondering if there are any better ideas to reduce counting.

import random
def check_five(matrix):
    white_win = False
    black_win = False
    for i in range(0, len(matrix)):
        num_white_so_far = 0
        num_black_so_far = 0
        for j in range(0, len(matrix[0])):
            if matrix[i][j] == 1: # 1 for white
                num_white_so_far += 1
                num_black_so_far = 0
                if num_white_so_far == 5:
                    white_win = True
            elif matrix[i][j] == 2: # 2 for black
                num_black_so_far += 1
                num_white_so_far = 0
                if num_black_so_far == 5:
                    black_win = True
            else:
                num_black_so_far = 0
                num_white_so_far = 0
    for j in range(0, len(matrix[0])):
        num_white_so_far = 0
        num_black_so_far = 0
        for i in range(0, len(matrix)):
            if matrix[i][j] == 1: # 1 for white
                num_white_so_far += 1
                num_black_so_far = 0
                if num_white_so_far == 5:
                    white_win = True
            elif matrix[i][j] == 2: # 2 for black
                num_black_so_far += 1
                num_white_so_far = 0
                if num_black_so_far == 5:
                    black_win = True
            else:
                num_black_so_far = 0
                num_white_so_far = 0
    for i in range(0, len(matrix)):
        num_white_so_far = 0 # direction of \, bottom part
        num_black_so_far = 0
        j = 0
        while i < len(matrix) and j < len(matrix[0]):
            if matrix[i][j] == 1: # 1 for white
                num_white_so_far += 1
                num_black_so_far = 0
                if num_white_so_far == 5:
                    white_win = True
            elif matrix[i][j] == 2: # 2 for black
                num_black_so_far += 1
                num_white_so_far = 0
                if num_black_so_far == 5:
                    black_win = True
            else:
                num_black_so_far = 0
                num_white_so_far = 0
            i += 1
            j += 1
    for j in range(1, len(matrix[0])): # direction of \, upper part
        num_white_so_far = 0
        num_black_so_far = 0
        i = 0
        while i < len(matrix) and j < len(matrix[0]):
            if matrix[i][j] == 1: # 1 for white
                num_white_so_far += 1
                num_black_so_far = 0
                if num_white_so_far == 5:
                    white_win = True
            elif matrix[i][j] == 2: # 2 for black
                num_black_so_far += 1
                num_white_so_far = 0
                if num_black_so_far == 5:
                    black_win = True
            else:
                num_black_so_far = 0
                num_white_so_far = 0
            i += 1
            j += 1
    for j in range(1, len(matrix[0])): # direction of /, upper part
        num_white_so_far = 0
        num_black_so_far = 0
        i = 0
        while i < len(matrix) and j >=0:
            if matrix[i][j] == 1: # 1 for white
                num_white_so_far += 1
                num_black_so_far = 0
                if num_white_so_far == 5:
                    white_win = True
            elif matrix[i][j] == 2: # 2 for black
                num_black_so_far += 1
                num_white_so_far = 0
                if num_black_so_far == 5:
                    black_win = True
            else:
                num_black_so_far = 0
                num_white_so_far = 0
            i += 1
            j -= 1
    for i in range(1, len(matrix)): # direction of /, bottom part
        num_white_so_far = 0
        num_black_so_far = 0
        j = len(matrix[0]) - 1
        while i < len(matrix) and j < len(matrix[0]):
            if matrix[i][j] == 1: # 1 for white
                num_white_so_far += 1
                num_black_so_far = 0
                if num_white_so_far == 5:
                    white_win = True
            elif matrix[i][j] == 2: # 2 for black
                num_black_so_far += 1
                num_white_so_far = 0
                if num_black_so_far == 5:
                    black_win = True
            else:
                num_black_so_far = 0
                num_white_so_far = 0
            i += 1
            j += 1

    return (white_win, black_win)

if __name__ == "__main__":
    matrix = [[0] * 15 for _ in range(15)]
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            matrix[i][j] = random.randint(0,2)
    for r in matrix:
        print r
    print check_five(matrix)
\$\endgroup\$
4
\$\begingroup\$

Instead of checking every direction individually you could represent the directions as list of tuples (y-delta, x-delta) to the previous cell in this direction. Doing this would allow you to easily loop over the directions instead of processing them in separate branches.

DIRECTIONS = [
    (-1, -1), # Top left to bottom right
    (-1, 0),  # Top to bottom
    (-1, 1),  # Top right to bottom left
    (0, -1)   # Left to right
]

Since there are four different directions you could either loop over the matrix four times or alternatively calculate the distances in separate directions in parallel. The second approach would require you store all four directions for each cell in matrix.

Let's take a smaller matrix and see how second approach would work in practice:

matrix = [
    [1, 0, 0],
    [1, 2, 2],
    [1, 2, 0]
]

With above matrix the first cell at (0, 0) would have store [1, 1, 1, 1] since it's a first piece in line for every four directions. Since second cell doesn't have a piece it can't belong to a line of pieces of same color so we store 0 as distance for each direction: [0, 0, 0, 0]. Third cell on the first row is treated the same as the second one since it is empty: [0, 0, 0, 0].

After we have processed the first row our current state looks like this:

state = [
    [[1, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0]],
    [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
    [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
]

On the second row thing get bit more interesting sine we have to take into account the row we processed in previous step. At (1, 0) we check if the color matches each of the directions. If it does we take the previously stored and increment it, otherwise it's the first piece in line.

For first direction (-1, -1) the previous cell is (0, -1) which is out of bounds so this is the first piece in line for that direction thus we store 0. When checking the second direction (-1, 0) we see that there's a piece with same color at (0, 0). Thus we take the previous stored value from state[0][0][1] and increment it by one resulting to 2. Since there is no piece in previous cell in third direction and fourth direction is out of bounds they both result to 1.

Now our current state looks following:

state = [
    [[1, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0]],
    [[1, 2, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0]],
    [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
]

Cell (1, 1) is processed the same manner as earlier ones. The only difference compared to previous is that fourth direction (0, -1) has piece of different color. We treat this exactly the same as there would be empty space in previous location so we store 1 to state[1][1][3].

Once we have processed the whole matrix the end result looks like this:

state = [
    [[1, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0]]
    [[1, 2, 1, 1], [1, 1, 1, 1], [1, 1, 1, 2]]
    [[1, 3, 1, 1], [1, 2, 2, 1], [0, 0, 0, 0]]
]

The above takes roughly four times the memory of the original matrix. That is quite wasteful since we only need to know the state for current and previous row during the processing. Thus we could just store the state for previous and current row and swap them after a row in the matrix has been processed.

There are couple smaller enhancements to the original code as well:

  • Name the constants, EMPTY, WHITE & BLACK are much more descriptive than 0, 1 & 2
  • random.choice could be used to select piece for each cell
  • There's no need to populate the matrix with 0 before randomizing the cells
  • Instead of looping you could use pprint to print the matrix
  • Terminate early if both players win
  • Bug where diagonal line starting on the right side of the matrix was not detected has been fixed. You can reproduce the issue with matrix with line between (1, 14) and (5, 10)

Here's a version that implements the above algorithm:

import random
import pprint

EMPTY = 0
WHITE = 1
BLACK = 2
CELL_OPTIONS = [EMPTY, WHITE, BLACK]
WIN = 5
DIRECTIONS = [
    (-1, -1), # Top left to bottom right
    (-1, 0),  # Top to bottom
    (-1, 1),  # Top right to bottom left
    (0, -1)   # Left to right
]
CURRENT = 1   # Index of current row in state

def check_five(matrix):
    # Each cell in the state has counter for each direction,
    # only two rows are required since we can process the matrix
    # row by row as long as we know the status for previous row
    state = [[[0] * len(DIRECTIONS) for _ in matrix[0]] for _ in range(2)]
    white_win = False
    black_win = False

    for y, row in enumerate(matrix):
        # Swap rows in state that current (1) becomes previous (0)
        state = state[::-1]

        for x, color in enumerate(row):
            cell = state[CURRENT][x]
            for dir_index, (y_diff, x_diff) in enumerate(DIRECTIONS):
                prev_x = x + x_diff

                if color == EMPTY:
                    cell[dir_index] = 0
                elif 0 <= prev_x < len(row) and color == matrix[y + y_diff][prev_x]:
                    # There's a piece which doesn't match the previous one
                    # or previous was out of bounds
                    cell[dir_index] = state[CURRENT + y_diff][prev_x][dir_index] + 1
                else:
                    cell[dir_index] = 1

                if cell[dir_index] == WIN:
                    if color == WHITE:
                        white_win = True
                    else:
                        black_win = True

                    # Early termination if both win conditions met
                    if white_win and black_win:
                        return white_win, black_win

    return white_win, black_win

if __name__ == "__main__":
    matrix = [[random.choice(CELL_OPTIONS) for _ in range(15)] for _ in range(15)]
    pprint.pprint(matrix, indent=4)
    print check_five(matrix)
\$\endgroup\$
  • \$\begingroup\$ Hi niemmi, love your code and mark your reply as answer. I have a further idea to improve to store only one row data based on your idea, I post here => codereview.stackexchange.com/questions/154547/…, any advice is highly appreciated. \$\endgroup\$ – Lin Ma Feb 6 '17 at 4:41
4
\$\begingroup\$

A few suggestions:

  • Can both players win? If not, how do you decide which one to check first? If they can, if both of them have already won in the first check, no need to go on, just return True, True.
  • You are using a lot of hard-coded values (1, 2, 5) that are repeated through the code. I think it would be better to call them something like white_cell, black_cell, min_winning_cells.
  • The values can be only 0, 1 and 2, so random.choice could be better, also because...
  • ... You could use random.choice(['0', '1', '2']). Notice that these are strings, so it's sort of cheating maybe.

This way you could do something like:

white_winning_cells = '1' * 5
black_winning_cells = '2' * 5


def check_rows(rows):
    white_win = False
    black_win = False
    for row in rows:
        # Avoid overwriting
        white_win |= white_winning_cells in ''.join(row)
        black_win |= black_winning_cells in ''.join(row)
        if (white_win and black_win):
            return (white_win, black_win)
    return (white_win, black_win)

    def check_five(matrix):
        row_length = 15
        white_win = False
        black_win = False

        (white_win, black_win) = check_rows(matrix)
        if (white_win and black_win):
            return (white_win, black_win)

        # We need to avoid overwriting also here
        (white_win_temp, black_win_temp) = check_rows(zip(*matrix))
        white_win |= white_win_temp
        black_win |= black_win_temp

        return (white_win, black_win)

Of course you still need to add the code to put the diagonals in an array to check, but this is the general idea. Keep in mind that here I'm assuming a variable size matrix, but still square.

EDIT: As @Graipher noted, you need to use |= so you don't overwrite values. This has to be done in both the function and the caller. Also, for diagonals you can use the same code you have now to generate the arrays and pass them to the check_rows. You can also consider generating everything at once (rows, columns, diagonals), put them all in the same variable and call check_rows only once. But as I said, this is just a general idea.

\$\endgroup\$
  • \$\begingroup\$ Thanks ChatterOne, vote up for your reply and accepy your advice of for bulletin points. But I double your method of sub string match like white_winning_cells in ''.join(row) works more efficient than me, since in my code, I use dp to remember count, reduce re-counting. \$\endgroup\$ – Lin Ma Jan 25 '17 at 6:21
  • \$\begingroup\$ Also, how do you check diagonal? Did not find related code in your post. \$\endgroup\$ – Lin Ma Jan 25 '17 at 6:22
  • \$\begingroup\$ For your question, in my case, player can win at the same time. So there is a possible return of both sides win. \$\endgroup\$ – Lin Ma Jan 25 '17 at 6:48
  • \$\begingroup\$ @LinMa I edited my answer to include what Graipher said. \$\endgroup\$ – ChatterOne Jan 25 '17 at 13:37
  • \$\begingroup\$ Looks better. But you overindented the complete second function, making it an inner function, which is not what you want. \$\endgroup\$ – Graipher Feb 6 '17 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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