Tuesday, August 25, 2009

Mars Rover Problem from Thoughtworks - Design considerations

This is my design for the problem below.
I have my code if you need guidelines but I never heard back from them on anything further after submitting my code!
Problem Objective


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
Design Considerations

The solution could have been devised using any of these three design patterns –
Strategy Pattern
Command Pattern
State Pattern

I have chosen to use Command Pattern so that each of the commands issued to the rovers, can be treated as objects of a same command family. The execute method accepts the rover object in the parameter so that the initial state (direction and coordinates) of the rover can be determined. Based on the initial state, the new state of the rover is calculated and maintained.

There are 6 main components in the solution -

1. Rover Class (sg.tw.marsrover)
This class contains and maintains the Rover Position (Coordinates and Direction).
This class also contains the list of Command objects issued to the rover.

In addition to the getter/setter methods for the rover’s state, there are additional methods to –

moveStraight() – This method advances the rover one step ahead from its current position.
For example if the rover’s current direction is North and coordinates are (2,5), then the new coordinates of rover will be (2,6) in North. There is no change in direction.

turnRight() – This method turns the rover 90 degrees in its right. The method changes the direction of the rover but there are no changes in the coordinates.

turnLeft() – This method turns the rover 90 degrees in its left. The method changes the direction of the rover but there are no changes in the coordinates.

navigate() – Navigate the rover based on the set of commands issued. The method also maintains the state of the rover after invocation of each of the command. It returns the final position of the rover.

2. Position Class (sq.tw.marsrover.Location)
This class holds the position data of a rover including the Coordinates of the rover and the Direction of a rover.

3. Command Interface (sg.tw.marsrover.command)
The classes in commad package are used to implement the command pattern for each of the three commands.
The execute() method accepts rover object as parameter to invoke the command.

4. Plateau Class (sg.tw.marsrover)
The Plateau class is used to hold the coordinates of mars plateau grid.

5. Utility Classes (sg.tw.marsrover.util)
This package contains all the utility classes used to build the solution –
The Interface InputDataReader contains two methods –
getPlateau() – This method reads the input, parses it and returns a valid Plateau object.
getRoverList() – This method reads the input, parses it and returns a valid list of rovers launched on the plateau.
If there are other input modes other than a standard text file, for example a stream of data, remote objects or a voice input, the respective reader classes need to implement this interface similar to the FileInputReader class.

6. MarsRoverApp Class (sg.tw.marsrover)
This class contains the main method to launch the application.

Assumptions
1. The application is based on an integer coordinate system.
2. The plateau is rectangular with coordinates as (bottom, left, top, right).
3. When the next rover is navigated, the previous rover has been removed from the plateau (i.e. No two rovers can have the same location in the grid thereby avoiding a possible collision scenario).

Build/Environment Details
JDK Version – 1.4.2_11
IDE – Eclipse Version 3.4.0

Further Work
1. Exception Handling/ Log4j – A proper strategy to handle exceptions. Currently the solution propagates all exceptions into an ApplicationException which is thrown from the main class onto the user console.
Also, further work is required to decide whether the application should terminate after an invalid scenario or try to resume after throwing an exception.

2. Adding Unit tests – The current solution doesn’t contains any Junits and was manually tested.

3. Implementation of more boundary conditions and error handling scenarios for null objects. For example-
Test to verify that Rovers are landed inside the Plateau

4. Handling various input types – The current application assumes that there is a valid Input file that contains the information of Grid coordinates and Rover positions alongwith commands.
The format of the input file is as given in the problem objective. The current solution does not support any deviation from this format.

5. Build scripts and batch file/shell script to deploy and run the application – The application was run directly from eclipse IDE. There is no build script to deploy the code.

Note : To run the application, you need to provide the input file name and path as parameters to the main method.

Basics on Web application deployment

This post contains links to some nice articles I found for web.xml details

Web Application deployment basics

Web Application basics