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[i].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
'-', which means that the cell is empty
the author of the statement has strange choices, I would have used a space for an empty cell ;-)
Concerning your problem :
first apply_gravity moves the boxes too fast.
If you print the position of the boxes at the end of apply_gravity, and for instance a column does not have an obstacle, you will see that all the boxes of this column immediately move to the bottom.
The consequence is, moving too fast a box does not explode when it has to do, because it is not at the right level.
and you also have to manage the movement of the boxes and the explosion at the same time
A proposal from yours :
def solution(board):
rows = len(board)
cols = len(board[0])
# helper: Apply one step of gravity to all columns from the bottom
# (boxes fall down without an obstacle)
# explosion_pos is updated to contain the list of obstacle
# positions producing the explosion of a cell
# Returns False if no cell moves nor explodes
def apply_gravity(explosion_pos):
something_new = False
for c in range(cols):
for r in reversed(range(rows - 1)):
if board[r][c] == '#':
if board[r+1][c] == '-':
# can go down
something_new = True
board[r+1][c] = '#'
board[r][c] = '-'
elif board[r+1][c] == '*':
# explosion
something_new = True
explosion_pos.append((r+1,c))
return something_new
# offsets for 3x3 neighborhood around an obstacle position
directions = [(-1,-1), (-1,0), (-1,1),
(0,-1), (0,1),
(1,-1), (1,0), (1,1)]
# main loop, loops while something happened to at least a cell
while True:
explosion_pos = []
if not apply_gravity(explosion_pos):
break # all stable
for r,c in explosion_pos:
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == '#':
board[nr][nc] = '-'
return board
def wr(board):
for r in board:
print(r)
print()
board = [['#', '-', '#', '#', '*'],
['#', '-', '-', '#', '#'],
['-', '#', '-', '#', '-'],
['-', '-', '#', '-', '#'],
['#', '*', '-', '-', '-'],
['-', '-', '*', '#', '-']]
print("start board")
wr(board)
print("end board")
wr(solution(board))
print()
board = [['#', '#', '*'],
['#', '-', '*'],
['#', '-', '*'],
['-', '#', '#'],
['*', '-', '#'],
['*', '-', '-'],
['*', '-', '-']]
print("start board")
wr(board)
print("end board")
wr(solution(board))
Execution :
bruno@raspberrypi:/tmp $ python board.py
start board
['#', '-', '#', '#', '*']
['#', '-', '-', '#', '#']
['-', '#', '-', '#', '-']
['-', '-', '#', '-', '#']
['#', '*', '-', '-', '-']
['-', '-', '*', '#', '-']
end board
['-', '-', '-', '-', '*']
['-', '-', '-', '-', '-']
['-', '-', '-', '-', '-']
['-', '-', '-', '-', '-']
['-', '*', '-', '-', '#']
['#', '-', '*', '-', '#']
start board
['#', '#', '*']
['#', '-', '*']
['#', '-', '*']
['-', '#', '#']
['*', '-', '#']
['*', '-', '-']
['*', '-', '-']
end board
['-', '-', '*']
['-', '-', '*']
['-', '-', '*']
['-', '-', '-']
['*', '-', '-']
['*', '-', '#']
['*', '-', '#']
bruno@raspberrypi:/tmp $
and even if I print the boards the execution time on my Pi5 (Debian Bookworm 64b) is around 0.03 seconds.