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:

  1. Go left.
  2. Go right.
  3. No operation.
  4. 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.

Advertisements

Pages: 1 2

2 Responses to “Mars Rover”

  1. no one said

    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.

  2. Daniel said

    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();
        }
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: