We will analyze the Mars Rover problem in this article and try to see how we can design a solution for this problem. Below is the problem statement for same.
Problem Statement
Mars Rover Challenge
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
Solution
The complete code for this problem is given at this github repo.
There could be multiple ways of solving the problem and we are going to discuss once such solution in this article . The programming language we are going to use in this article is C#.
As per the input mentioned above, initial position and direction of the rover on the pleatue is as shown in the figure.
To design the solution for the problem we would analyze the entities that are part of the problem statement.
At a high level we observe there are 2 important entities which are:
- Pleatue
- Rover
If we read the problem statement carefully these entities are related in the maaner in which pleatue maximum and minimum corrdinates acts as bound contraints for the rovers.
Therefore two classes we need are pretty straightforward i.e.
- Pleatue
- Rover
The other classes for the problem statement are :
- ReadInputs: This class is used to read inputs from the system console.
- Direction : This class is an abstract class that contain method Left or Right. Derived classes like North, South , East and West are derived from the Direction class. The left and right method return the direction object as per left or right move of the rover.
The overall class diagam for the solution to the problem statement is displayed below
Code sample for Pleatue class. Here the (MinX, MinY) are hardcoded as (0,0) and (MaxX,MaxY ) are the Max coordinate position for the pleatue.
public class Pleatue
{
public int MinX { get; set; } = 0;
public int MinY { get; set; } = 0;
public int MaxX { get; set; }
public int MaxY { get; set; }
public Pleatue()
{
MinX = 0;
MinY = 0;
}
public Pleatue(int maxX, int maxY)
{
MinX = 0;
MinY = 0;
MaxX = maxX;
MaxY = maxY;
}
}
And the Rover class has 2 important properties i.e.
- CurrentPosition (x,y)
- Direction
In addition Rover has a public method Move() that updates the(X, Y)coordinates of Rover or updates its direction as per the instruction provided by the program to Rover. For example:
In the instructions LMLMLMLMM, if the L or R is received then the direction update is done and if M is received then the X or Y coordinate is updated as per Rover’s direction.
Here Rover class Move method also has 2 private methods to update either the position of the rover or update its direction i.e.
- UpdatePosition
- UpdateDirection
The code for the Rover class is as follows:
public class Rover
{
public Pleatue Pleatue;
public Position CurrentRoverPosition;
public Direction CurrentDirection { get; set; }
public Rover() { }
public Rover(int x, int y, char directionChar)
{
CurrentRoverPosition.X = x;
CurrentRoverPosition.Y = y;
CurrentDirection = Direction.GetDirection(directionChar);
}
public Rover(Position initPos,char directionChar)
{
CurrentRoverPosition= initPos;
CurrentDirection = Direction.GetDirection(directionChar);
}
public void Move(string instructionString)
{
foreach (char c in instructionString.ToCharArray())
{
if (c.Equals('L') || c.Equals('R'))
{
updateDirection(c);
}
else
{
updatePosition();
}
}
}
private void updatePosition() {
switch (CurrentDirection.GetType().Name)
{
case "North":
if(CurrentRoverPosition.Y > Pleatue.MinY)
CurrentRoverPosition.Y = CurrentRoverPosition.Y+ 1;
break;
case "South":
if (CurrentRoverPosition.Y < Pleatue.MaxY)
CurrentRoverPosition.Y = CurrentRoverPosition.Y - 1;
break;
case "East":
if (CurrentRoverPosition.X < Pleatue.MaxX)
CurrentRoverPosition.X = CurrentRoverPosition.X + 1;
break;
case "West":
if (CurrentRoverPosition.X > Pleatue.MinX)
CurrentRoverPosition.X = CurrentRoverPosition.X - 1;
break;
default:
break;
}
}
private void updateDirection(char leftorright)
{
Direction directionUpdate = CurrentDirection;
if (leftorright.Equals('L'))
{
CurrentDirection = CurrentDirection.Left();
}
else
{
CurrentDirection = CurrentDirection.Right();
}
}
public void DisplayRoverCoordinates()
{
Console.WriteLine("{0} {1} {2} \n\n", CurrentRoverPosition.X.ToString(), CurrentRoverPosition.Y.ToString(), CurrentDirection.ToString());
}
}
The Direction classess have the following structure:
public class Direction
{
public Direction() { }
public virtual Direction Left()
{
return this;
}
public virtual Direction Right()
{
return this;
}
public static Direction GetDirection(char directionChar)
{
Direction direction = null;
if (directionChar.Equals('N'))
direction= new North();
else if (directionChar.Equals('S'))
direction= new South();
else if (directionChar.Equals('W'))
direction= new West();
else if (directionChar.Equals('E'))
direction= new East();
return direction;
}
}
public class North : Direction
{
public North() { }
public override Direction Left()
{
return new West();
}
public override Direction Right()
{
return new East();
}
public override string ToString()
{
return "N";
}
}
public class South : Direction
{
public South() { }
public override Direction Left()
{
return new East();
}
public override Direction Right()
{
return new West();
}
public override string ToString()
{
return "S";
}
}
public class East : Direction
{
public East() { }
public override Direction Left()
{
return new North();
}
public override Direction Right()
{
return new South();
}
public override string ToString()
{
return "E";
}
}
public class West : Direction
{
public West() { }
public override Direction Left()
{
return new South();
}
public override Direction Right()
{
return new North();
}
public override string ToString()
{
return "W";
}
}
Output of the program will be as follows:
