Two robots are to be parachuted onto random locations on an infinite line. When they land, their parachutes detach and remain where they are. The robots may each be programmed with numbered instructions from the following set:
- Go left one unit
- Go right one unit
- Skip next instruction unless there is a parachute here
- Go to (label)
Each instruction takes one cycle to execute. Program the robots to collide.
Notes:
There must be a finite number of lines of code (ie, you can't say move right once, then left twice, then right thrice, .. ad infinitum).
Try to do it using the fewest lines of instructions (if both robots have the same instruction set, you can count it only once).
There is no way for the robots to distinguish between the two parachutes if they are crossed.
The instructions in the program are numbered, and are executed in order. An instruction of "go to" some label means that the next instruction to follow will be at that number, and continue from that point in numerical order.
For example, look at the following:
10 right one unit
20 left one unit
30 go to 10
40 do a backflip
This code would have the robot forever going back and forth between two spots.
Line 10 would execute, then 20, then 30, and then back to 10 (line 40 in this example would never be run).
Here's one with 9 lines of code:
Robot 1:
10 right one unit
20 skip next instruction unless there is a parachute here
30 go to 50
40 go to 10
50 right one unit
60 right one unit
70 go to 50
Robot 2:
10 right one unit
20 goto 10
Case 1: Robot 1 begins to the right of Robot 2:
Robot 1 will never run into a parachute, therefore it will always go right once for every 3 execution cycles (right 2 for every 6 execution cycles)--it will perpetually skip line 30.
Robot 2 will always go right once for every 2 execution cycles (right 3 for every 6 execution cycles).
Therefore Robot 2 will eventually catch up with Robot 1 and they collide.
Case 2: Robot 2 begins to the right of Robot 1:
Robot 1 will eventually run into Robot 2's parachute, and at that time it will execute line 30, which jumps to line 50. At that point, it will move right 2 units for every 3 execution cycles (4 units in 6 cycles), whereas Robot 2 will continue to move right 1 unit for every 2 execution cyles (3 units in 6 cycles). Therefore, Robot 1 will eventually catch up with Robot 2 and they collide.
Edited on September 11, 2003, 1:59 pm
Solution (spoiler)
