All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Collision Course (Posted on 2003-09-11) Difficulty: 4 of 5
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.


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).

See The Solution Submitted by DJ    
Rating: 4.3500 (20 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Two robots, same program | Comment 2 of 11 |
10 move left
20 move right
30 move left
40 skip next instruction unless there is a parachute here
50 goto 70
60 goto 10
70 move left
80 goto 70

This program can be given to both robots. With both robots slowly moving left, one robot will eventually find the other one's parachute since neither one looks for a parachute on their starting point. The robot which finds a parachute then moves at full pace toward the still slowly traveling robot and eventually catches it.

Edited on September 11, 2003, 2:30 pm

Edited on September 11, 2003, 2:31 pm
Edited on September 11, 2003, 2:32 pm
  Posted by Brian Smith on 2003-09-11 14:29:13
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information