Friday, February 19, 2010

Mars Rovers coding problem

This is one of the coding problems I got when I attended one of the famous MNCs. I am providing the question and the solution having the complete Java code for the same. They give these kinds of problems not to see whether you get the right answer, but to check your Object Oriented skills and comprehensiveness in coding. I cleared this round. :)

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

The solution follows. You may download the complete program here.

package nasa.main;

import nasa.exceptions.InvalidInputException;
import nasa.exceptions.OutOfRangeException;

public class Nasa {
 
 private ISignal signal;
 
 private ControlPanel controlPanel;
 
 public Nasa(ISignal signal){
  this.signal = signal;
 }
 
 public void execute() throws InvalidInputException, OutOfRangeException {
  
  controlPanel = new ControlPanel(signal.getBounds());
  
  controlPanel.setRoverPos(new Heading(signal.getInitialPos()));
  
  controlPanel.setData(signal.getData());
  
 }
 
 public String getFinalPosition(){
  
  Heading finalHeading = controlPanel.getRoverPos();
  
  return finalHeading.toString();
 }
 
}
package nasa.main;

import java.util.StringTokenizer;

import nasa.exceptions.InvalidInputException;
import nasa.exceptions.OutOfRangeException;

public class Heading {
 
 private int x;
 
 private int y;
 
 private byte direction;
 
 public Heading(){
  
 }
 
 public Heading(String position) throws InvalidInputException, OutOfRangeException{
  parse(position);
 }
 
 private void parse(String position) throws InvalidInputException, OutOfRangeException {
  
  StringTokenizer tokens = new StringTokenizer(position);
  if(tokens.hasMoreTokens()){
   
   try{
    x = Integer.parseInt(tokens.nextToken());
   
    y = Integer.parseInt(tokens.nextToken());
   }catch(NumberFormatException ne){
    throw new InvalidInputException("Invalid number!!");
   }
   
   direction = tokens.nextToken().getBytes()[0];
  }
  
  if(!verifyBounds()){
   throw new OutOfRangeException("Invalid inital position!!!");
  }
 }
 
 public void parseCommand(byte command) throws InvalidInputException, OutOfRangeException{
  
  switch(command){
  case Constants.ROTATE_LEFT:
   rotateLeft();
   break;
  case Constants.ROTATE_RIGHT:
   rotateRight();
   break;
  case Constants.MOVE:
   move();
   break;
  default:
   throw new InvalidInputException("Invalid signal");
  }
 }

 private void move() throws OutOfRangeException{
  switch (direction) {
  case Constants.DIRECTION_NORTH:
   y += 1;
   break;
  case Constants.DIRECTION_EAST:
   x += 1;
   break;
  case Constants.DIRECTION_SOUTH:
   y -= 1;
   break;
  case Constants.DIRECTION_WEST:
   x -= 1;
   break;
  }
  if(!verifyBounds()){
   throw new OutOfRangeException("Rover exceeding range!!!");
  }
 }

 private boolean verifyBounds() {
  if((x>ControlPanel.BOUNDS_X || y>ControlPanel.BOUNDS_Y)
    || x<0 || y<0){
   return false;
  }
  return true;
 }

 private void rotateRight() {
  switch(direction){
  case Constants.DIRECTION_NORTH:
   direction = Constants.DIRECTION_EAST;
   break;
  case Constants.DIRECTION_EAST:
   direction = Constants.DIRECTION_SOUTH;
   break;
  case Constants.DIRECTION_SOUTH:
   direction = Constants.DIRECTION_WEST;
   break;
  case Constants.DIRECTION_WEST:
   direction = Constants.DIRECTION_NORTH;
   break;
  }
 }

