How Many Squares the Walk Touches
A walker starts at 0 0 on a grid with no edges and takes one step for each
character of a command string:
N y + 1 S y - 1
E x + 1 W x - 1
Print how many DISTINCT squares the walker has occupied, counting the starting square and counting a square once however many times it is revisited.
NNEE -> 5 four steps, five squares, none repeated
NSNSNS -> 2 it only ever stands on 0 0 and 0 1
N -> 2 the start and one more
## What most people try first
Count the steps, or count the steps and subtract something. There is no formula
in the number of steps: NNEE and NSNSNS are both four or six characters and
give completely different answers, because what matters is which squares repeat
and that depends on the shape of the path, not its length.
The other first attempt is to keep a list of visited squares and scan it for
each new one. That is correct, and it is O(m^2) for m steps: at the stated
limit of 50000 steps it is 2.5 billion comparisons.
## Hold the visited squares in a set
A square is a pair, and a set of pairs answers "have I been here" in constant time:
seen = { (0, 0) }
for each command:
move x and y
put (x, y) into seen
answer = size of seen
Putting the start in BEFORE the loop is not decoration. A walk of zero steps
still occupies one square, and more importantly a walk that returns to 0 0
must not count it a second time, which it will if the start is only added when
the walker arrives back at it.
## Packing a pair into one number
Languages without a pair key, which here means C, need the two coordinates in
one value. After m steps neither coordinate can be further from zero than
m, because every step changes exactly one of them by one. So with m at most
50000, shifting by 100000 makes both non-negative and
key = (x + 100000) * 300001 + (y + 100000)
is distinct for distinct squares and never exceeds about 6 * 10^10. That needs
64 bits, and in JavaScript it is still exact because it is far below 2^53. Do
not build the key with shifts in JavaScript: a bitwise operator truncates to 32
bits and would collapse different squares onto the same key.
## Cost
O(m) steps with O(m) memory for the set. Sorting the keys and counting
equal runs instead is O(m log m) and is what the C reference does.