The Problem : Mars Rovers

by Albert Mutangiri 30. September 2012 19:44

Well last week I received mail from thoughtworks, and all in one - time has been quite hectic on my side, been working remotely away from home and trying to catch up. On my flight back to JHB, had all these ideas running through my mind.. so soon i got home ..dropped everything had to get some time for this and after all is done, why not share the experience as well. This was such a fun programming exercise..So hooked up to my desk and fired up visual studio 2010..



PROBLEM : 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 and location is represented by a combination of 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.
INPUT AND OUTPUT

Test Input:
5 5
1 2 N
LMLMLMLMM
3 3 E
MMRMMRMRRM

Expected Output:
1 3 N
5 1 E

SOLUTION: MARS ROVERS

Where do i start ? So I didn't wanna rush though this, so had to think this through correctly. The design architecture, the technology language, test driven design and a bunch of other concerns.  I've been given a language of my choice Java , Ruby or C#, so even though I'm exposed to Java in my day to day life job, I've decided to run with C# as my language of choice because of the great integrated development evironment that ships with it.

Our solution is pretty simple if we look at the x and y graph below, given a scenario that we deployed a robot at position X,Y (0,0)  North, I noted the following interesting states and our final solution will be revolving arround these rules.

1) Any move from point (X,Y) and the rover facing towards North will increment    ++Y
2) Any move from point (X,Y) and the rover facing towards South will decrement   --Y
3) Any move from point (X,Y) and the rover facing towards East will increment     ++X
4) Any move from point (X,Y) and the rover facing towards West will decrement   --X

Finally any change in state of the rover in terms of direction will not affect the positioning of the rovern in terms of X,Y location, so lets say we pass a command string "MM" for a rover positioned at X,Y(0,0) facing North. The final destination of the Rover will be X,Y(0,2) and any state change in direction with command "L" or "R" will only cause the rover to face a new direction in this case West and East respectively but position according to X and Y will remain X,Y(0,2). So with our task clearly defined, Lets look at the design.

 

 

The design architecture

I remember early on back 2010 spending some time trying to understand design patterns when writing software and have learned one thing - designing object oriented software is hard and designing reusable object oriented software is even harder, I must find pertinent objects, factor them into classes at the right granurality, define class interfaces, inheritence structures and establish key common grounds or relationships among them. I'm challenged once again with the design, it has to be specific to the problem at hand but generic enough to address any future changes. So without wasting time my mind had already landed on the idea that we're dealing with dynamic state change at runtime based on some context and was more comfortable working with state design architecture.

The state pattern can be seen as a dynamic version of the strategy pattern. When the state inside an object changes it changes its behaviour by switching to a set of different options. I could achieve this objective by an object variable changing its subclass within a class hierarchy. The Context "Rover" has a reference of a type IState "INavigator" that starts out to a particular reference to a particular state, in this case X,Y(0,0) N. All requests are passed through to the Handle operation in that state. In this design, the State has full access to the Rover data.

So at any point in time the Context or the State can decide it is time to switch states.

 


This presents an interesting interplay between Context "The Rover" and State in this case X and Y, Direction North, South, East and West. In this case I have defined the following interface and class hierarchies.

The Context is handled by the following classes.

1) Rover
2) Position
4) NavigationController

The State Is handled by the following classes.

1) INavigator
2) DirectionWest
3) DirectEast
4) DirectionNorth
5) DirectionSouth
6) NavigationCordinates

Constants are defined in this class
1) RoverConstants

So lets look at the code..

INavigator - the main interface object for manipulating state of the device, all the direction classes implement this interface.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


/* Developer : Albert Mutangiri */

namespace Albertoncaffeine.MarsRovers.Core {

/*
At a hight level defines the Interface for a particular state of the Context "Rover"
Our Context is the Rover that holds reference to the particular Rover to be moved
The Rover can move forward, turn left as well as turn right
*/