 private void rotateLeft() {
  switch(direction){
  case Constants.DIRECTION_NORTH:
   direction = Constants.DIRECTION_WEST;
   break;
  case Constants.DIRECTION_WEST:
   direction = Constants.DIRECTION_SOUTH;
   break;
  case Constants.DIRECTION_SOUTH:
   direction = Constants.DIRECTION_EAST;
   break;
  case Constants.DIRECTION_EAST:
   direction = Constants.DIRECTION_NORTH;
   break;
  }
 }

 public String toString(){
  String toString = null;
  
  toString = x+" "+y+" "+toChar(direction);
  
  return toString;
 }

 private char toChar(byte direction) {
  String s = String.valueOf(direction);
  
  char c = (char)Integer.parseInt(s);
  
  return c;
 }

 
}
package nasa.main;

public interface ISignal {
 
 /**
  * This returns the upper right corner of the Rectangle in string format
  */
 public String getBounds();

 /**
  * This returns the data which includes movement and rotation commands
  */
 public String getData();

 /**
  * This returns the initial position of the rover
  */
 public String getInitialPos();
}
package nasa.main;

import nasa.exceptions.InvalidInputException;
import nasa.exceptions.OutOfRangeException;

public class Rover {
 ControlPanel parentControl;
 
 Heading currentHeading;
 
 public Rover(ControlPanel control){
  this.parentControl = control;
 }

 public Heading getCurrentHeading() {
  return currentHeading;
 }

 public void setCurrentHeading(Heading currentHeading) {
  this.currentHeading = currentHeading;
 }

 public void setData(String data) throws InvalidInputException, OutOfRangeException{
  parseData(data);
 }

 private void parseData(String data) throws InvalidInputException, OutOfRangeException{
  
  byte[] bytes = data.trim().getBytes();
  
  for(int i=0;i<bytes.length;i++){
   currentHeading.parseCommand(bytes[i]);
  }
 }
}
package nasa.main;

public class Constants {
 
 public static final byte DIRECTION_NORTH = 'N';
 
 public static final byte DIRECTION_EAST = 'E';
 
 public static final byte DIRECTION_SOUTH = 'S';
 
 public static final byte DIRECTION_WEST = 'W';
 
 public static final byte ROTATE_LEFT = 'L';
 
 public static final byte ROTATE_RIGHT = 'R';
 
 public static final byte MOVE = 'M';
 
}
package nasa.main;

import java.util.StringTokenizer;

import nasa.exceptions.InvalidInputException;
import nasa.exceptions.OutOfRangeException;

public class ControlPanel {

 private Rover rover;

 /**
  * Default bounding value for X
  */
 public static int BOUNDS_X = 5;

 /**
  * Default bounding value for Y
  */
 public static int BOUNDS_Y = 5;

 public ControlPanel(String bounds) throws InvalidInputException {
  parse(bounds);
  rover = new Rover(this);
 }

 private void parse(String bounds) throws InvalidInputException {

  StringTokenizer tokens = new StringTokenizer(bounds);

  if (tokens.hasMoreTokens()) {

   try {
    BOUNDS_X = Integer.parseInt(tokens.nextToken());

    BOUNDS_Y = Integer.parseInt(tokens.nextToken());
   } catch (NumberFormatException e) {
    throw new InvalidInputException("Invalid bounding values");
   }
  }

  if (BOUNDS_X <= 0 || BOUNDS_Y <= 0) {
   throw new InvalidInputException(
     "Bounding values should be greater than or equal to 1");
  }

 }

 public void setRoverPos(Heading heading) {
  rover.setCurrentHeading(heading);
 }

 public Heading getRoverPos() {
  return rover.getCurrentHeading();
 }

 public void setData(String data) throws InvalidInputException,
   OutOfRangeException {
  rover.setData(data);
 }

}
package nasa.implementation;

import nasa.main.ISignal;

public class TestSignal implements ISignal {
 
 private String bounds = "5 5";
 
 private String data = "LMLMLMLMM";
 
 private String initalPos = "2 2 N";

 public String getBounds() {
  return bounds;
 }

