Programming Challenge: Robot Search

Programming Challenge: Robot Search

Assume that two robots land from two different
flights with the help of parachuttes (at different
points) on an infinite plane.

Each robot leaves its parachutte on landing and goes in
search of the other robot. The problem is to write a
program which will be executed by both the robots for
rendevezvous(meeting).

You have the following instructions at your disposal
to write the program:

1) Step L - makes the robot take one step towards left
2) Step R - makes the robot take one step towards right
3) goto label - jump to the label
4) if P one instruction, where
P is a predicate which will be true when a robot senses a
parachutte. It will be true as long as the robot is near it.
The moment it takes a step towards left or right after sensing it,
then P will become false.

As part of 'if' statement one can execute one instruction which could be
(1) or (2) or (3)

Could anybody write a program to help the robots to
meet :)? Make your own assumptions and justify them.

Remember the same program needs to be executed by both robots :-)

Till Now One Answer Found:

Assumptions:

1) Both the robots are aligned in straight line.

2) Each "Step"(L/R) instruction takes O(1) time. 3) Time taken by the other statements are negligible.

1) Label A:

2) If P goto B;

3) Step L;

4) Step L;

5) Step R;

6) goto A;

7) Label B:

8) Step L;

9) Goto B;

This code runs in both the robots. Instructions 1-6 execute until robot on the right side finds the robot on the left side. Here for each one step movement we are actually making three steps. Its actually done to perform "1 step left" in O(3) time until any of the parachute is found. If the right side robot finds the parachute it moves to the "Instruction 7" which keep on moving the right robot "1 step left" in O(1) time. Now the left side robot is moving "1 step left in O(3) time" where as the right side robot is moving at a speed of "3 step left in O(3) time". Hence the right side robot will catch the left side robot after a considerable amount of time. Lets say that the time passed till right robot found the parachute be "x" units. Now the right robot will find the left one in another cei(x/2) units.