Arrows Painted on the Floor
An r by c grid has an arrow painted on some squares and nothing on the
others:
^ north, meaning row - 1 v south, meaning row + 1
< west, meaning column - 1 > east, meaning column + 1
. nothing painted
A robot starts on row 0, column 0 facing a given direction. Row 0 is the top row. One tick is:
1 if the square the robot is standing on has an arrow,
the robot turns to face that arrow's direction
2 the robot moves one square in the direction it is now facing
If the move in step 2 takes the robot outside the grid it has escaped. Print
EXIT t, where t counts every tick including the one that carried it out. If
the robot can never escape, print LOOP.
2 2, facing east 2 2, facing south
>v v.
^< >.
LOOP EXIT 3
## What most people try first
Run the simulation and stop after some large round number of ticks, say a
million, calling it a loop. That is a guess rather than an argument, and the
problem then has two failure modes at once: too small a bound reports LOOP for
a robot that would have escaped, and too large a bound is slow for no reason.
## The state is small, which settles it
Everything the next tick depends on is the triple (row, column, facing). The
grid never changes, and the rule is deterministic, so the same triple always
produces the same next triple. There are exactly 4 r c triples. Therefore:
- if the robot runs for more than
4 r cticks it must have repeated a triple, - and from that point it is replaying a sequence it has already walked, so it
- will never escape;
- and if it escapes at all, it escapes within
4 r cticks.
That gives two correct implementations. Remember every triple seen and stop the
moment one repeats, which is O(r c) time and O(r c) memory; or simply run
for 4 r c + 1 ticks and report LOOP if the robot is still inside, which is
O(r c) time and O(1) extra memory. The reference solutions use the first
and the oracle checks it against the second.
## Why the facing has to be part of the state
Position alone is not enough. A robot can stand on the same blank square twice
while facing differently, and those two visits have different futures, so
treating position alone as the state declares a loop that is not there. With
4 r c states and r, c up to 500 that is a million entries, which is why the
visited marks are a flat array of bytes rather than a hash set.
## Cost
O(r c) time and O(r c) memory, since the robot takes at most 4 r c ticks
and each tick is a constant amount of work.