Making two identical robots meet on a line
Question
Two robots parachute onto different points of an infinite integer line, leave their parachutes where they land, and then run the same program. The only instructions are: step left, step right, jump to a line label, and jump to a label if the current square has a parachute. Write a program that guarantees they eventually meet.
Short answer
Walk slowly one way until you find a parachute, then speed up. Loop A: step right, step left, step right, and if on a parachute jump to loop B, else repeat A. Loop B: step right, repeat. Both drift right at the slow rate; the one behind reaches the other's parachute, switches to the fast loop and closes the gap, so they meet.
Adapted from Joshi, Denson & Downes, Quant Job Interview Questions and Answers, Q5.18, p.159; question and answer rewritten by SelfMadeQuant.com.
See the hint and the full worked solution in the question bank (free account).
Open the worked solution