 public String getData() {
  return data;
 }

 public String getInitialPos() {
  return initalPos;
 }
 
}
package nasa.implementation;

import nasa.main.Nasa;

public class TestMain {

 public static void main(String args[]) {
  try {
   TestSignal test = new TestSignal();

   Nasa n = new Nasa(test);

   n.execute();

   String finalPos = n.getFinalPosition();

   System.out.println("Final position is : " + finalPos);
  } catch (Exception e) {
   e.printStackTrace();
  }

 }
}
package nasa.exceptions;

public class OutOfRangeException extends Exception {

 /**
  * 
  */
 private static final long serialVersionUID = 1L;
 
 public OutOfRangeException(String msg){
  super(msg);
 }
 
}
package nasa.exceptions;

public class InvalidInputException extends Exception{

 /**
  * 
  */
 private static final long serialVersionUID = 1L;
 
 public InvalidInputException(){
  super();
 }
 
 public InvalidInputException(String msg){
  super(msg);
 }
 
}

TestMain would be the point of entry.

Cheers,
Bragaadeesh.

11 comments:

Nadir Saghar said...

I don't think posting solution is a bad idea. Don't you think TW is aware of the fact that their questions & solutions are available on the net? Still, they have not changed the problem set. A right candidate will make it through whether or not he uses the posted solutions.

Bragaadeesh said...

@Nadir : 100% true

Gonzalo said...

Actually, they probably think that the solution is not the code but the process to reach the code.


Anyway... Bragaadeesh, what's class Heading supposed to represent?

Vinay Taneja said...

I agree with Gonzalo and Nadir.
Here are few points for this code:
1) not a production quality code, it does not contain docs about class purpose.
2) no need of class Constants, you don't need a class for that, it should be defined in interface.
3) ISignal interface needs to be broken in a class and interface:
a) class representing bounds and initial position (initial pos not mandatory in a class it can be constructor arguments)
b) a class/interface representing the command. A rover can get commands multiple time but this implementation does not have that possibility. BTW what does it mean by data, it should be command.
4) ContolPanel should not contain public static bound_x and bound_y, being static no possibility of deploying two rovers on two different locations.
5) if Nasa class is an executer, it does not make sense, its execute method will execute same thing again and again. at least it should take argument of type mentioned in point 3b to reposition a rover. What if I do not invoke execute and call getFinalPosition{why final position why not just position}.
6) parseCommand in Heading, name does not say that it will parse and take any action both. Name suggests only parsing is done.


class name Nasa seems to be funny, if you want to create two rovers, you will create two Nasa instances :D does it mimic real life scenario (fails in OOPS where each object represent a software version of real life entity).

Bragaadeesh said...

@Vinay: Much appreciate your inputs!!!

SagaR said...

From Vinay comment:
>>2) no need of class Constants, you don't need a class for that, it should be defined in interface.<<
Don't abuse interface, just because by default all variable declared in interface are "public static final" doesn't mean constants are declared in them. Use enum.

vignesh said...

Thank u very much. its much useful

Gayathri said...

Thanks for your information...
Am gonna attend interview on jan 27 th,Can u pls guide me to get placement in thoughtworks...

Chris Aitchison said...

Here's a solution in 3 lines of Ruby code. Not sure if it's what TW is looking for though :D

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

visalakshi said...

Am gonna attend interview on aug 4th,Can u pls guide me to get placed in thoughtworks...

Manikesh said...

TW does not look for solution alone, they basically see the approach, this code will be straight away rejected. I am not sure if it was written keeping TW in mind.. this can be solved using 3 design patterns..

1. state pattern
2. strategy pattern
3.command pattern

This is what they see, I am writing the code using strategy and command pattern, will share the code for needy. Dont take TW interview lightly, it is very hard to clear, even a single small mistake can cause your rejection... look at below link for more details....

http://nikunjsoni.com/interview-at-thoughtWorks