Skip to content

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