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);
}
}
Advertisement
