Mark Every Square the Robot Stood On
A robot starts at row 0, column 0 of an r by c grid, facing EAST. Row 0 is
the top row and column 0 is the leftmost column. It reads a string of commands:
L turn a quarter turn anticlockwise, without moving
R turn a quarter turn clockwise, without moving
F move one square forward in the direction it is facing
If the square in front is outside the grid, the F does nothing: the robot
stays put and keeps facing the same way. Print the grid with * on every square
the robot has ever stood on, including the one it started on, and . everywhere
else.
r = 3, c = 3, "FF" r = 3, c = 3, "FFRFF"
*** ***
... ..*
... ..*
## What most people try first
Mark the square only when the robot arrives somewhere new, and forget the starting square. The grid then comes back with its first cell empty whenever the commands never bring the robot back to it, which is almost always. The starting square is occupied at time zero, before any command runs, so it is marked before the loop starts.
The second common first attempt is to let F move the robot and then clamp the
coordinates back inside the grid. That is not the same rule: clamping leaves the
robot against the edge, which is where it already was, so the position happens
to come out right, but it also marks the clamped square as a new visit and it
hides the case where the robot was NOT at the edge. Test the destination before
moving.
## Turning without moving
Hold the facing as an index into the four headings in clockwise order, starting at north, in grid coordinates where north decreases the row:
headings = [(-1,0), (0,1), (1,0), (0,-1)] N E S W
L: d = (d - 1 + 4) mod 4
R: d = (d + 1) mod 4
The + 4 before the modulo matters in C, C++, Java and JavaScript, where
-1 mod 4 is -1 and the heading lookup then reads off the front of the array.
The robot starts facing east, which is index 1, not index 0.
## Why the trail cannot be reconstructed afterwards
It is tempting to record only the robot's path as a list of turning points and
fill in the straight runs at the end. That works only while the runs are
straight and inside the grid, and a refused F makes the path stop without a
turn. Marking each square as it is occupied cannot get that wrong, because it
records exactly what the specification says: the squares the robot stood on.
## Cost
O(r c) to build and print the grid plus O(1) per command, so
O(r c + m) in total for m commands.