Settle the Sandpile
Each cell of grid (a list of rows) holds a number of grains of sand. A cell with 4 or more grains is unstable and topples: it loses 4 grains and each of its side neighbours (up, down, left and right) gains 1 grain. Grains pushed over the edge of the grid fall off and are lost. A topple can make neighbouring cells unstable, so keep toppling unstable cells, one at a time and in any order, until every cell holds at most 3 grains. The final grid is the same whatever order you choose. Return it as a new grid, leaving grid itself unchanged.
Example 1
The centre topples once and gives one grain to each of its four side neighbours.
Example 2
The bottom-right cell topples first and pushes two grains over the edge. That makes its neighbours unstable one after another, and the chain ends with 1, 1, 1 and 2 grains.
Constraints
1 <= rows, cols <= 100 <= grid[r][c] <= 12
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Grids problems
- Slide and MergeMedium
- Snake GameMedium
- Spiral FillMedium
- Spiral OrderMedium
- Spiral Out From a CellMedium
- Sudoku Rules CheckMedium
- Turn Every RingMedium
- Zigzag DiagonalsMedium