Two robots on a line

Question

You probably know the problem with the two robots dropped on a line when you need to program them to meet.

Two robots are dropped from an airplane and land on a single line (with discrete positions) using a parachute which is left at the landing point. The robots are both facing north, they are an unknown distance apart, and one has landed directly east of the other.

The robots are now to be programmed such that they meet each other. They can be instructed to move left or right to a neighboring position and to check whether a parachute is present at the current location. If the other robot is met both robots stop there and live happily ever after.

The parachute check might conditionally execute any number of instructions and any block of instructions may be repeated unconditionally. Write down a program that both robots can follow simultaneously and which garuantees that they meet.

You have to create a generic algorithm (a little pleonastic) that applied to both robots guarantees that the robots will meet. They leave their parachute on the spot where they are dropped and they can check if in the current position there is a parachute.

The original statement is here: http://en.wikibooks.org/wiki/Puzzles/Logic_puzzles/Parachuted_Robots There is also a solution that I don't understand. If someone can make any sense of it, please help me with a little explaning. Any other solution would be much appreciated.

My first thought on this problem would be to program the robot to choose randomly to first go right or left, and then make something like an exponential search: first go 2 positions to right, then 4 to left etc. If in one of this "trips" in right or left the robot finds the second parachute (the one that was used by the other robot), the robot will only search in that direction. Does this make any sense?

Thank you very much!

Answer 1

My program is actually shorter, and works like a charm too:

start: left
skipNext
goto start
next: left
goto next

This works because the second loop is faster than the first loop.

You can test your program here: http://david-peter.de/parachuting-robots/

Answer 2

Your "first thought" solution should work too, but it will take a while longer for the robots to meet than the solution you cited at wikibooks. To recap, the wikibooks solution is:

• 10 Go right
• 20 Go left
• 30 Go right
• 40 If Not Parachute GOTO 10
• 50 Go right
• 60 GOTO 50

In case you don't recognize the syntax, the author is trying to mimic BASIC, where the numbers 10-60 are line numbers, and the GOTOs are code jumps.

Lines 10-40 have both robots moving slowly right. The "right, left, right" steps slow down movement to the right. It could have just as easily been "right, wait". Line 40 checks for the parachute. When both robots landed on the line, exactly one of them was to the left of the other. The left robot will eventually find the other parachute. The right never will. When the left robot finds the right robot's parachute, it enters lines 50-60, where it moves right without the slowdown. Now that the left robot is moving right faster than the right robot, the left will eventually catch up.

Personally I think the algorithm you posed is more fun, since both robots would swing back and forth a lot. In a way it's a similar algorithm, but the slowdown grows linearly with each step.