    public interface INavigator {
        /*returns the direction of the rover at any given point in time */
        string DIRECTION_NAME { get; }
        /*moves the Rover forward */
        void navigateForward(Rover device);
        /*switches the rover to face right direction */
        void navigateRight(Rover device);
        /* switches the rover to face left direction */
        void navigateLeft(Rover device);

    }
}

Direction North implementation is for managing state when this device is facing North, i have other implementation for all directions for this device, will make the source available on this blog post.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

/* Developer : Albert Mutangiri */


namespace Albertoncaffeine.MarsRovers.Core {
/*
This class will handle behavior of switching direction facing North associated with a state of the Context "Rover"
Our Context is the Rover that holds reference to the particular Rover to be moved
The Rover can move forward, turn left as well as turn right
*/

    public class DirectionNorth : INavigator {          

        /* Returns direction name string "N" */
        public string DIRECTION_NAME {
            get {
                return RoverConstants.DIRECTION_NORTH;
            }
        }
        /*Accepts the Rover to be moved and moves this rover forward in this case facing North the rover will increment ++Y */
        public void navigateForward(Rover device) {
             device.location.incrementCountY();
        }
        /* Accepts the Rover to be moved and switches the rover from facing North to East,state on X,Y remains the same. */
        public void navigateRight(Rover device) {
            device.location.navigator = NavigationController.getNavigator(DirectionTypes.EAST);
        }
        /* Accepts the Rover to be moved and switches the rover from facing North to West,state on X,Y remains the same. */
        public void navigateLeft(Rover device) {
            device.location.navigator = NavigationController.getNavigator(DirectionTypes.WEST);
        }  

    }
}

Lets face the Rover, our main Context object

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/*
Developer : Albert Mutangiri */


namespace Albertoncaffeine.MarsRovers.Core {
/*
  This class defines the main Context "Rover".
  Holds a direct reference to Position and our Position tells us where to find X,Y as well as direction facing this device
*/

    public class Rover  {

        /*Position object in this case the location can point us to the device's location " X,Y " and direction */
        Position positon = new Position();
        public Position location { get { return positon; } set { positon = value; } }       

        /*default constructor method sets the current position to X,Y(0,0) */
        public Rover() {
            location.cord.X = 0;
            location.cord.Y = 0;         
        }
        /* overloaded constructor allows us to pass initial x,y as well as direction of this device */
        public Rover(int x, int y, DirectionTypes facingDirection) {
            location.cord.X = x;
            location.cord.Y = y;
            positon.navigator = NavigationController.getNavigator(facingDirection);
        }
       /* remote users will run this function with the necessary commands to navigate the device */
        public void startRemotePushButton(string commands) {
            moveRover(commands);          
        }
        /* the main function to move the rover */
        void moveRover(string commands) {

            for (int x = 0; x < commands.Length; x++) {

                switch (commands[x].ToString().ToUpper()) {
                    case RoverConstants.NAVIGATE_COMMAND_FORWARD:
                         positon.navigator.navigateForward(this);
                        break;
                    case RoverConstants.NAVIGATE_COMMAND_LEFT:
                        positon.navigator.navigateLeft(this);
                        break;
                    case RoverConstants.NAVIGATE_COMMAND_RIGHT:
                        positon.navigator.navigateRight(this);
                        break;
                    default:
                        break;
                }
            }

            notifyCurrentPosition();
         }   
      /* signals the current position of this device */
       void notifyCurrentPosition() {
            Console.WriteLine("{0} {1} {2}", this.positon.cord.X, this.positon.cord.Y, this.location.navigator.DIRECTION_NAME);
        }
    }

}

So after writting a whole lot of code the solution was looking good. I could fire up this thing and run the test cases get the expected result, though there is a few areas I still need to refactor and polishb up like the client app that will send the commands to the remote device and again time is not on my side.. but here is a few test cases i had to run.

using Albertoncaffeine.MarsRovers.Core;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;

namespace Albertoncaffeine.MarsRover.Tests {   

/*
   This is a test class for RoverTest and is intended
  to contain all RoverTest Unit Tests
*/

[TestClass()]
    public class RoverTest {

        private TestContext testContextInstance;
        /*
         Gets or sets the test context which provides
         information about and functionality for the current test run for the Mars Rover device.
        */

        public TestContext TestContext  {
            get  {
                return testContextInstance;
            }
            set {
                testContextInstance = value;
            }
        }
        /*
          A test for Rover direction facing and positioning initialisation
        */

        [TestMethod()]
        public void RoverConstructorTest() {
            int x = 1; /* Initialize position x of this rover */
            int y = 2; /* Initialize position y for this rover */
            DirectionTypes facingDirection = DirectionTypes.NORTH; /*Initialize facing direction for this rover to the South */
            Rover target = new Rover(x, y, facingDirection);
           /*the result must point 1 2, N */
            Assert.AreEqual(target.location.navigator.DIRECTION_NAME, "N");
            Assert.AreEqual(target.location.cord.X, 1);
            Assert.AreEqual(target.location.cord.Y, 2);
        }
         /*
          A test for moving the rover x and y position and location.
         */

        [TestMethod()]
        public void startRemotePushButton()  {
            int x = 1; /* Initialize position x of this rover */
            int y = 2; /* Initialize position y for this rover */
            DirectionTypes facingDirection = DirectionTypes.NORTH; /* Initialize facing direction for this rover to the North  */
            Rover target = new Rover(x, y, facingDirection);
            /* Move the rover twice and navigate left */
            target.startRemotePushButton("MML");           
            Assert.AreEqual(target.location.navigator.DIRECTION_NAME, "W");
            Assert.AreEqual(target.location.cord.X, 1);
            Assert.AreEqual(target.location.cord.Y, 4);           
        }
        /*
         Test to move the rover as per the given scenario problem, given input : 5 5 1 2 N LMLMLMLMM
        */

        [TestMethod()]
        public void startRemotePushButtonForFirstTestCaseScenario() {
            int x = 1; /* Initialize position x of this rover */
            int y = 2; /* Initialize position y for this rover */
            DirectionTypes facingDirection = DirectionTypes.NORTH; /* Initialize facing direction for this rover to the North  */
            Rover target = new Rover(x, y, facingDirection);
            /* Move the rover twice and navigate left and our expected result must be ... 1 3 N
            target.startRemotePushButton("LMLMLMLMM");
            Assert.AreEqual(target.location.navigator.DIRECTION_NAME, "N");
            Assert.AreEqual(target.location.cord.X, 1);
            Assert.AreEqual(target.location.cord.Y, 3);
        }     
   
    }
}

Tags:

C# | design patterns | Java | thoughtworks

Comments

3/12/2013 12:55:21 AM #

Chris

I had some fun condensing the solution to this into 3 lines of code Laughing

https://gist.github.com/cmaitchison/5133520

Chris Australia | Reply

10/4/2013 7:14:53 PM #

albert

Now that's what i call awesome!

albert United States | Reply

4/23/2013 8:32:17 AM #

Sachin Kainth

The moveRover method breaks O in SOLID.  What solution do you propose for that?

Sachin Kainth United Kingdom | Reply

11/19/2014 6:37:05 AM #

trackback

Agile Adoption - Part 1

Agile Adoption - Part 1

Let's Talk Dev | Reply

12/20/2016 7:23:23 PM #

pingback

Pingback from steroidsforsale.biz

anabolic steroids for sale

steroidsforsale.biz | Reply

Add comment


(Will show your Gravatar icon)

  Country flag

biuquote
  • Comment
  • Preview
Loading



About Me

mage.axd?picture=2012%2f4%2fbert.jpg

Hi, My name is Albert Mutangiri, I am a software developer currently interested in software design, integration, .net technologies and Java. I'm currently developing enterprise applications for business process automation using Java & .Net Technologies.

 

I Code Java

PSNetwork


bertoncaffeine

Playing
17 0 1 0 18
13 6 0 0 19
4 0 0 0 4
22 1 0 0 23
0 0 3 0 3

Tag cloud