Mars Rovers

This is my solution for the famous Mars Rovers problem. The problem is a typical random walk simulation problem with input data coming from user. I wrote this in Java in 2007. Looking back, I do admit that there is a lot of verbosity here. In a more expressive language, the solution could be reduced to half, I am sure.

package com.nasa.rovers.data;

//Enumerator for Directions (N,E, W, S)
/*
 * Each direction is defined as a set of 1 step move from (0,0) in that direction
 * so NORTH is (0,1) and EAST is (1,0) and SOUTH is (0,-1) and so on
 *
 */
public enum DIR {
	N(0, 1), //NORTH
	E(1, 0), //EAST
	S(0, -1), //SOUTH
	W(-1, 0); //WEST

	private XY xy;

	DIR(int x, int y) {
		xy = new XY(x, y);
	}

	public XY getXY() {
		return xy;
	}

	public DIR left() {
		//return the left (i.e. anti clockwise) move of 'this' direction
		switch (this) {
		case N:
			return W;
		case E:
			return N;
		case S:
			return E;
		case W:
			return S;
		}

		throw new AssertionError("Unknown direction: " + this);
	}

	public DIR right() {
		//return the right (i.e. clockwise) move of 'this' direction
		switch (this) {
		case N:
			return E;
		case E:
			return S;
		case S:
			return W;
		case W:
			return N;
		}

		throw new AssertionError("Unknown direction: " + this);
	}

}

package com.nasa.rovers.data;

/*
 * Encapsulation for (x,y) coordinates
 * Needed because they are everywhere.
 */
public class XY
{

	private int x = 0;
	private int y = 0;

	public XY() {};

	public XY(int x, int y)
	{
		this.x=x;
		this.y=y;
	}

	public XY(XY xy)
	{
		this.x = xy.x;
		this.y = xy.y;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}

	public void add(XY xy)
	{
		this.x = this.x + xy.getX();
		this.y = this.y + xy.getY();

	}

	public void scale(int m)
	{
		this.x *= m;
		this.y *= m;
	}

	public String toString()
	{
		return "(" + x + "," + y + ")";
	}

	public static XY add(XY from, XY to)
	{
		XY result = new XY(from);
		result.add(to);
		return result;
	}

}

package com.nasa.rovers.data;

import java.util.ArrayList;
import java.util.List;

//Define the boundaries of the surface
public class Map {

	private XY left  = new XY(0,0);
	private XY right = left;

	private int maxX = right.getX();
	private int maxY = right.getY();

	public int getMaxX() {
		return maxX;
	}

	public int getMaxY() {
		return maxY;
	}

    public Map() {};

	public Map(XY right)
	{
		this.right = new XY(right);

		maxX = right.getX();
		maxY = right.getY();
	}

	public void setBoundary(XY right)
	{
		this.right = new XY(right);
		maxX = right.getX();
		maxY = right.getY();
	}

	/*
	 * Check if the coordinates are on the map or outside
	 */
	public boolean onMap(XY xy)
	{
		if ((0 <= xy.getX() && xy.getX() <= maxX) &&
		   (0 <= xy.getY() && xy.getY() <= maxY))
			return true;
		else
			return false;
	}

}

package com.nasa.rovers.data;

public class Rover
{

	private XY xy;
	private DIR dir;

	private boolean debug = Boolean.getBoolean("debug");

	public Rover() {};

	public Rover(int x, int y, DIR d)
	{
		xy = new XY(x,y);
		this.dir = d;
	}

	public XY getXY() {
		return xy;
	}

	public void setXY(XY xy) {
		this.xy = xy;
	}

	public DIR getDir() {
		return dir;
	}

	public void setDir(DIR dir) {
		this.dir = dir;
	}

	public void move()
	{
		xy.add(dir.getXY());
	}

	public void moveBy(int m)
	{
		XY moveBy = new XY(dir.getXY());
		moveBy.scale(m);
		xy.add(moveBy);
	}

	public void leftSpin()
	{
		this.dir = this.dir.left();
	}

	public void rightSpin()
	{
		this.dir = this.dir.right();
	}

    /*
     * Heart of the system
     * Navigates based on plan (string of instruction characters) and
     * a map that defines the boundaries
     * So...
     * The rover knows where it is going
     *
     * TODO implement logic to avoid collision with other rovers
     */
	public void navigate(String plan, Map map)
	{
		//must check if boundaries are crossed
		//rover must have knowledge of planet (map)

		char[] instructions = plan.toCharArray();
		char ins = 0;

		int moveX = 0;
		int moveY = 0;
		XY moveTo = null;

		print("start");
		print(this);

		for (int i =0; i < instructions.length; i++)
		{
			print(instructions[i]);
			switch (instructions[i])
			{
			case 'L' : leftSpin();break;
			case 'R' : rightSpin(); break;
			case 'M' :
				//check if it's a valid move
				//a move is invalid if it takes the rover beyond the boundary

				//find out what the final destination will be
				moveTo = XY.add(this.xy, this.dir.getXY());

				if (map.onMap(moveTo))
				{
					//safe move as it doesn't take us out of the boundaries
					move();
				}
				else
				{
					//don't move
					//should we throw an exception?
					print("invalid move");
				}
				break;

			default: //do nothing; we just ignore all crappy instructions.
			}

			print(this);
		}

		System.out.println(this);
		print("end");
	}

	public String toString()
	{
		return xy.toString() + "  " + dir.toString();
	}

	private void print(Object o)
	{
		if (debug) System.out.println(o);
	}
}

package com.nasa.rovers.control;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;

import com.nasa.rovers.data.DIR;
import com.nasa.rovers.data.Map;
import com.nasa.rovers.data.Rover;
import com.nasa.rovers.data.XY;

public class Navigator
{

	public static void main(String[] args)
	{
		System.exit(run(args));
	}

	public static int run(String[] args)
	{
		System.out.println("---Begin Program");

		try
		{

			Map map = new Map();

			String fileName = args[0]; //do basic authentication later

			//read input data
			BufferedReader f = new BufferedReader(new FileReader(fileName));
		    String line = null;

		    //read first line
		    line = f.readLine();
		    if (line != null)
		    {
		    	//top right coordinates
		    	line = line.trim();
		    	int x = Integer.parseInt(line.substring(0,1));
		    	int y = Integer.parseInt(line.substring(2));
		    	map.setBoundary(new XY(x,y));
		    }

		    int i = 1;
		    Rover r = null;
		    //TODO should we maintain a list of rovers
		    while (( line = f.readLine()) != null)
		    {
		    	line = line.trim();
		    	if (i % 2 != 0)
		    	{
		    		// first line of input for rover
			    	int x = Integer.parseInt(line.substring(0,1));
			    	int y = Integer.parseInt(line.substring(2,3));

			    	char d = line.charAt(4);
			    	switch (d)
			    	{
			    	case 'N': r = new Rover(x,y, DIR.N);break;
			    	case 'E': r = new Rover(x,y, DIR.E);break;
			    	case 'S': r = new Rover(x,y, DIR.S);break;
			    	case 'W': r = new Rover(x,y, DIR.W);break;
			    	default : r = new Rover(x,y, DIR.N);break; //create a new Rover anyway
			    	}

		    	}
		    	else
		    	{
		    		// second line of input
		    	    //TODO implement logic to avoid collision with other rovers

		    		r.navigate(line, map);
		    	}

		    	i++;

		    }

		}
		catch(Exception e)
		{
			e.printStackTrace();
			return (-1);
		}

		System.out.println("---End Program");
		return (0);
	}

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: