RoomPather.java

/*
	RoomPather.java
	By: Kevin Hulin
	
	Upon reading the challenge problem, I immediately thought of a math problem
	that I had read an article about.  The NP-C salesman problem, or "Given
	a set of houses to visit, give the shortest path that touches each 
	house only once."  This idea being set in my head and a little more research
	on the problem led me to design a program that takes a set of coordinates
	and returns an "almost shortest" path that touches each point exactly once.
	
	The basic algorithm that I have implemented is as follows:
		given a starting position and a list of points to visit,
		find the closest point to here and move there
		repeat until all points have been reached.
		
	This algorithm is seriously and obviously flawed in that a point in the 
	list that does not come close to any other point will be saved as the
	last point to visit, and thus will yield a lengthy leg that could no
	doubtedly been shortened.  You can see in my coding that I had started on
	a second algorithm to take these cases into account, however, rather than
	go mad over a challenging problem, I took a pause.  Now, as the close of the
	challenge is here, I will submit my progress thus far.  If, in a 
	future assignment, it becomes appearant that such a solution is necessary,
	I will complete the algorithm.
	
	(Note:  As a NP-C problem, the absolute answer can not be known without 
	iterating through every possible solution.  Thus, I decided to throw out
	this answer and settle for an estimated solution that could be obtained 
	in much fewer cycles.)
	
	Statistics:  Given an area of 1000x1000 units^2 containing 100 points,
		one should expect to travel between 8500 and 9500 linear units
	
	
	The Program:
	
	Use an optional command line argument to let the program know how many times you
	want to run the test.  This was merely for testing statistics and can be
	ignored.
	
	class RoomPather
		go() - creates a level consisting of 100 rooms.  Each room is 
		assigned a random coordinate pair (0,10000], making sure that no
		two rooms have identical coordinates.
	class Statistics - for future algorithm testing purposes
		add(double) - include a new value to be considered in statistics calculations
		avg(), max() - average and max for statistics values
	class Room
		Room(Coord) - Constructor, sets location of room
		setClosest(Room) - Mutator for setting the room that is closest
		getClosest() - returns room that was set as closest
	class Level
		findShortestPath1() - iterates through each room using the algorithm
			mentioned above.  Returns the distance required to vist
			each room in the level.
		findShortestPath2() - iterates through each room, creating a collection
			of libraries that each contain the distance from one room to every 
			other room in the level.
			(I stopped programming here, closing it off to basically do
			the same thing that the first algorithm did.)
	class Coord
		Coord(int x, int y) - constructor, sets the x and y coordinate pair
		static distance(Coord a, Coord b) - returns the distance between 
			two coordinate pairs being represented as Coord objects
			
	class Library - inspired by other programming language's "library" functionality
		Allows for easy access to previously calculated data.
		getHashMap() - returns the library in a hash map of type <Room,Double>
*/
import java.util.*;
public class RoomPather{
	private static LinkedList<Coord> coords = new LinkedList<Coord>();
	private static Level level;
	private static Level level2 ;
	private static Statistics s = new Statistics();
	public static void main(String[] args){
		double total = 0;
		int iter = 1;
		for(String s : args)
			iter = Integer.parseInt(s);
		
		for(int i = 0; i < iter; i++){
			s.add(go());
		}
		System.out.println(s.toString());
	}
	
	public static double go(){
		int randX, randY;
		coords.clear();
		Coord c;
		for(int i = 0; i < 100; i ++){
			randX = (int)(Math.random() * 1000);
			randY = (int)(Math.random() * 1000);
			c = new Coord(randX, randY);
			if(check(c))
				coords.add(c);
		}
		
		level = new Level(coords.toArray(new Coord[coords.size()]));
		System.out.println(level.toString());
		
		//System.out.println(level.findShortestPath1());
		//level2.findShortestPath2();
		//System.out.println(level2.findShortestPath2());
		level.findShortestPath2();
		return level.findShortestPath1();
	}
	
	public static boolean check(Coord c){
		for(Coord co : coords){
			if(c.equals(co))
				return false;
		}
		return true;
	}
}
class Statistics{
	private ArrayList<Double> vals = new ArrayList<Double>();
	public Statistics(){
	}
	
