Algorithm challenge: Robots on a Line The solution is small and elegant.

[Mickey]

Two robots are placed at different points on a straight line of
infinite length. When they are first placed down, they each spray out
some oil to mark their starting points.

You must program each robot to ensure that the robots will eventually
crash into each other. A program can consist of the following four
instructions:

* Go left one space
* Go right one space
* Skip the next instruction if there is oil in my current spot
* Go to a label

[Note that a "label" is a name that refers to a line of your code. For
example, you could label the third line of your program "surveying".
Then, the instruction "goto surveying" would jump to line 3 and start
executing from there on the next cycle.]

A robot will carry out one instruction per second. Both robots need
not have the same program. Note that you won't know ahead of time
which robot is on the left and which is on the right.

Regards,
Jyoti

Turing machine.

[Mickey]

The solution to this problem is to just have both robots move
consistently in one direction, but not at full speed. Then, have
either robot pick up to full speed when it sees oil again (which will
only happen for one robot). This robot will eventually catch up to the
other robot, causing a collision.

Regards,
Jyoti

[SUDHEER DURUSOJU]

Jyoti,

Solution is interesting. You did not mentioned anything about speed in the problem. Should we assume that the oil spill is causing the robot to speed up ?

-Sudheer.

[Mickey]

Hi Sudheer,

slow can be imagined like this,
When both decide to move to the east/left/north:
move two steps in chosen direction and then move one step in reverse.
That way we are advancing only one step in three cycles. And when one
finally comes across an oil it can start start advancing three steps
in three cycles... thereby 'speeding up'.

Regards,
Jyoti