package hw1;

import java.util.ArrayList;
import java.util.Arrays;
import java.io.*;

public class EightPuzzle {
	
	Node root;
	Node goal;
	int totalVisited = 0;
	int totalDiscovered = 0;
	ArrayList<Node> path = new ArrayList<Node>();
	
	public EightPuzzle(int[] root, int[] goal) {
		this.root = new Node(root);
		this.goal = new Node(goal);		
	}
	
	private boolean solve(String searchType) {
		totalVisited = 0;
		ArrayList<String> discovered = new ArrayList<String>();
		ArrayList<Node> toVisit = new ArrayList<Node>();
		ArrayList<Integer> toVisitLC = new ArrayList<Integer>();
		toVisit.add(root);
		if (searchType == "a*lc" || searchType == "a*lc2m")
			toVisitLC.add(0);
		
		int weight;
		if (searchType == "a*lc2m")
			weight = 2;
		else
			weight = 1;
		
		while (toVisit.size() != 0) {
			Node n;
			if (searchType == "dfs") {
				n = toVisit.remove(toVisit.size()-1);
			}
			else if (searchType == "bfs") {
				n = toVisit.remove(0);
			}
			else { // searchType == "a*" || "a*lc" || "a*lc2m"
				int bestNode = 0;
				int bestDist = 0;
				for (int i = 0; i<toVisit.size(); i++) {
					Node node = toVisit.get(i);
					int g = node.getLevel();
					int h = getManhattanDistance(node.getValue(), goal.getValue());
					int f = g + weight*h;
					if (searchType == "a*lc" || searchType == "a*lc2m")
						f += 2*toVisitLC.get(i);
					if (i == 0 || f < bestDist) {
						bestNode = i;
						bestDist = f;
					}
				}
				n = toVisit.remove(bestNode);
				if (searchType == "a*lc" || searchType == "a*lc2m")
					toVisitLC.remove(bestNode);
			}

			totalVisited += 1;
			totalDiscovered = totalVisited + toVisit.size();
			
			if (!Arrays.equals(n.getValue(), goal.getValue())) {
				System.out.println(n.getLevel() + " " + totalVisited + " " + totalDiscovered);
				ArrayList<Node> children = n.getChildren();
				for (Node child : children) {
					if (!discovered.contains(child.getValueString())) {
						toVisit.add(child);
						discovered.add(child.getValueString());	
						if (searchType == "a*lc" || searchType == "a*lc2m")
							toVisitLC.add(getLinearConflict(child.getValue(), goal.getValue()));
					}
				}
			}
			else {
				path.add(n);
				while (n.getParent() != null) {
					n = n.getParent();
					path.add(0, n);
				}
				return true; // Solution Found!
			}
		}
		return false; // No Solution Exists.
	}

	private static int getManhattanDistance(int[] state, int[] goal) {
		int dist = 0;
		for (int i = 1; i < 9; i++) {
			int index = 0;
			for (int j = 0; i < 9; j++) {
				if (state[j] == i) {
					index = j;
					break;
				}
			}
			int row_i = index / 3;
			int col_i = index % 3;
			for (int j = 0; i < 9; j++) {
				if (goal[j] == i) {
					index = j;
					break;
				}
			}
			int row_f = index / 3;
			int col_f = index % 3;
			dist += Math.abs(row_i - row_f) + Math.abs(col_i - col_f);
		}
		return dist;
	}
	
	@SuppressWarnings("unused")
	private static int getHammingDistance(int[] state, int[] goal) {
		int matches = 0;
		for (int i=0; i<9; i++) {
			if (state[i] == goal[i] && state[i] != 0)
				matches++;
		}
		return 8-matches;
	}
	
	private static int getLinearConflict(int[] state, int[] goal) {
		int conflict = 0;
		for (int i=0; i<3; i++) {
			int[] r = {state[3*i],state[3*i+1],state[3*i+2]};
			int[] g = {goal[3*i],goal[3*i+1],goal[3*i+2]};
			if ((r[0]>0 && r[0] == g[2] && ((r[1]>0 && (r[1] == g[0] || r[1] == g[1])) || (r[2]>0 && (r[2] == g[0] || r[2] == g[1])))) ||
			    (r[0]>0 && r[0] == g[1] && ((r[1]>0 && r[1] == g[0]) || (r[2]>0 && r[2] == g[0]))) ||
			    (r[1]>0 && r[1] == g[2] && ((r[2]>0 && (r[2] == g[1] || r[2] == g[1])))) ||
			    (r[2]>0 && r[2] == g[0] && r[1]>0 && r[1] == g[1])) {
				conflict++;
			}
			if (r[0]>0 && r[0] == g[2] && r[1]>0 && r[1] == g[1] && r[2]>0 && r[2] == g[0])
				conflict++;
		}
		for (int i=0; i<3; i++) {
			int[] r = {state[i],state[i+3],state[i+6]};
			int[] g = {goal[i],goal[i+3],goal[i+6]};
			if ((r[0]>0 && r[0] == g[2] && ((r[1]>0 && (r[1] == g[0] || r[1] == g[1])) || (r[2]>0 && (r[2] == g[0] || r[2] == g[1])))) ||
			    (r[0]>0 && r[0] == g[1] && ((r[1]>0 && r[1] == g[0]) || (r[2]>0 && r[2] == g[0]))) ||
				(r[1]>0 && r[1] == g[2] && ((r[2]>0 && (r[2] == g[1] || r[2] == g[1])))) ||
				(r[2]>0 && r[2] == g[0] && r[1]>0 && r[1] == g[1])) {
				conflict++;
			}
			if (r[0]>0 && r[0] == g[2] && r[1]>0 && r[1] == g[1] && r[2]>0 && r[2] == g[0])
				conflict++;
		}
		return conflict;
	}
	
	private void printAnswers() {
		int[] r = root.getValue();
		int[] g = goal.getValue();
		System.out.println();
		System.out.println(r[0] + " " + r[1] + " " + r[2] + "       " + g[0] + " " + g[1] + " " + g[2]);
		System.out.println(r[3] + " " + r[4] + " " + r[5] + "  -->  " + g[3] + " " + g[4] + " " + g[5]);
		System.out.println(r[6] + " " + r[7] + " " + r[8] + "       " + g[6] + " " + g[7] + " " + g[8]);
		System.out.print("Moves: (");
		System.out.print(path.size()-1);
		System.out.print(") ");
		for (int i=1; i<path.size(); i++) {
			Node n = path.get(i);
			System.out.print(n.getDirection());
		}
		System.out.println("\nNodes Visited: " + totalVisited);
		System.out.println("Nodes Generated: " + totalDiscovered);
	}
	
	private void printPathToFile(String filename) {
		try {
			FileOutputStream out = new FileOutputStream(filename);
			PrintStream p = new PrintStream(out);
			for (int i=0; i<path.size(); i++) {
				int [] state = path.get(i).getValue();
				p.println(state[0] + " " + state[1] + " " + state[2]);
				p.println(state[3] + " " + state[4] + " " + state[5]);
				p.println(state[6] + " " + state[7] + " " + state[8]);
				p.println();
			}
		} catch (FileNotFoundException e) {
			System.out.println("Error with output to file.");
		}
	}
		
	public static void main(String[] args) {
		
		ArrayList<int[]> startStates = new ArrayList<int[]>();
		ArrayList<int[]> goalStates  = new ArrayList<int[]>();
		
		int[] start, goal;
		
		start  = new int[] {2, 8, 3, 1, 6, 4, 7, 5, 0};
		goal   = new int[] {1, 2, 3, 8, 0, 4, 7, 6, 5};
		// (Case 1)  DFS: 21540 22381 39012; BFS: 6 73 123; A*: 6 7 13
		startStates.add(start); goalStates.add(goal);

		start  = new int[] {2, 8, 3, 1, 6, 4, 7, 0, 5};
		goal   = new int[] {2, 8, 3, 1, 6, 4, 7, 5, 0};
		// (Case 2)  DFS: 1 2 4; BFS: 1 4 8; A*: 1 2 4
		startStates.add(start); goalStates.add(goal);
		
		start  = new int[] {2, 1, 6, 4, 0, 8, 7, 5, 3};
		goal   = new int[] {2, 8, 1, 4, 6, 0, 7, 5, 3};
		// (Case 3)  DFS: 52269 131505 167835; BFS: 5 64 119; A*: 5 6 13
		startStates.add(start); goalStates.add(goal);
		
		start  = new int[] {2, 8, 1, 0, 4, 3, 7, 6, 5}; // Medium
		goal   = new int[] {1, 2, 3, 8, 0, 4, 7, 6, 5};
		// (Case 4)  DFS: 25125 160710 179978; BFS: 9 343 560; A*: 9 16 28
		startStates.add(start); goalStates.add(goal);
		
		start  = new int[] {2, 8, 1, 4, 6, 3, 0, 7, 5}; // Hard
		goal   = new int[] {1, 2, 3, 8, 0, 4, 7, 6, 5};
		// (Case 5)  DFS: 28884 157389 179192; BFS: 12 1619 2560; A*: 12 26 47
		startStates.add(start); goalStates.add(goal);

		start  = new int[] {5, 6, 7, 4, 0, 8, 3, 2, 1}; // Worst
		goal   = new int[] {1, 2, 3, 8, 0, 4, 7, 6, 5};
		// (Case 6)  DFS: 4578 4702 8352; BFS: 30 181364 181440; A*: 30 3470 5196
		startStates.add(start); goalStates.add(goal);

		start  = new int[] {8, 7, 6, 1, 0, 5, 2, 3, 4}; // Test
		goal   = new int[] {1, 2, 3, 8, 0, 4, 7, 6, 5};
		// (Case 7)  DFS: 25302 26393 45795; BFS: 28 180007 181152; A*: 28 10127 15405
		startStates.add(start); goalStates.add(goal);
		
		start  = new int[] {8, 7, 6, 0, 4, 1, 2, 5, 3}; // Most moves needed (31)
		goal   = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8}; 
		// (Case 8)  DFS: 40757 44186 73832; BFS: 31 181439 181440; A*: 31 18476 26996
		startStates.add(start); goalStates.add(goal);
		
		start  = new int[] {8, 0, 6, 5, 4, 7, 2, 3, 1}; // Most moves needed (31)
		goal   = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8};
		// (Case 9)  DFS: 18055 166721 180799; BFS: 31 181440 181440; A*: 31 18476 26996
		startStates.add(start); goalStates.add(goal);

		start  = new int[] {8, 5, 6, 7, 2, 3, 4, 1, 0}; // Most solutions possible (64)
		goal   = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8};
		// (Case 10) DFS: 55752 126735 164919; BFS: 30 181259 181438; A*: 30 13373 19937
		startStates.add(start); goalStates.add(goal);

		int tc = 10; // ENTER TEST CASE NUMBER HERE
		
		EightPuzzle puzzle = new EightPuzzle(startStates.get(tc-1), goalStates.get(tc-1));
		
		long startTime = System.currentTimeMillis(); 
		boolean solvable = puzzle.solve("a*lc2m"); // "dfs" || "bfs" || "a*" || "a*lc" || "a*2m"
		float elapsedTimeSec = (System.currentTimeMillis() - startTime) / 1000F; 
		
		if (solvable) { 
			puzzle.printAnswers();
			puzzle.printPathToFile("solution.txt");
			System.out.println("Elapsed Time: " + elapsedTimeSec + " sec.");
		}
		else {
			System.out.println("No solution exists.");
		}	
	}
}