perplexus.info :: Algorithms : Collision Course

Collision Course (Posted on 2003-09-11)

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

Submitted by DJ

Rating: 4.3500 (20 votes)

Solution: (Hide)

If the two robots are called A and B, there are two possibilities: either A is farther to the right, or B is farther to the right.
Both robots start moving to the right (it matters little), at a rate of one step every three cycles. Thus, they remain the same distance apart.
If either robot crosses a parachute, it must belong to the other, so they start moving at a rate of one step every two cycles. Thus, they are moving faster than the other robot, and will catch up and eventually collide.
The following set of instructions, given to both robots, will do this:
10 go right one unit 20 skip next instruction unless there is a parachute here 30 go to 50 40 go to 10 50 go right one unit 60 go to 50
// Original problem concept from Microsoft.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
Puzzle Thoughts	K Sengupta	2023-08-18 08:01:11
Puzzle Thoughts	K Sengupta	2023-08-18 08:01:07
solution (not too sure)	Dacre	2003-09-22 08:51:37
re: Two robots, same program	Charlie	2003-09-12 09:41:56
Great problem!	Aaron	2003-09-11 20:15:16
re(2): Two robots: I really need to proofread better	DJ	2003-09-11 20:10:07
re(2): Pretty good	SilverKnight	2003-09-11 16:25:32
re: Pretty good	Brian Wainscott	2003-09-11 16:04:11
Pretty good	DJ	2003-09-11 15:43:04
re: Solution (spoiler) - 7 lines	SilverKnight	2003-09-11 15:01:30
re: Two robots: I really need to proofread better	Brian Smith	2003-09-11 14:33:46
Two robots, same program	Brian Smith	2003-09-11 14:29:13
Solution (spoiler)	SilverKnight	2003-09-11 13:55:48

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

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

Chatterbox:


perplexus dot info