Puzzles/Logic puzzles/Parachuted Robots

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Puzzles | Logic puzzles | Parachuted Robots

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 guarantees that they meet.