	public void add(double d){
		vals.add(new Double(d));
	}
	public double avg(){
		double a = 0;
		for(Double d : vals){
			a += d;
		}
		a = a/vals.size();
		return a;
	}
	public double max(){
		double m = Double.MIN_VALUE;
		for(Double d : vals){
			if (d > m)
				m = d;
		}
		return m;
	}
	public String toString(){
		return "Avg: " + avg() + "\nMax: " + max();
	}
	
}
class Room{
	private int id;
	private int load;
	private Room closest;
	private Coord coord;
	private static int idLast = 0;
	
	public Room(Coord c){
		coord = c;
		id = idLast ++;
	}
	public Room(){
		coord = null;
	}
	public Coord getCoord(){
		return coord;
	}
	public String toString(){
		try{
			return id + ": (" + coord.getX() + "," + coord.getY() + ")";
		}
		catch(Exception ex){
			
			return "ERROR: Invalid Coord";
		
		}
	}
	public Room getClosest(){
		return closest;
	}
	public void setClosest(Room r){
		closest = r;
	}
}
class Level{
	private ArrayList<Room> rooms = new ArrayList<Room>();
	private ArrayList<Library> libs = new ArrayList<Library>();
	
	public Level(Coord[] cs){
		
		for(Coord c:cs){
			rooms.add(new Room(c));
		}
	}
	public String toString(){
		String s = "";
		for(Room r:rooms){
			s += r.toString() + "\n";
		}
		return s;
	}
	public double findShortestPath1(){
		double currentCost = 0;
		boolean go = true;
		Room start = new Room(new Coord(0,0));
		Room current = start;
		Room min ;
		while(!rooms.isEmpty()){
			min = new Room(new Coord(9999,9999)); 
			for(Room r : rooms){
				if (Coord.distance(current.getCoord(), r.getCoord()) < Coord.distance(current.getCoord(), min.getCoord()))
					min = r;
			}
			
			rooms.remove(min);
			currentCost += Coord.distance(current.getCoord(), min.getCoord());
			System.out.println( min.toString() + "\t" + Coord.distance(current.getCoord(), min.getCoord()));
			current = min;
		}
		return currentCost;
	}
	public double findShortestPath2(){

		for(Room r : rooms){
			Library l = new Library(r);
			libs.add(l);
			for(Room ro : rooms)
				l.add(ro, Coord.distance(ro.getCoord(), r.getCoord()));
		}
		//for(Library l : libs)
		//	System.out.println(l.toString());
		for(Library l: libs){
			Room root = new Room();
			Double close = new Double(9999.9);
			Room rClose = new Room();
			for(Map.Entry<Room,Double> e : l.getHashMap().entrySet()){
				if (e.getValue() == 0.0)  
					root = e.getKey();
				else if(e.getValue() < close){
					close = e.getValue();
					rClose = e.getKey();
				}
			}
			root.setClosest(rClose);
			
		}
		for(Room r : rooms){
			//System.out.println(r.toString() + "\t" + r.getClosest().toString());
		}
		return 0.0;
	}
}

class Coord{
	private int x;
	private int y;
	public int getX(){
		return x;
	}
	public int getY(){
		return y;
	}
	public static double distance(Coord a, Coord b){
		return Math.sqrt(Math.pow(a.getX() - b.getX(), 2) + Math.pow(a.getY() - b.getY(), 2));
	}
	public Coord(int a, int b){
		x = a;
		y = b;
	}
	public boolean equals(Coord c){
		return (c.getX() == x && c.getY() == y);
	}
}
class Library{
	HashMap<Room,Double> lib = new HashMap<Room,Double>();
	public Library(Room r){
		lib.put(r, new Double(0));
	}
	
	public void add(Room r, double dist){
		if(!lib.containsKey(r))
			lib.put(r, new Double(dist));
	}
	public HashMap<Room,Double> getHashMap(){
		return lib;
	}
	public String toString(){
		String s = "";
		double total = 0.0;
		for(Room k : lib.keySet()){
			s+= k.toString() + "\t" + lib.get(k) + "\n";
			total += lib.get(k);
		}
		s += total + "\n";
		return s;
	}
}