Mars Rover
August 21, 2018
Today’s exercise is a Microsoft interview question:
Write code using the commands below for two rovers to meet. Two rovers are dropped on Mars. Imagine Mars to be a straight infinite plane. When the rovers are dropped on Mars they are dropped with a parachute, so their initial position on Mars is on the parachute:
The only commands available are:
- Go left.
- Go right.
- No operation.
- If on parachute go to label.
A label points to a piece of code with a name where it is possible to transfer execution.
Using ONLY the commands above, write code to enable the rovers to meet.
Your task is to write a program to help the Mars rovers meet. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Assuming you meant line and not plane, there’s no need for the “if on parachute” command. It’s a performance optimization. Without that, one rover stays still, and the other goes right one, left two, right three, left four… This is O(x^2) where x is the distance between rovers.
Here’s a program in C for both rovers. The program moves each rover slowly to the left (by moving one step right for each two steps left). When the rightmost rover lands on the other rover’s parachute, it moves fast to the left to catch up to the other rover (it moves fast by only executing the left command).
void go_left(); void go_right(); int on_parachute(); int main(void) { move_left_slow: while (1) { go_left(); go_left(); go_right(); if (on_parachute()) { goto move_left_fast; } } move_left_fast: while (1) { go_left(); } }