The Mars Rover Tech Challenge (in Lisp!) Part 1

Doing the Mars Rover Tech Challenge in common lisp!

A friend of mine is applying for dev jobs and is being sent programming tests. He showed me one recently, about controlling a rover on Mars by parsing a string of commands made up of L(eft), R(ight) and M(ove).

This looked like a fun distraction, so I decided to try it.

This series of posts

This is the first of three posts on this topic. I’ll update these links as I publish the other posts. I’ve used lisp (the second oldest programming language still in use!) for this, and in the third post I’ll explore why:

Part 1 : Initial code - running from a REPL
Part 2 : Read the configuration file and running from the command line
Part 3 : Benchmarking (AKA why this funny looking language?)

(Updated: [2020-02-15 Sat])

The challenge

This is a well known problem, so, rather than using the example that was sent, I’ll point you to the Google coding challenge:

https://code.google.com/archive/p/marsrovertechchallenge/

Mars Rover Technical Challenge

MARS ROVERS

A squad of robotic rovers are to be landed by NASA on a plateau on Mars.

This plateau, which is curiously rectangular, must be navigated by the rovers so that their on board cameras can get a complete view of the surrounding terrain to send back to Earth.

A rover’s position is represented by a combination of an x and y co-ordinates and a letter representing one of the four cardinal compass points. The plateau is divided up into a grid to simplify navigation. An example position might be 0, 0, N, which means the rover is in the bottom left corner and facing North.

In order to control a rover, NASA sends a simple string of letters. The possible letters are ‘L’, ‘R’ and ‘M’. ‘L’ and ‘R’ makes the rover spin 90 degrees left or right respectively, without moving from its current spot.

‘M’ means move forward one grid point, and maintain the same heading.

Assume that the square directly North from (x, y) is (x, y+1).

Input:

The first line of input is the upper-right coordinates of the plateau, the lower-left coordinates are assumed to be 0,0.

The rest of the input is information pertaining to the rovers that have been deployed. Each rover has two lines of input. The first line gives the rover’s position, and the second line is a series of instructions telling the rover how to explore the plateau.

The position is made up of two integers and a letter separated by spaces, corresponding to the x and y co-ordinates and the rover’s orientation.

Each rover will be finished sequentially, which means that the second rover won’t start to move until the first one has finished moving.

Output:*

The output for each rover should be its final co-ordinates and heading.

Test Input:

5 5

1 2 N

LMLMLMLMM

3 3 E

MMRMMRMRRM

Expected Output:

1 3 N

5 1 E

My code: Running from a REPL

So, rather than following the rules (I’m doing this for myself, rather than getting a job), I decided to ignoring suggestions to do write this in the functional programming style or requiring a particular language. I wanted to use common lisp, so that’s what I did. As a side issue, there’s only a slight change needed to make this functional, but I’ll leave that as a challenge for the reader.

Rather than presenting a final solution up front, let’s work through my thinking.

Some initial starting points

Let’s start with some initial set up and write code to satisfy these constraints.

(defparameter *x_max* 5)         ;; How big is the plateau?
(defparameter *y_max* 5)

