The Step Where Two Walkers Meet
Two walkers stand on a grid with no edges. Each has its own command string, and the two strings have the SAME length. On every step both walkers move AT THE SAME INSTANT, one square each:
N y + 1 S y - 1
E x + 1 W x - 1
Print the number of the first step AFTER WHICH both walkers stand on the same
square, counting steps from 1. If they already share a square before any step,
print 0. If they never share a square, print -1.
A at 0 0 with "EE", B at 2 0 with "WW" -> 1
A at 0 0 with "EE", B at 1 0 with "EE" -> -1 B stays one ahead forever
A at 0 0 with "N", B at 0 0 with "S" -> 0 together before the first step
## What most people try first
Move one walker, test, then move the other, test. That is the wrong simulation,
and it reports meetings that do not happen. With A at 0 0 going east and B at
1 0 going east, moving A first puts it on 1 0 while B is still there, and a
test at that moment says they met. They did not: B left at the same instant A
arrived. Move BOTH, then test once.
## Passing through each other is not a meeting
With A at 0 0 going east and B at 1 0 going west, after one step A is at
1 0 and B is at 0 0. They swapped. The specification asks for the same
SQUARE after a step, and after that step they are on different squares, so the
answer is not 1. The declared test 0 0 1 0 with E and W pins it, and a
solution that also checks for a swap gets it wrong.
## The loop
if A and B start on the same square: answer 0
for i from 1 to length:
move A by command i
move B by command i
if A and B are on the same square: answer i and stop
answer -1
Stopping at the FIRST such step matters: the walkers may meet several times and only the earliest is wanted. Because the loop returns as soon as the test succeeds, no later meeting can overwrite the answer.
## Cost
O(L) for strings of length L, with O(1) memory. Nothing has to be stored,
because only the two current positions decide the test.