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!