Let the Sand Settle
A grid holds three kinds of cell:
o a grain of sand
. empty space
# a solid block, which never moves
Gravity pulls every grain straight down, within its own column, until it rests on the floor, on a block, or on another grain. Sand never moves sideways. Print the settled grid.
.o. ...
... -> ...
... .o.
o.o ...
.#. -> .#.
o.o o.o
... o.o
In the second example the left column has two grains that stack at the bottom, and the right column is the same; the block in the middle column is not in either falling path.
## What most people try first
Repeat a pass over the whole grid moving every grain down one square, until a
pass changes nothing. That is correct, and it is O(r) passes of O(r c) work,
so O(r^2 c): at 1000 by 1000 that is 10^9 cell visits.
It is worth writing once, because it is also the easiest thing to be sure of, and the reference oracle uses exactly it to check the fast method.
## Each column is independent, so sweep it once
Sand never moves sideways, so the columns do not interact at all and each can be settled on its own. Walk a column from the BOTTOM upwards, keeping a pointer to the lowest free cell:
for each column:
write = bottom row
for row from bottom to top:
if the cell is '#': write = row - 1 nothing falls past a block
if the cell is 'o': clear it, put 'o' at write, write = write - 1
One pass per column, so O(r c) in total.
## Why the sweep must go upwards
Going downwards means a grain can be moved into a cell that a later step then
examines again, so one grain falls repeatedly in a single pass and overtakes
grains below it. Sweeping upwards, every cell is read exactly once and the
write pointer only ever moves up, so each grain is placed once and never
revisited.
That is the same discipline as problem 2127, where cells had to be read from the previous generation. Here it is achieved by the direction of the sweep rather than by a second grid.
## The block resets the pointer
When the sweep meets #, the lowest free cell becomes the row ABOVE it, not the
bottom of the grid. Forgetting that lets sand fall through solid blocks, which
the declared test with a block between two grains catches.
## Cost
O(r c), one pass per column, with O(1) extra memory beyond the grid itself.