A Walker Bouncing Between Four Walls
A walker is inside an r by c grid at row sr, column sc, carrying a
velocity (dr, dc) where each of dr and dc is either -1 or 1. One tick
does exactly this, in this order:
1 if row + dr is outside the grid, dr = -dr
2 if row + dr is now inside, row = row + dr
3 if col + dc is outside the grid, dc = -dc
4 if col + dc is now inside, col = col + dc
Print the row, the column, dr and dc after exactly t ticks.
``` r = 3, c = 3, start 0 0, velocity 1 1, t = 2 -> 2 2 1 1 r = 3, c = 3, start 0 0, velocity 1 1, t = 4 -> 2 2 -1 -1
at t = 2 the walker has just arrived in the far corner and is still pointing into it; the flip happens on the tick that tries to leave ```
## What most people try first
Move, then if the walker has left the grid, flip the velocity and put it back. That is a different rule and it gives a different answer. Moving and repairing makes the walker spend the tick that touches the wall standing still after a flip, while the stated rule flips BEFORE moving and so never leaves the grid at all. The two disagree about the sign of the velocity whenever a tick ends against a wall, which is why the velocity is part of the required output: it is the only way to see that the flip is lazy.
## Why step 2 can fail
Step 1 flips dr when the move would leave the grid, and step 2 then checks
AGAIN. The second check is not redundant. With r = 1 there is only one row,
so row + 1 and row - 1 are both outside, and after the flip the move is
still illegal: the row simply does not change that tick, while dr has been
flipped. A solution that trusts the flip and moves unconditionally steps to row
-1 and reads out of bounds. A single row or a single column is a declared
test for exactly this.
## The two axes never interact
Nothing in the rule lets the row affect the column or the other way round, so
the row with dr and the column with dc can be advanced by the same
one-dimensional routine called twice. That is worth noticing because it halves
the code and because it is the fact a closed-form solution would rest on: on one
axis the walker's path is a triangle wave of period 2(r - 1). The reference
solutions simulate, since t is at most 200000.
## Cost
O(t) with O(1) memory. The grid is never stored: only the position and the
velocity matter.