The Ant That Repaints the Floor
Every square of an r by c grid starts WHITE. An ant stands on row sr,
column sc facing NORTH, where north is row minus one. One step is three
things, in this order and no other:
if the square under the ant is white:
turn a quarter turn clockwise, paint the square black, move forward one
if the square under the ant is black:
turn a quarter turn anticlockwise, paint the square white, move forward one
The grid WRAPS on all four edges, so moving off the top arrives at the bottom
and moving off the left arrives at the right. After exactly k steps, print how
many squares are black, then the ant's row, column and facing.
``` 3 by 3, ant at 1 1, k = 1 -> 1 1 2 E
the square was white, so the ant turned clockwise from north to east, painted 1 1 black, and moved east to 1 2 ```
## What most people try first
Any other order. Painting before turning, or moving before painting, or turning after moving: each of the five wrong orders produces a plausible answer and all of them differ from this one within a handful of steps. There is no algorithm to get right here, only an order, and the order is the problem. A good habit is to write the three lines in the order the statement gives them and never reorder them for convenience.
The second instinct is to think a pattern will appear and shortcut it. The ant's
trail on a wrapping grid is genuinely chaotic for thousands of steps; there is
no closed form to reach for, and k is small enough to simply obey.
## The turn, written out
Facing is a quarter turn, so hold it as an index into the four headings in clockwise order, north first:
headings = [(-1,0), (0,1), (1,0), (0,-1)] N E S W
clockwise: d = (d + 1) mod 4
anticlockwise: d = (d - 1 + 4) mod 4
The + 4 is needed in C, C++, Java and JavaScript, where -1 mod 4 is -1.
The same applies to the wrap: write (row + dr + r) mod r, because (0 - 1) mod r
is -1 in those four languages and the next read is out of bounds.
## Why the black count cannot be derived from k
Each step flips exactly one square, so after k steps the number of flips is
k. That does not make the number of black squares k or k mod 2 or anything
else in k alone, because a square flipped twice is white again and the ant
revisits squares constantly, especially on a small wrapping grid. Keep the
colours and count them, or carry a running total that goes up on a white square
and down on a black one. The declared test on a two by two grid after eight
steps answers 0, which is the case that kills every formula in k.
## Cost
O(r c + k): constant work per step, with the grid of colours costing
O(r c) memory.