/* 8-puzzle using algorithm A*

This program tries to implement algorithm A*, but there are a couple of flaws.

Puzzle will use 1-D array to simulate 2-D array:
0 1 2
3 4 5
6 7 8
Note that the row number of index i is i/3 and the column number of i is i%3.
Instead of A[i][j] we write A[i*3+j]
Left(i) is i-1, right is i+1, north is i-3, south is i+3.

*/
import java.util.*;

// a puzzle state is a node in the search space:
class state implements HeapValue<state>
{
    char[] s; // 9-char array representing current state
    state parent; // pointer to parent state
    int dist; // distance (number of moves) from start state
    int cost; // dist + estimated dist to target
    boolean closed = false; // is node on interior?
    int spacei; // position of space char in string s
    public state(char[] x, state p) 
	{
	    s=x; parent=p;
	    for(int i=0;i<s.length;i++) 
		if (s[i]==' ') {spacei=i; i=s.length; }
	}//constructor
    public state(char[] x, state p, int si) 
	{
	    s=x; parent=p;  spacei=si;
	}
    public static boolean chareq(char[] a, char[] b)
    {
	if (a.length!=b.length) return false;
	for(int i=0;i<a.length;i++) if (a[i]!=b[i]) return false;
	return true;
    }
    public boolean equals(Object b) 
    {  // check if char[] are the same
	char[] t = ((state)b).s;
	return chareq(s,t);
    }
    public int compareTo(state x) { return cost-x.cost; }

    public void copyTo(state c)
    {
	if (c==null) return;
	c.s = s; c.parent=parent; c.spacei=spacei;
	c.dist = dist;	c.cost = cost;
	c.closed = closed;
    }
    protected int hi = -1; // for HeapValue interface
    public int getIndex() { return hi;}
    public void setIndex(int i) { hi=i;}

    // method to destructively invert a state-lists' parent pointers,
    // return pointer to reversed list (new first state)
    public static state reverse(state S)
    {
	state prev = null;
	state current = S;
	while (current!=null)
	    {   state next = current.parent;
		current.parent = prev;
		prev = current;
		current = next;
	    }
	return prev;
    }// destructive reverse
}//state

public class puzzle
{
    // calculate index of neighbor, return -1 if invalid
    static int right(int i) 
    { if (i<8 && i/3==(i+1)/3) return i+1; else return -1; } // check same row
    static int left(int i)
    { if (i>0 && i/3==(i-1)/3) return i-1; else return -1; }
    static int up(int i)
    { if (i>2) return i-3; else return -1; } 
    static int down(int i)
    { if (i<6) return i+3; else return -1; }

    // need structure to hold 9! max states:
    FlexQueue<state> Open = new FlexQueue<state>(16);
    HashMap<String,state> States = new HashMap<String,state>();
    // do not pre-generate all 9! states
    
    //    String starts =  " ABCDEFGH";
    //    String targets = "ABCD EFGH";
    char[] start, target;

    public int scx; // number of states generated
    public int rpx; // number of Heap requeues

    // @Override the following in a subclass to improve performance.
    // estimate distance from current to target: number of different chars
    int heuristic(char[] current) 
    {
	int cx = 0; // count number of differences
	for(int i=0;i<9;i++) if (current[i]!=target[i]) cx++;
	return cx;
    }// heuristic

    state astar() // main search algorithm
    {
	scx = 1; // number of states generated, diagnostic counter
	rpx = 0; // number of reposition, better-route adjustments
	Open.setComparator( (x,y) -> y.compareTo(x) ); // inverts comparator
	state state0 = new state(start,null); // start state
	state0.dist = 0;
	state0.cost = heuristic(start);
	States.put(new String(start),state0);  // add to table of states
	Open.enqueue(state0);    // insert into Frontier queue/heap
	
	state last = null; // to be set and returned
	int[] Moves = new int[4];  // up to four possible moves each turn
	while (last==null && Open.size()>0) // main loop
	{
	    state current = Open.dequeue(); //remove lowest cost state from Open
	    if (state.chareq(current.s,target)) {last=current; break;}
	    current.closed = true; // move to interior
	    int si = current.spacei; // position of space
	    // examine each neighbor of current:
	    Moves[0] = up(si);  Moves[1] = down(si); 
	    Moves[2] = left(si); Moves[3] = right(si);
	    for(int dir:Moves)
		{
		    if (dir>=0) // if valid, move square into space
		    {
		      state neighbor = new state(current.s.clone(),current,dir);
		      //  System.out.println(si+ " , "+dir);  //error trace
		      neighbor.s[si] = neighbor.s[dir];
		      neighbor.s[dir] = ' ';  // new position of space
		      neighbor.dist = current.dist+1;
		      neighbor.cost = neighbor.dist + heuristic(neighbor.s);
		      //if (state.chareq(neighbor.s,target)) {last=neighbor;}
		      // default status = 1=frontier;
		      // check if state exists
		      String key = new String(neighbor.s);
		      state existing = States.get(key);
		      if (existing==null)
			  {
			      States.put(key,neighbor);
			      Open.enqueue(neighbor);
			      scx++; // increase state count
			  }
		      else if (!existing.closed && neighbor.cost<existing.cost)
			  {
			      neighbor.copyTo(existing);
			      Open.requeue(existing);
			      rpx++;
			  }
		      // else ignore neighbor
		    }// if valid move
		}// for each direction
	}//while !done
	return last;
    }//astar
   

    static void print2d(char[] s) // print char[] as 3x3 matrix
    {
	int k = 0;
	for(int i=0;i<3;i++)
	  {
	    for(int j=0;j<3;j++)
		System.out.print(s[k++]);
	    System.out.println();
	  }
	System.out.println();
    }//print2d

    public static void main(String[] av)
    {
	puzzle P = new puzzle();
	P.start = av[0].toCharArray();
	P.target = av[1].toCharArray();
	state path = P.astar();
	int moves = 0;
	while (path!=null)
	    { 
		//System.out.println(new String(path.s));
		print2d(path.s);
		path=path.parent;   moves++;
	    }
	System.out.println(moves+ " moves");
	System.out.println("number of states: "+P.scx);
	System.out.println("number of repositions: "+P.rpx);
    }//main
}// puzzle

// tests:
// java puzzle "A BCDEFGH" "CAB DEFGH"
// java puzzle " ABCDEFGH" "ABCD EFGH"


////// override heuristic:
class dijkstra extends puzzle  // pure Dijkstra doesn't use heuristic
{
    int heuristic(char[] current) 
    {
	return 0;
    }
}//dijkstra


class better extends puzzle
{
    int heuristic(char[] s)
    {
	int ax = 0;
	for(int i = 0;i<9;i++) // for each char in s
	    {
		// lookup position of char in target
		int ti = 0;
		for(int j=0;j<9;j++) if (target[j]==s[i]) {ti = j; j=9;}
		int rowi = i/3, coli = i%3;
		int rowt = ti/3, colt = ti%3;
		int dx = Math.abs(rowi-rowt), dy = Math.abs(coli-colt);
		ax += dx + dy;
	    }//for i
	return ax;
    }//heuristic
}