(defparameter *x* 1)             ;; Where do we start?
(defparameter *y* 2)
(defparameter *orientation* 'n)  ;; What's our orientation?
(defparameter *commands* "LML")  ;; What commands are sent?

Now, I’ll convert my global variables to the local variables that I’ll use in my functions. Let’s just ignore the fact that these are all global variables at this point. This is my thinking process…

I’m converting the *commands* into a list, so I can pull the first command off the front, action it and then step on to the next one.

(defparameter cmds (coerce *commands* 'list))
(defparameter pos (cons *x* *y*))
(defparameter orientation *orientation*)

The core function

Looking at this problem, it feels like the workhorse will be a function that takes my location and orientation and then applies a move, so let’s write that…

I know that I need a rotate function, and some sort of move function, but I’m not exactly sure what the functions will look like. No worries, in lisp, just write the code and the compiler will let you know what’s missing.

(defun update-position (pos orientation cmds)
  (let ((move (car cmds)))
    (if move
        (progn
          (cond
            ((or (eq move #\L) (eq move #\R)) (setq orientation (rotate move orientation)))
            ((eq move #\M) (setq pos (move pos orientation)))
            (t (error "Unknown move")))
          (update-position pos orientation (cdr cmds)))
        (format t "~d ~d ~s~%~%" (car pos) (cdr pos) orientation))))

The other thing I’m doing here is recursively calling this function (the (update-position pos orientation (cdr cmds)) line) with the cdr (rest) of the commands. When there are no commands left, just write out the current position.

Build the rotate function

Rotating should be easy to implement. Take our orientation and then rotate left or right:

(defun rotate (move orientation)
  ;;    N
  ;;   W E
  ;;    S
  (let* ((compass '((N . (W E)) (E . (N S)) (S . (E W)) (W . (S N))))
         (possible (assoc orientation compass)))
    (if (eq move #\L)
        (cadr possible)
        (cddr possible))))

This should have been straightforward but, of course, testing makes sense

(princ (rotate #\L 'N))
(fresh-line)
(princ (rotate #\R 'N))

W
(E)

That doesn’t look right. Oh, of course! I needed caddr rather than cddr, or convert the sub-lists to cons es.

(defun rotate (move orientation)
  ;;    N
  ;;   W E
  ;;    S
  (let* ((compass '((N . (W E)) (E . (N S)) (S . (E W)) (W . (S N))))
         (possible (assoc orientation compass)))
    (if (eq move #\L)
        (cadr possible)
        (caddr possible))))

(princ (rotate #\L 'N))
(fresh-line)
(princ (rotate #\R 'N))

W
E

Build the move function

As lisp has generic setters (meaning the same code can be used to pull or put a value in a data structure) we can just update our pos directly.

As an aside, adding the maximum plateau size to the arguments to this function is the only real change needed to make this a functional programming implementation.

(defun move (pos orientation)
  (cond
    ((eq orientation 'N) (setf (cdr pos) (1+ (cdr pos))))
    ((eq orientation 'S) (setf (cdr pos) (1- (cdr pos))))
    ((eq orientation 'E) (setf (car pos) (1+ (car pos))))
    ((eq orientation 'W) (setf (car pos) (1- (car pos))))
    (t (error "Unknown orientation: ~a" orientation)))
  (unless (and (plateaup (car pos) *x_max*)
               (plateaup (cdr pos) *y_max*))
    (error "Outside of plateau"))
  pos)

I also want to make sure that we’re not driving off the edge of the plateau so I’ll create a predicate to check it.

(defun plateaup (coord max)
  (when (and (>= coord 0) (<= coord max))
    t))

Let’s do some quick tests.

Are we inside the plateau?
```
(princ (plateaup 4 5))
```
```
T
```
Are we outside the plateau?
```
(princ (plateaup 6 5))
```
```
NIL
```

Move north

(princ pos)
(fresh-line)
(princ (move pos 'N))

(1 . 2)
(1 . 3)

Move west

(princ pos)
(fresh-line)
(princ (move pos 'W))

(1 . 3)
(0 . 3)

Move west again
```
(princ pos)
(fresh-line)
(princ (move pos 'W))
```
An error is raised because we’re off the plateau.

Run it and see…

Lets add a handler for passing the right objects to the update-position function:

pos is a cons of x and y
cmds is coerced from a string to a list

(defun runme (x y orientation cmds)
  (let ((pos (cons x y)))
    (update-position pos orientation (coerce cmds 'list))))

Let’s run it and see

(runme 3 3 'E "MMRMMRMRRM")

5 1 E

As expected!

So what are we missing?

The input command

I’ll build that in the next post on this topic.

Does it need comments?

I’d suggest that when you look at the code below it is pretty clear and doesn’t need many comments.

In fact, I’d say it’s considerably more concise AND yet clearer than most solutions I’ve seen online.

Final code

If you want the final version of the code, here it is, or get it from my GitHub:

(defparameter *x_max* 5)         ;; How big is the plateau?
(defparameter *y_max* 5)

(defun update-position (pos orientation cmds)
  (let ((move (car cmds)))
    (if move
        (progn
          (cond
            ((or (eq move #\L) (eq move #\R)) (setq orientation (rotate move orientation)))
            ((eq move #\M) (setq pos (move pos orientation)))
            (t (error "Unknown move")))
          (update-position pos orientation (cdr cmds)))
        (format t "~d ~d ~s~%~%" (car pos) (cdr pos) orientation))))


(defun rotate (move orientation)
  ;;    N
  ;;   W E
  ;;    S
  (let* ((compass '((N . (W E)) (E . (N S)) (S . (E W)) (W . (S N))))
         (possible (assoc orientation compass)))
    (if (eq move #\L)
        (cadr possible)
        (caddr possible))))


(defun move (pos orientation)
  (cond
    ((eq orientation 'N) (setf (cdr pos) (1+ (cdr pos))))
    ((eq orientation 'S) (setf (cdr pos) (1- (cdr pos))))
    ((eq orientation 'E) (setf (car pos) (1+ (car pos))))
    ((eq orientation 'W) (setf (car pos) (1- (car pos))))
    (t (error "Unknown orientation: ~a" orientation)))
  (unless (and (plateaup (car pos) *x_max*)
               (plateaup (cdr pos) *y_max*))
    (error "Outside of plateau"))
  pos)


(defun plateaup (coord max)
  (when (and (>= coord 0) (<= coord max))
    t))


(defun runme (x y orientation cmds)
  (let ((pos (cons x y)))
    (update-position pos orientation (coerce cmds 'list))))


(runme 3 3 'E "MMRMMRMRRM")

…and as expected the output is

5 1 E

This series of posts#

The challenge#

My code: Running from a REPL#

Some initial starting points#

The core function#

Build the rotate function#

Build the move function#

Run it and see…#

So what are we missing?#

The input command#

Does it need comments?#

Final code#