Particles That Vanish Where They Meet
An r by c grid holds n particles, each on its own cell and each heading in
one of four directions, given as 0 for north, 1 for east, 2 for south and
3 for west. North decreases the row. The walls reflect.
Every particle moves at the same instant. One tick, in order:
1. each surviving particle checks the cell it is heading into. If that cell is
outside the grid, the particle REVERSES first, so north becomes south and
east becomes west.
2. each particle then moves one cell in the direction it now faces.
3. any cell now holding TWO OR MORE particles loses all of them. They vanish
together and take no further part.
After exactly t ticks, print the grid as r lines of c characters, with
# on a cell holding a surviving particle and . everywhere else.
``` r = 3, c = 3, t = 1, one particle at (0,0) heading south and one at (2,0) heading north
both move into cell (1,0) on the same tick, so both vanish. -> ... ... ... ```
``` r = 3, c = 3, t = 4, one particle at (0,0) heading south
it goes to (1,0), (2,0), then reverses at the wall and goes to (1,0) and (0,0). Nothing to collide with, so it is back where it started. -> #.. ... ... ```
## What most people try first
Walking the particles one at a time and writing each into the grid as it moves. That makes the answer depend on the order you happened to walk them: a particle moved early can be seen by a particle moved later, and the collision rule then fires at the wrong moment or not at all. The statement says every particle moves at the SAME instant, so no particle may ever see another one's new position while deciding its own.
The shape that cannot get this wrong is to read only from the old state and write only to a new one:
for each tick:
new = []
for each particle: reverse if it must, then step, and append to new
count how many particles each cell of new holds
keep only the particles whose cell holds exactly one
The counting is a separate pass over new, after every particle has moved.
That is what makes the step simultaneous rather than sequential.
## Why the reflection must be decided before the move and not after
A particle on the bottom row heading south would leave the grid. Reversing
first means it moves north on that tick, so it is never outside the grid at any
point. Letting it step out and then pulling it back would place it two cells
from where the rule says, and on a grid of three rows that is the difference
between the second worked example returning to (0,0) and never returning at
all.
Note that a particle on the bottom row heading south and one on the row above heading north SWAP cells rather than meeting, so neither vanishes. The rule asks only about cells holding two or more particles after the move, so a swap is not a collision here. That is a decision, and it is made in the statement rather than left to the implementation.
## Why three or more can share a cell
Unlike a line, a grid cell can be entered from four sides, so three or even four particles can arrive together. The rule says all of them vanish, which is why the step counts particles per cell rather than pairing them up.
## Overflow
Everything here is small. The grid is at most 50 by 50, there are at most 50
particles, and t is at most 200, so at most 10000 moves happen in total.
Every value fits in a 32 bit integer with room to spare, and no test is tagged
as an overflow because none could be.
## Cost
O(t * (n + r * c)) time and O(n + r * c) memory.