## Saturday, May 10, 2014

### Robots on a line

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.

### Solution

The first thought most people have it to try to get each robot to go back and forth, centered on their original spot, each time going a little further out in each direction. This won't work.

Another insight is that since you don't know which robot will be on the left or right, it probably doesn't make sense to give them different programs.

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.
Here is a working program, which you will give to both robots. Note that our "move_slowly" section is able to move slowly by moving an extra right and left space.

[Label: move_slowly]
1 Move Right
2 Move Right
3 Move Left
4 Skip Next Instruction If On Oil
5 GOTO move_slowly

[Label: move_quickly]
6 Move Right
7 GOTO move_quickly

References