'Two robots on a line

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!

algorithmsearch


Solution 1:[1]

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.

Solution 2:[2]

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/

Solution 3:[3]

It seems to me that your algorithm ought to work. The idea in the posted solution is that both robots keep a pattern of going right left right, meaning they are advancing right at a certain pace. But when the robot on the left finds the other's parachute, it starts moving to the right at a faster pace since it does not step once to the left as part of its walking pattern but keeps going right, eventually catching up to the robot on the right.

Solution 4:[4]

Both robots move left till the right robot finds the left robot's parachute and starts sprinting towards the left robot. Then they collide.

start: left
       skipNext
       goto start
       goto moveLeftFast

moveLeftFast: left
              goto moveLeftFast

Solution 5:[5]

I made this: 

start: left
       skipNext
       goto start
fastL: left
       left
       goto fastL

The idea is simple: we go left one bit. One of the robots (the one on the right) will eventually bump into parachute and then it will skip out of the fist loop, and enter the second which makes him go left twice as fast.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 ldgabbay
Solution 2 sheldonzy
Solution 3 גלעד ברקן
Solution 4 Rob Fox
Solution 5 Grzegorz

Related Questions