Minesweeper Python coding challenge-CodePudding

Rules are super simple: We take as input a grid of where the mines are, and we output a grid where each cell represents the number of mines explicitly around it.

This means we need to check at 8 spots for each cell: Top left, Top Middle, Top Right, Middle Right, Middle Left, Bottom Left, Bottom Middle, and Bottom Right. If any of these cells contain a mine, the cell we are checking it for becomes the NUMBER of mines we have just counted.

Example Input:

input = ["OOOXXXOXX", "XXXXXXOXX", "XOOXXXXXX", "OOXXOXOXX", "XXXXXXXXX"]

For which we output:

2 3 4 X X X 4 X X
X X X X X X 7 X X
X 5 6 X X X X X X
3 5 X X 8 X 8 X X
X X X X X X X X X

Now here is my working solution:

def minesweeper(array):

    # Vertical iterations
    for lineIndex in range(len(array)):
        
        line = array[lineIndex]
        outputLine = []

        # Horizontal iterations
        for cellIndex in range(len(line)):
            
            # Check cell content
            if (line[cellIndex] == "O"):

                northIndex = lineIndex - 1
                eastIndex = cellIndex - 1
                southIndex = lineIndex   1
                westIndex = cellIndex   1

                verticals = [northIndex, lineIndex, southIndex]
                horizontals = [eastIndex, cellIndex, westIndex]

                counter = 0

                for v in verticals:
                    for h in horizontals:
                        if v >= 0 and h >= 0:
                            if array[v][h] == 'X':
                                counter  = 1

                outputLine.append(str(counter))

            else:
                outputLine.append("X")

        print(' '.join(outputLine))

I believe there must be a better solution in terms of space-time complexity and just in general. I was given 15 minutes to solve this in a coding challenge, and still can't figure out for the life of me how someone would have approached this.

CodePudding user response：

If you want to minimize space usage, use a generator to join each line of output rather than allocating a list. You might also get some constant-factor time wins by iterating over the lists with enumerate instead of doing the for index in range(...) thing, and minimizing the number of extra variables you allocate.

def minesweeper(array):
    for y, line in enumerate(array):
        print(' '.join(
            "X" if cell == "X" else str(sum(
                cell == "X"
                for line in array[max(0, y-1):min(len(array), y 2)]
                for cell in line[max(0, x-1):min(len(line), x 2)]
            )) for x, cell in enumerate(line)
        ))

It's still O(n) time with respect to array, though; it's not really possible to improve on that. Any solution is necessarily going to have to look at every cell in the board, which means it can never possibly be faster than O(n).

CodePudding user response：

An easy way to get to the adjacent positions is to prepare a list of offsets for the 8 neighbouring cells based on the row and column numbers. You can initialize a result matrix with a zero on "O" cells and "X" on the mine positions. Then a nested loop on each position can go through the offsets to add 1 to the 'zero' cells when the neighbouring position is in range of the board and contains an "X":

board = ["OOOXXXOXX",
         "XXXXXXOXX",
         "XOOXXXXXX",
         "OOXXOXOXX",
         "XXXXXXXXX"]

offsets = [ (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1) ]
result  = [ [[0,"X"][c=="X"] for c in row] for row in board] # initialize
for r,s in enumerate(board):  # go through board rows
    for c,m in enumerate(s):  # co through row's columns
        for dr,dc in [] if m=="X" else offsets: # neighbours of "O" cells
            if r dr in range(len(board)) and c dc in range(len(s)):
                result[r][c]  = board[r dr][c dc] == "X" # count bombs

Output:

for row in result:
    for c in row:
        print(c,end=" ")
    print()

2 3 4 X X X 4 X X 
X X X X X X 7 X X 
X 5 6 X X X X X X 
3 5 X X 8 X 8 X X 
X X X X X X X X X

If you want to avoid messing with indexes and offsets, you can prepare 8 shifted copies of the board (one per direction) and use zip() to combine them into a tuple of neighbours for each position. then count the number of Xs in the merged tuples:

emptyRow   = ["."*len(board[0])]
left       = [ "." row for row in board ]
right      = [ row[1:] "." for row in board ]
up         = emptyRow   board
down       = board[1:]   emptyRow
upLeft     = emptyRow   left
upRight    = emptyRow   right
downLeft   = left[1:]   emptyRow
downRight  = right[1:]   emptyRow
neighbours = (board,left,right,up,down,upLeft,upRight,downLeft,downRight)
result     = [ [n.count("X") if m=="O" else m for m,*n in zip(*rows)]
               for rows in zip(*neighbours) ]

for row in result:
    for c in row:
        print(c,end=" ")
    print()

2 3 4 X X X 4 X X 
X X X X X X 7 X X 
X 5 6 X X X X X X 
3 5 X X 8 X 8 X X 
X X X X X X X X X

This runs roughly 5x faster than the index/offset based solution