A puzzle game's board is a grid of coloured bubbles. board[r][c] is a positive colour id, or 0 for an empty cell. Row 0 is the top. Two cells are neighbours when they share a side (up, down, left, right; not diagonals).
Implement settle(board: list[list[int]]) -> list[list[int]], which plays the board out and returns the final grid. The input may have bubbles floating above empty cells, so first let everything fall (step 3 below). Then repeat these rounds until a round pops nothing:
- Find unstable bubbles. A bubble is unstable if at least two of its neighbours have the same colour as it.
- Pop, all at once. Every unstable bubble pops, and so does every same-coloured neighbour of an unstable bubble. All the pops of a round are decided from the board as it was at the start of the round, then applied together (the popped cells become
0). - Fall. In every column, the remaining bubbles drop straight down to fill the empty cells below them, keeping their top-to-bottom order.
Return a new grid with the same shape. Don't modify board.
settle([[1, 2, 2],
[3, 2, 1],
[3, 3, 1]])
# Round 1: the top-middle 2 has two 2-neighbours, so it and both of them pop.
# The bottom-left 3 has two 3-neighbours, so all three 3s pop.
# The 1s each have only one 1-neighbour and stay.
# After falling:
# [[0, 0, 0],
# [0, 0, 1],
# [1, 0, 1]]
# Round 2 pops nothing, so this is the answer.
Popping can cause chain reactions: bubbles that fall may land next to others of their colour and become unstable in the next round.
Constraints: 1 <= rows, cols <= 60, colours between 1 and 10^6.
Show hint
Each round, build a separate pop grid of booleans first (mark each unstable cell and its same-coloured neighbours), then clear the marked cells, then compact each column from the bottom up with a write pointer. Stop when a round marks nothing.