Monday, September 6, 2010

Parachuting robots

Two identical robots living in flatland parachute from the sky.  Each one falls somewhere an on infinite number line.  They each leave their parachutes on the ground and start walking around.

For some reason, this puzzle brings to mind an image of a para-bomb, from one of the Super Mario Brothers games.

When each robot lands, it executes a program that tells it when to go left or right and under what conditions.  Each robot has an identical program.  Neither robot can tell which direction the other robot is just by looking. The goal is to have these two robots meet.

Write a program that will make this happen.  You don't need to know any programming, just write it in English or pseudocode.

See the solution

intrinsicallyknotted said...

If the robots can identify the sight of a parachute on the ground, I can do it:

Each robot, after it lands, should do the following:

For n starting at 1 do:

start: Move n units to the right. If a parachute is encountered during this travel, END.
Move n units to the left (back to the landing site).
Move n units to the left. If a parachute is encountered during this travel, END.
Move n units to the right (back to the landing site).
Increment n and GOTO start.

Each robot will be moving in the same direction at the same speed at all times until one of them halts. Eventually, one will travel far enough in the correct direction to encounter the other's parachute, and will stop there. When the other robot returns to its own landing site, they will meet.

miller said...

Yes! Robots can recognize the parachute on the ground. That solution works perfectly.

However, the amount of time for the algorithm to complete is proportional to N^2, where N is the distance between the robots. It's possible to find an algorithm whose completion time is proportional to N. (For you CS geeks: I'm saying that you can find a O(N) solution.)

intrinsicallyknotted said...

Really, there's an O(n) solution? I shall have to think harder! (I can think of some minor improvements to my first solution, but nothing yet that will improve the complexity.)

The Barefoot Bum said...

Until you have encountered the other parachute, move one unit to the left and wait for one unit of time. Once you have encountered the other parachute, move one unit to the left without waiting. This is at least some improvement to O(N*2).

The Barefoot Bum said...

O(N*3), actually: N*2 to find the other parachute, N to find the other robot.

The Barefoot Bum said...

If you can't wait, each robot can move two units to the left and then one unit to the right until it encounters the other parachute. Thanks to intrinsically knotted for spotting the parachute-spotting trick; without it, I don't think you can solve the problem in less than O(N^2) time.

miller said...

Barefoot Bum, unless I am mistaken, your solution is O(N). It takes 2N steps to find the parachute, and then 2N more to find the robot.

Secret Squïrrel said...

I think Barefoot Bum's got it, altho' we have to assume that each robot has the same understanding of "left" (which is safe to do given that they're presumably two dimensional).

The ability to detect the other's parachute is pretty much essential since we need some event to trigger a change in the behaviour of one of them. Otherwise they would require a random number generator to tell them to occasionally change direction.

If you consider both robots to be parts of a single machine for detecting parachutes, you very quickly realise that there is no need to have the robots search in both directions.

The move 1, wait 1 algorithm is the most efficient because the total time taken to meet is shared equally between searching for the parachute and closing the gap after detection. Any increase in efficiency in one activity is more than matched by a greater decrease in efficiency in the other.

Danny said...

Just found this site and loving the puzzles! I came up with a solution that is a bit different, and I realize after reading the comments, not quite as good as Barefoot Bum, but I believe still O(N). Correct me if I'm wrong!

Start by moving 1 unit to the right.
While haven't found other chute (or other bot):
Turn around and double your distance
Once you find the chute, keep moving in same direction til you meet other bot.

Using Excel to try different values I seem to get between 2N and 4N for total time (and also distance).

Again, not as good as the move one, wait one. Still linear time though.

miller said...

It was difficult to convince myself, but I'm sure your solution is O(n), Danny. I was surprised that a zig-zagging solution could work, but it does. The fact that the robots double their distance at every step (rather than increasing it linearly) is crucial.