Modeling Mars rovers with F#

Although currently somewhat overshadowed by ESA's amazing Rosetta mission, Mars rovers are awesome in their own right. So when a colleague pointed me in the direction of an interview puzzle about modeling Mars rovers and mentioned that he was writing an (immutable) F# implementation I decided to follow suit and have a go myself.

The problem

The basic problem described in the puzzle is modeling the movements of rovers on the surface of Mars. The surface is represented by a simple grid with the point (0,0) being at the left hand corner. Rovers land at a given point facing a given direction and are then commanded to either move in the direction they are facing or rotate 90° either to the left or the right.

The program should accept as an input a series of commands. The first defines the planet surface as a maximum value of the X and Y coordinates. Subsequent commands describe the landing position of rovers followed by their movements.

5 5
1 2 N
LMLMLMLMM
3 3 E
MMRMMRMRRM

In this example the first line initialises the planet surface to have maximum X and Y coordinates of 5. Then a rover is added to (1,2), facing north. Instructions for this rover follow, with L turning the rover 90° to the left, R turning it 90° to the right and M moving it forwards one place in the direction it is facing. The process is then repeated for another rover starting at (3,3) and facing east.

Once the input has been processed the final position and direction of the rovers should be printed.

1 3 N
5 1 E

The original problem does not explicitly state error conditions but I think that at a minimum movement out of bounds and rover collisions should be covered. The original problem also does not state how the input should be processed. There are two possibilities:

I decided to adopt the second approach as it is implied by the format of the input and is simpler.

Finally, for the sake of clarity I gave the rovers names, so the input now becomes:

5 5
Opportunity 1 2 N
LMLMLMLMM
Curiousity 3 3 E
MMRMMRMRRM

The solution

The solution I arrived at can be found on GitHub, with the majority of the interesting code in Model.fs.

Basic design

I decided to use single case unions when writing my model, as described in this post over at F# for fun and profit. I really like the elegance of this approach and was interested to see how it would work in practice. (I did not use .fsi files as described in the post as I found them to be more trouble than they were worth.)

Using this approach is a nice compromise between object oriented style encapsulation and a more functional approach.

The article above defines an apply method which grants a function access to the union's underlying data. I also defined a mutate function which creates a new value based on a function which updates the underlying data.

module Rover = 

  type State = { ... }  
  type Instance = Rover of State

  let private apply f (Rover state) = f state  
  let private mutate f = apply (fun state -> Rover (f state))

This function can then be used to create new values.

//Rover.Instance -> Rover.Instance
let move = mutate (fun state ->
  let location = ...
  in { state with Location = location; }
)

Errors

In order to represent the success/failure of an operation I created a new union type, Outcome<'T>. This is essentially the same as Choice<'T,String> but with nicer semantics and syntax.

//Using Choice<'T,String>
match value with
| Choice1Of2 result -> ...
| Choice2Of2 message -> ...

//Using Outcome<'T>
match value with
| Success result -> ...
| Problem message -> ...

Using the Outcome<'T> type I could represent errors without the need for exceptions.

let create name location orientation = 
  if (String.IsNullEmptyOrWhitespace name) then
    Problem ("The rover name cannot be null, empty or whitespace.")
  else
    Success (...)

Composing functions

In order to be able to compose multiple functions of the form 'a -> Outcome<'b> I created a bind function and gave it an alias, -->, as a custom operator.

let bind (f : 'a -> Outcome<'b>) (g : 'b -> Outcome<'c>) = 
  fun x ->
    match (f x) with
    | Success x' -> g x'
    | Problem msg -> Problem msg

let (-->) = bind

This allowed me to create composite functions where each component function was only called if the previous one had been successful, with error messages being propogated otherwise. A good example of this is the validatedAdd function in Planet.MissionControl.

//(Planet.State * Rover.Instance) -> Outcome<Planet.Instance>
let private validatedAdd = 
  State.checkBounds
  --> State.checkCollissions
  --> Rover.add
  --> State.toPlanet

(This is an example of a monad. There are a lot of monad tutorials out there if you are interested in finding out more.)

Issuing instructions

Once the planet surface has been initialised there are two types of command:

These commands share two validation rules regarding the state of the planet surface:

The model of the planet surface is fairly straight forward.

module Planet = 
  type State = {
    Width : int;
    Height : int;
    Rovers : Rover.Instance list;
  }

Rovers are responsible for keeping track of their current position.

module Rover =
  type State = {
    Name : String;
    Location : Location.Instance; //X and Y coordinates
    Orientation : Orientation.Instance; //Direction the rover is facing
  }

In order make my solution as simple as possible I made the second command, moving a rover, a case of the new rover command. When modeling a move command a new planet State is created minus the moving rover, the rover's position is then updated and the rover re-added to the State as if it were a new rover. This can be seen in the functions touchdown and instruct in the Planet.MissionControl module.

let private validatedAdd =   
  State.checkBounds           //Ensure within bounds
  --> State.checkCollissions  //Ensure not at same location as another
  --> Rovers.add              //Add to the surface
  --> State.toPlanet 

///Rover.Instance -> Planet.Instance -> Outcome<Planet.Instance>
let touchdown rover (Planet state) =
  validatedAdd (state, rover)

///String -> (Rover.Instance -> Rover.Instance) -> Planet.Instance -> Outcome<Planet.Instance>
let instruct name instruction (Planet state) = 
  let f = 
    Rovers.find                    //Find by name
    --> Rovers.extract             //Remove from planet surface
    --> Rovers.update instruction  //Issue the instruction
    --> validatedAdd               //Re-add to the planet surface
  in f (state, name)

Processing the input defined in the puzzle is now a case of simply creating the initial, empty, model of the planet and then folding over a list of instructions.

Conclusion

You can see the model in action in Program.fs, which is somewhat less elegant. I think that although the model could certainly be polished and expanded it is a good solution to the problem.

Running the program with the standard input will give the following response.

Rovers:
Curiousity | (5, 1) | Facing East
Opportunity | (1, 3) | Facing North

One of the things that really impressed me when writing this was how easy it is in F# to create a viable working solution without the missteps and gotchas that you tend to associated with the same process in languages like C#. The single case union model also worked really well and allowed me to think broadly in terms of real world objects while using a functional style.

Comments