[Python] Couldn't solve this gravity simulation problem

I recently tried to solve this problem to no avail. Anyone know what to do?

You are running a gravity simulation involving falling boxes and exploding obstacles. The scenario is represented by a rectangular matrix of characters board.

Each cell of the matrix board contains one of three characters:

'-', which means that the cell is empty; '*', which means that the cell contains an obstacle; '#', which means that the cell contains a box. The boxes all fall down simultaneously as far as possible, until they hit an obstacle, another grounded box, or the bottom of the board. If a box hits an obstacle, the box explodes, destroying itself and any other boxes within eight cells surrounding the obstacle. All the explosions happen simultaneously as well.

Given board, your task is to return the state of the board after all boxes have fallen.

Note: You are not expected to provide the most optimal solution, but a solution with time complexity not worse than O(board[0].length · board.length2) will fit within the execution time limit.

Example

For

board = [['#', '-', '#', '#', '*'],
['#', '-', '-', '#', '#'],
['-', '#', '-', '#', '-'],
['-', '-', '#', '-', '#'],
['#', '*', '-', '-', '-'],
['-', '-', '*', '#', '-']]


the output should be

solution(board) = [['-', '-', '-', '-', '*'],
['-', '-', '-', '-', '-'],
['-', '-', '-', '-', '-'],
['-', '-', '-', '-', '-'],
['-', '*', '-', '-', '#'],
['#', '-', '*', '-', '#']]


For

board = [['#', '#', '*'],
['#', '-', '*'],
['#', '-', '*'],
['-', '#', '#'],
['*', '-', '#'],
['*', '-', '-'],
['*', '-', '-']]


the output should be

solution(board) = [['-', '-', '*'],
['-', '-', '*'],
['-', '-', '*'],
['-', '-', '-'],
['*', '-', '-'],
['*', '-', '#'],
['*', '-', '#']]


Input/Output

[execution time limit] 0.5 seconds (cpp)

[memory limit] 1 GB

[input] array.array.char board

A matrix that shows where the boxes and obstacles are located. The matrix consists only of characters '-', '*', and '#'.

Guaranteed constraints: 3 ≤ board.length ≤ 100, 3 ≤ board.length ≤ 100.

[output] array.array.char

Return a matrix representing the state of the board after all of the boxes have fallen.

Here is what I tried:

def solution(board):
rows = len(board)
cols = len(board[0])

# helper: apply gravity to all columns (boxes fall down within obstacle-separated segments)
def apply_gravity():
for c in range(cols):
write_row = rows - 1
r = rows - 1
while r >= 0:
if board[r][c] == '*':
# obstacle blocks - next write position is just above it
write_row = r - 1
r -= 1
elif board[r][c] == '#':
if write_row != r:
board[write_row][c] = '#'
board[r][c] = '-'
write_row -= 1
r -= 1
else: # empty
r -= 1

# main loop: gravity -> find explosions -> remove -> repeat until no explosions
while True:
apply_gravity()

to_destroy = set()
# offsets for 3x3 neighborhood
directions = [(-1,-1), (-1,0), (-1,1),
(0,-1), (0,0), (0,1),
(1,-1), (1,0), (1,1)]

# mark explosions only for obstacles that have a box directly above them
for r in range(rows):
for c in range(cols):
if board[r][c] == '*':
if r - 1 >= 0 and board[r - 1][c] == '#':
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == '#':
to_destroy.add((nr, nc))

if not to_destroy:
break # stable — no more explosions

# apply destruction and then loop again (so remaining boxes can fall further)
for (r, c) in to_destroy:
board[r][c] = '-'

return board

Continue reading...