Where the Robot Ends Up
A robot starts at coordinate 0 0 facing NORTH. It reads a line of commands,
one character each:
L turn 90 degrees anticlockwise, without moving
R turn 90 degrees clockwise, without moving
F move one step in the direction it is facing
B move one step BACKWARDS, without turning
Print its final position and the direction it is facing.
North increases y, east increases x. So from 0 0 facing north, F moves
to 0 1, and R then F moves to 1 1 facing east.
FF -> 0 2 N
FRFRFRFR -> 0 0 N a full square, back where it started
L -> 0 0 W turning does not move
## The thing to get right
Turning and moving are separate. B moves backwards WITHOUT changing the
direction the robot faces, so after B the robot is behind where it was but
still looking the same way. A solution that implements B as "turn around,
move, turn back" gets the position right and is harder to read; one that
implements it as "turn around and move" gets the final direction wrong.
## Two ways to hold the direction
Either as an index into a list of the four headings, turning by adding or subtracting 1 modulo 4:
DIRS = [(0,1), (1,0), (0,-1), (-1,0)] north, east, south, west
L: d = (d - 1 + 4) mod 4
R: d = (d + 1) mod 4
or as a vector (dx, dy) rotated directly:
L: (dx, dy) becomes (-dy, dx)
R: (dx, dy) becomes (dy, -dx)
Both are used by the reference solutions and the oracle checks them against each
other. The index version needs the + 4 before the modulo in languages where
-1 mod 4 is -1 rather than 3, which is C, C++, Java and JavaScript. Python
is the exception. That single difference is the most common bug in this problem.
## The order of the four directions matters
The list must be in rotational order, so that adding 1 really is a quarter turn
clockwise. Writing them in a different order, say north, south, east, west,
makes R jump two quarters at a time and the whole thing silently wrong.
## Why it is correct
There is no shortcut being claimed here, so what has to be argued is that the two representations above agree, since the reference solutions use both and a student may use either.
Index d stands for the heading (DX[d], DY[d]) with the list in clockwise
order starting at north. Write the vector as (dx, dy). A clockwise quarter
turn is the map (dx, dy) -> (dy, -dx): check it on one heading and the rest
follow, because applying the same map repeatedly walks the list. North is
(0, 1), and the map sends it to (1, 0), which is east, which is the next
entry; east goes to (0, -1), south; south goes to (-1, 0), west; west goes
back to (0, 1), north. So the map is a cyclic shift by one along the same
list that d = (d + 1) mod 4 shifts, and the two agree after any number of
turns. Anticlockwise is the inverse map (dx, dy) -> (-dy, dx), matching
d - 1.
Position then follows, because each F adds the current heading and each B
subtracts it, and neither touches d. The final position is the sum of those
signed headings in command order, which is what one pass accumulates. Order
matters within that sum, since the heading in force changes as turns are read,
which is why there is no closed form to replace the loop.
## Cost
O(number of commands), one pass, with O(1) memory.