Mars Rover

August 21, 2018

Our solution makes use of the “go left” and “if on parachute” commands. Both rovers move one step left at each turn. As soon as one of the rovers reaches a parachute, it continually moves left until it reaches its mate:

(define (rovers landing1 landing2)
  (let loop ((rover1 landing1) (rover2 landing2))
    (cond ((= rover1 rover2) rover1)
          ((= rover1 landing2)
            (let r1 ((rover1 (- rover1 1)))
              (if (= rover1 rover2) rover1
                (r1 (- rover1 1)))))
          ((= rover2 landing1)
            (let r2 ((rover2 (- rover2 1)))
              (if (= rover1 rover2) rover1
                (r2 (- rover2 1)))))
          (else (loop (- rover1 1) (- rover2 1))))))

And here are two examples:

> (rovers 3 6)
0
> (rovers 6 3)
0

It doesn’t matter which rover is on the left or the right, or which moves first. The rovers each move left until one of them reaches its mate’s parachute, at which time it knows its mate is to the left, and it runs until it finds its mate.

You can run the program at https://ideone.com/035JQs.

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: