tsp.java

import java.io.*;
import java.util.*;


/**
 * Created with IntelliJ IDEA.
 * User: pradeepnayak
 * Date: 23/02/14
 * Time: 3:45 PM
 * To change this template use File | Settings | File Templates.
 */
public class tsp {

    private static ArrayList<Cell> maze = new ArrayList<Cell>();
    public static void main(String[] args) throws IOException{
        int taskNumber = Integer.parseInt(args[1]);
        if (taskNumber == 1)
            buildShortestPathGraph(args);
        else
        {
            buildShortestPathGraph(args);
            findShortestPath(args);
        }
    }

    private static void buildShortestPathGraph(String... args) throws IOException
    {
        //first build the maze
        BufferedReader inputFile = new BufferedReader(new FileReader(args[3]));
        PrintWriter pathLogFile = new PrintWriter(args[5]);
        PrintWriter traverseLogFile = new PrintWriter(args[7]);
        Maze maze = new Maze(inputFile);
        //get all the checkpoints
        Character [] checkpoints = maze.returnCheckpointNames();
        for (int i = 0;i<checkpoints.length;i++)
        {
            for (int j = i+1;j<checkpoints.length;j++)
            {
                traverseLogFile.println("from \'" + checkpoints[i] + "\' to \'" + checkpoints[j]+ "\'");
                traverseLogFile.println("---------------------------------------------");
                traverseLogFile.println("x,y,g,h,f");
                Maze tmpMaze = new Maze (maze);
                Map <Character, Cell> myMap = tmpMaze.returnCheckpoints();
                Cell startCell = new Cell (myMap.get(checkpoints[i]));
                Cell goalCell = new Cell (myMap.get(checkpoints[j]));
                AStar(startCell,goalCell,tmpMaze,pathLogFile,traverseLogFile);
                traverseLogFile.println("---------------------------------------------");
            }
        }
    }

    /*
        The A* algorithm is adapted from :  http://en.wikipedia.org/wiki/A*_search_algorithm
     */
    private static void AStar(Cell startCell, Cell goalCell, Maze maze, PrintWriter pathLogFile, PrintWriter traverseLogFile) throws IOException
    {
        List<Cell> visited = new ArrayList<Cell>();
        startCell.g_score = 0;
        startCell.f_score = startCell.g_score + tsp.manhattanDistacne(startCell,goalCell);

        PriorityQueue<Cell> openset = new PriorityQueue<Cell>(1, new Comparator<Cell>() {
            @Override
            public int compare(Cell o1, Cell o2) {
                if (o1.f_score == o2.f_score)
                {
                    if (o1.row != o2.row)
                        return (o1.row - o2.row);
                    else
                        return (o1.col - o2.col);

                }
                return (o1.f_score - o2.f_score);
            }
        });
        openset.add(startCell);

        while (!openset.isEmpty())
        {
            Cell current = openset.poll();
            traverseLogFile.println(current.col + "," + current.row + "," + current.g_score + "," + tsp.manhattanDistacne(current, goalCell) + "," + current.f_score);
            if (current.name.equals(goalCell.name)) {
                pathLogFile.println(startCell.name + "," + goalCell.name + "," + current.f_score);
                break;
            }
            visited.add(current);
            current.setVisited();
            List<Cell> neighbours = current.getNeighbours(maze,goalCell);
            for(Cell n: neighbours)
            {
                if (visited.contains(n) || n.isVistited())
                    continue;
                int tentative_g_score = current.g_score + tsp.manhattanDistacne(current,n);

                if (!openset.contains(n) || tentative_g_score < n.g_score)
                {
                    n.g_score = tentative_g_score;
                    n.f_score = n.g_score + tsp.manhattanDistacne(n,goalCell);
                    if (!openset.contains(n))
                    {
                        openset.add(n);
                    }
                }

            }

        }


    }
    private static void readInputFile(BufferedReader inputFile) throws IOException
    {

    }

    private static void findShortestPath(String... args) throws IOException
    {

    }

    public static int manhattanDistacne (Cell start, Cell end)
    {
        int distance = Math.abs(start.row-end.row) + Math.abs(start.col-end.col);
        return distance;
    }
}



class Cell {
    public int row, col;
    private boolean visited;
    Character name;
    public int f_score, g_score;

    public Cell(Cell newCell)
    {
        this.row = newCell.row;
        this.col = newCell.col;
        this.name = newCell.name;
        this.f_score = newCell.f_score;
        this.g_score = newCell.g_score;
        this.visited = newCell.visited;
    }

    Cell(int row, int col, Character name)
    {
        this.row = row;
        this.col = col;
        this.name = name;
        this.visited = false;
    }

    public boolean isVistited()
    {
        return this.visited;
    }

    public void setVisited()
    {
        this.visited = true;
    }

    public void unsetAllFields()
    {
        this.f_score = 0;
        this.g_score = 0;
        this.visited = false;
    }

    public boolean isWall()
    {
        if (this.name == '*')
            return true;
        else
            return false;
    }

    public List<Cell> getNeighbours(Maze maze, Cell goalCell){
        List<Cell> neighbours = new ArrayList<Cell>();
        Cell right = maze.returnCell(this.row , this.col + 1);
        Cell left = maze.returnCell(this.row, this.col - 1);
        Cell up =  maze.returnCell(this.row - 1, this.col);
        Cell down = maze.returnCell(this.row +1 , this.col);

        if (up!=null && !up.isVistited() && !up.isWall())
            neighbours.add(up);
        if (left!=null && !left.isVistited() && !left.isWall())
            neighbours.add(left);
        if (right!=null && !right.isVistited() && !right.isWall())
            neighbours.add(right);
        if (down!=null && !down.isVistited() && !down.isWall())
            neighbours.add(down);

        return neighbours;
    }
}

class Maze {

    private  ArrayList<Cell> mymaze = new ArrayList<Cell>();
    public int ROW_MAX, COL_MAX;
    private HashMap <Character,Cell> checkpoints = new HashMap <Character, Cell>();


    public Maze (Maze newMaze)
    {
        this.mymaze = new ArrayList<Cell>(newMaze.mymaze);
        this.ROW_MAX = newMaze.ROW_MAX;
        this.COL_MAX = newMaze.COL_MAX;
        this.checkpoints = new HashMap<Character, Cell>(newMaze.checkpoints);
        for(Cell m : this.mymaze)
        {
            m.unsetAllFields();
        }
    }

    Maze(BufferedReader inputFile) throws IOException
    {
        String str = null;
        int j = 0;
        while ((str = inputFile.readLine()) !=null)
        {
            for (int i=0;i<str.length();i++)
            {
                this.mymaze.add(new Cell(j,i,str.charAt(i)));
                if (str.charAt(i)!= '*' && str.charAt(i)!= ' ')
                {
                    this.checkpoints.put(str.charAt(i),new Cell(j,i,str.charAt(i)));
                }
                COL_MAX = i;
            }
            j++;
        }
        ROW_MAX = j;

    }

    public Cell returnCell(int x, int y)
    {
        for(Cell cell: mymaze)
        {
            if (cell.row == x && cell.col == y)
            {
                return cell;
            }
        }
        return null;
    }

    public Character[] returnCheckpointNames()
    {
        Map myMap = this.checkpoints;
        Character [] result = this.checkpoints.keySet().toArray(new Character[this.checkpoints.keySet().size()]);
        Arrays.sort(result);
        return result;
    }

    public HashMap<Character, Cell> returnCheckpoints()
    {
        return this.checkpoints;
    }

}