19 February 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. :)

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).

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.

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


Test Input:
5 5
1 2 N
3 3 E

Expected Output:
1 3 N
5 1 E


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

TestMain would be the point of entry.



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


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....