Python: Why is this algorithm not working as intended?

Question

I am stuck on a problem on Codefights. Here is the description:

In the popular Minesweeper game you have a board with some mines and those cells that don't contain a mine have a number in it that indicates the total number of mines in the neighboring cells. Starting off with some arrangement of mines we want to create a Minesweeper game setup.

Example

For

matrix = [[True, False, False],
      [False, True, False],
      [False, False, False]]

The output should be:

minesweeper(matrix) = [[1, 2, 1],
                   [2, 1, 1],
                   [1, 1, 1]]

So from what I understand, we have to look trough the whole matrix because we need to know which cells are True, i.e contains a bomb, then when we find one, all neighbouring cells' value should be incremented by 1. I first tried to write the code using if/elif statements for the border cells (to not throw an error) but the code became really ugly and long. So the only thing I could come up with was this:

def minesweeper(matrix):

# First creating the same matrix but instead full of zeros.
result = [[0]* len(matrix[0]) for row in matrix]

# Start iterating through the original matrix to find True elements
for y in range(len(matrix)):
    for x in range(len(matrix[0])):
        if matrix[y][x] == True:

            # The remaining code tries to increment all possible neighbours by 1.
            for j in range(-1,2):
                for i in range(-1,2):

                    # If statement so that we do not increment the bomb cell itself.
                    if not (j == 0 and i == 0):
                        try:
                            result[y+j][x+i] += 1
                        except:
                            continue
return result

The output of my function for

input = [[True, False, False],
        [False, True, False],
        [False, False, False]]

is

[[1, 2, 2], [2, 1, 2], [2, 2, 2]]

Anyone has an idea why it doesnt work? And I also know that you should try to catch error with try/except statements and that this probably is bad practice, I just couldnt figure out another way without the super long if/elif statements.

Please fix your example further: the lowercase `true` and `false` should be strings (i.e. "true" and "false") or capitalized. Also, `yi` and `xi` in you inner loop are actually not defined. So, your code looks broken. — alisianoi, Aug 01 '17 at 12:55
Possible duplicate of [List of lists changes reflected across sublists unexpectedly](https://stackoverflow.com/questions/240178/list-of-lists-changes-reflected-across-sublists-unexpectedly) — Łukasz Rogalski, Aug 01 '17 at 13:01
@ŁukaszRogalski it is not a duplicate. The result-variable is correctly initialized. — Enfenion, Aug 01 '17 at 13:08

Bojan P. · Answer 1 · 2017-08-02T03:38:00.690

Another possible way to limit the ranges while executing len, min and max functions only once and without checking if cell is the cell itself on every point (iteration):

true = True  # or "true"
false = False  # or "false"

matrix = [[true, false, false],
          [false, true, false],
          [false, false, false]]


def minesweeper(matrix):
    # First creating the same matrix but instead full of zeros.
    result = [[0] * len(matrix[0]) for row in matrix]

    # Start iterating through the original matrix to find "true" elements
    y_max = len(matrix)
    for y in range(y_max):
        x_max = len(matrix[0])
        for x in range(x_max):
            if matrix[y][x] == true:
                # The remaining code increments all neighbours by 1, but not beyond the matrix size!
                for dy in range(max(0, y - 2), min(y_max, y + 2)):
                    for dx in range(max(0, x - 2), min(x_max, x + 2)):
                        result[dx][dy] += 1
                # Do not increment the bomb cell itself (it was).
                result[y][x] -= 1

    return result

And print(minesweeper(matrix)) gives the desired result [[1, 2, 1], [2, 1, 1], [1, 1, 1]].

score 0 · Accepted Answer · answered Aug 01 '17 at 12:55

I think your problem is that accessing a value using a negative index a valid operation in Python. Hence, when processing the first element, you would increase the last element in the result-matrix.

You should try to debug your code in smaller steps, either by stepping through it using the debugger, or stopping and checking out the values after the first iteration of x and y.

score 0 · Answer 3 · answered Aug 01 '17 at 13:25

With the help of the accepted answer the following code worked. And the try/except statements were competely useless since the code inside it never threw an error anyways.

def minesweeper(matrix):
    result = [[0]* len(matrix[0]) for row in matrix]

    for y in range(len(matrix)):
        for x in range(len(matrix[0])):
            if matrix[y][x] == True:
                for j in range(-1,2):
                    for i in range(-1,2):
                        if not (j == 0 and i == 0) and not ((y+j) < 0 or (x+i) < 0):    
                            result[y+yi][x+xi] += 1
    return result

score 0 · Answer 4 · answered Oct 10 '21 at 09:58

This is my proposal to solve this problem.

def minesweeper(matrix):
    minercount = [[0 for x in range(len(matrix[0]))] for y in range(len(matrix))] 
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == True:
                for di in range(i-1, i+2):
                    for dj in range(j-1, j+2):
                        if (di < 0 or dj < 0 or di >= len(minercount) or dj >= len(minercount[0]) or (di == i and dj == j) ):
                            continue
                        else:
                            minercount[di][dj] += 1
    return minercount

Python: Why is this algorithm not working as intended?

4 Answers4