FunctionRacerProblemsRace

Settle the Sandpile

MediumGridsPython, JavaScript, TypeScript, Java, C++

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

grid [[0,0,0],[0,4,0],[0,0,0]]
returns [[0,1,0],[1,0,1],[0,1,0]]

The centre topples once and gives one grain to each of its four side neighbours.

Example 2

grid [[3,3],[3,4]]
returns [[1,1],[1,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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Grids problems