/**
 *
 * Copyright (C) 2005 Uday Bondhugula
 *
 * This code is available under the GNU GPL version 2. See the file LICENSE
 * for terms and conditions.
 *
 */

public class Heuristics {
	public final static int FACE_NONE=-1;  // orthogonal to x-axis and visible
	public final static int FACE_XV=0;     // orthogonal to x-axis and visible
	public final static int FACE_XH=1;     // orthogonal to x-axis and hidden
	public final static int FACE_YV=2;     // and so on
	public final static int FACE_YH=3;
	public final static int FACE_ZV=4;
	public final static int FACE_ZH=5;
	

	public final static byte NONE = 6; 
	public final static byte BLUE = 0; 
	public final static byte WHITE = 1; 
	public final static byte GREY = 2; 
	public final static byte RED  = 3; 
	public final static byte YELLOW = 4; 
	public final static byte GREEN  = 5;


	public static Triplet [][][] face = new Triplet[3][3][3];
	public static Triplet [][][] pos  = new Triplet[7][7][7];

	
	// determine what all faces of each cubie matter in solving the cube
	public static void faceinit()	{
		face[0][0][0] = new Triplet(FACE_XH,FACE_YH,FACE_ZH);
		face[0][1][0] = new Triplet(FACE_XH,FACE_NONE,FACE_ZH);
		face[0][2][0] = new Triplet(FACE_XH,FACE_YV,FACE_ZH);
		face[1][0][0] = new Triplet(FACE_NONE,FACE_YH,FACE_ZH);
		face[1][2][0] = new Triplet(FACE_NONE,FACE_YV,FACE_ZH);
		face[2][0][0] = new Triplet(FACE_XV,FACE_YH,FACE_ZH);
		face[2][1][0] = new Triplet(FACE_XH,FACE_NONE,FACE_ZH);
		face[2][2][0] = new Triplet(FACE_XV,FACE_YV,FACE_ZH);
	
		face[0][0][2] = new Triplet(FACE_XH,FACE_YH,FACE_ZV);
		face[0][1][2] = new Triplet(FACE_XH,FACE_NONE,FACE_ZV);
		face[0][2][2] = new Triplet(FACE_XH,FACE_YV,FACE_ZV);
		face[1][0][2] = new Triplet(FACE_NONE,FACE_YH,FACE_ZV);
		face[1][2][2] = new Triplet(FACE_NONE,FACE_YV,FACE_ZV);
		face[2][0][2] = new Triplet(FACE_XV,FACE_YH,FACE_ZV);
		face[2][1][2] = new Triplet(FACE_XH,FACE_NONE,FACE_ZV);
		face[2][2][2] = new Triplet(FACE_XV,FACE_YV,FACE_ZV);
	
		face[0][0][1] = new Triplet(FACE_XH,FACE_YH,FACE_NONE);
		face[0][2][1] = new Triplet(FACE_XH,FACE_YV,FACE_NONE);
		face[2][0][1] = new Triplet(FACE_XV,FACE_YH,FACE_NONE);
		face[2][2][1] = new Triplet(FACE_XV,FACE_YV,FACE_NONE);
	}
		
	
		
	// initialize the correct positions of all cubies
	public static void initpos()	{	 
		pos[WHITE][RED][GREEN] = new Triplet(0,0,0);
		pos[WHITE][NONE][GREEN] = new Triplet(0,1,0);
		pos[NONE][WHITE][GREEN] = new Triplet(0,1,0);
		pos[WHITE][GREEN][NONE] = new Triplet(0,1,0);
		pos[WHITE][GREY][GREEN] = new Triplet(0,2,0);
		pos[NONE][RED][GREEN] = new Triplet(1,0,0);
		pos[RED][NONE][GREEN] = new Triplet(1,0,0);
		pos[RED][GREEN][NONE] = new Triplet(1,0,0);
		pos[NONE][GREY][GREEN] = new Triplet(1,2,0);
		pos[GREY][NONE][GREEN] = new Triplet(1,2,0);
		pos[GREY][GREEN][NONE] = new Triplet(1,2,0);
		pos[BLUE][RED][GREEN] = new Triplet(2,0,0);
		pos[BLUE][NONE][GREEN] = new Triplet(2,1,0);
		pos[NONE][BLUE][GREEN] = new Triplet(2,1,0);
		pos[BLUE][GREEN][NONE] = new Triplet(2,1,0);
		pos[BLUE][GREY][GREEN] = new Triplet(2,2,0);
	
		pos[WHITE][RED][YELLOW] = new Triplet(0,0,2);
		pos[WHITE][NONE][YELLOW] = new Triplet(0,1,2);
		pos[NONE][WHITE][YELLOW] = new Triplet(0,1,2);
		pos[WHITE][YELLOW][NONE] = new Triplet(0,1,2);
		pos[WHITE][GREY][YELLOW] = new Triplet(0,2,2);
		pos[NONE][RED][YELLOW] = new Triplet(1,0,2);
		pos[RED][YELLOW][NONE] = new Triplet(1,0,2);
		pos[RED][NONE][YELLOW] = new Triplet(1,0,2);
		pos[NONE][GREY][YELLOW] = new Triplet(1,2,2);
		pos[GREY][YELLOW][NONE] = new Triplet(1,2,2);
		pos[GREY][NONE][YELLOW] = new Triplet(1,2,2);
		pos[BLUE][RED][YELLOW] = new Triplet(2,0,2);
		pos[BLUE][NONE][YELLOW] = new Triplet(2,1,2);
		pos[BLUE][YELLOW][NONE] = new Triplet(2,1,2);
		pos[NONE][BLUE][YELLOW] = new Triplet(2,1,2);
		pos[BLUE][GREY][YELLOW] = new Triplet(2,2,2);
	
		pos[WHITE][RED][NONE] = new Triplet(0,0,1);
		pos[WHITE][NONE][RED] = new Triplet(0,0,1);
		pos[NONE][WHITE][RED] = new Triplet(0,0,1);
		pos[WHITE][GREY][NONE] = new Triplet(0,2,1);
		pos[NONE][WHITE][GREY] = new Triplet(0,2,1);
		pos[WHITE][NONE][GREY] = new Triplet(0,2,1);
		pos[BLUE][RED][NONE] = new Triplet(2,0,1);
		pos[NONE][BLUE][RED] = new Triplet(2,0,1);
		pos[BLUE][NONE][RED] = new Triplet(2,0,1);
		pos[BLUE][GREY][NONE] = new Triplet(2,2,1);
		pos[BLUE][NONE][GREY] = new Triplet(2,2,1);
		pos[NONE][BLUE][GREY] = new Triplet(2,2,1);
	}
	
	
	public static Triplet getVisible(Triplet cubelet)
	{
		return face[cubelet.x][cubelet.y][cubelet.z];
	}
	
	public static Triplet getCorrectPos(Cubelet cubepos, int x, int y, int z)
	{
		Triplet tempPos = new Triplet(x, y, z);
		Triplet facesVisible =  getVisible(tempPos);
		byte[] color = new byte[3];
		
		if(facesVisible.x == FACE_NONE)
		{
			color[1]=sort(cubepos.getColor(facesVisible.y),cubepos.getColor(facesVisible.z)).x;
			color[0]=NONE;
			color[2]=sort(cubepos.getColor(facesVisible.y),cubepos.getColor(facesVisible.z)).y;
		}
		else	if(facesVisible.y == FACE_NONE)
		{
			color[0]=sort(cubepos.getColor(facesVisible.x),cubepos.getColor(facesVisible.z)).x;
			color[1]=NONE;
			color[2]=sort(cubepos.getColor(facesVisible.x),cubepos.getColor(facesVisible.z)).y;
		}
		else if(facesVisible.z == FACE_NONE) 
		{
			color[0]=(byte)sort(cubepos.getColor(facesVisible.x),cubepos.getColor(facesVisible.y)).x;
			color[1]=(byte)sort(cubepos.getColor(facesVisible.x),cubepos.getColor(facesVisible.y)).y;
			color[2]=NONE;
                }else
		{
			color[0]=(byte)sort(cubepos.getColor(facesVisible.x),cubepos.getColor(facesVisible.y),cubepos.getColor(facesVisible.z)).x;
			color[1]=(byte)sort(cubepos.getColor(facesVisible.x),cubepos.getColor(facesVisible.y),cubepos.getColor(facesVisible.z)).y;
			color[2]=(byte)sort(cubepos.getColor(facesVisible.x),cubepos.getColor(facesVisible.y),cubepos.getColor(facesVisible.z)).z;
		}
		return pos[color[0]][color[1]][color[2]];
	}


	// for debugging purposes
	
	public static void main(String args[])
	{
		faceinit();
		initpos();
		Cubelet cubelet = new Cubelet();
		cubelet.colors[FACE_XV] = GREEN;
		cubelet.colors[FACE_XH] = 12;
		cubelet.colors[FACE_YV] = WHITE;
		cubelet.colors[FACE_YH] =10 ;
		cubelet.colors[FACE_ZV] =GREY;
		cubelet.colors[FACE_ZH] = 16;
		Triplet result = getCorrectPos(cubelet,2,2,2);
		if (result == null)	System.out.println("bug");
		System.out.println("Correct pos of this cube is "+result.x+'\t'+result.y+'\t'+result.z);
	}	


	public static Duplet sort(byte a, byte b)
	{
		Duplet temp = new Duplet() ;
		temp.x = smallest(a,b);
		temp.y = (byte)(a+b-smallest(a,b));
		return temp;
	}
	
	public static Triplet sort(byte a, byte b,byte c)
	{	Triplet trip = new Triplet();
		Duplet dup = new Duplet();
		dup = sort(a,b);	
		int pos = 0;
		if(c <dup.x){trip.x = c;trip.y = dup.x;trip.z = dup.y;}
		else
			if(c <dup.y){trip.x = dup.x ;trip.y = c ;trip.z = dup.y;}
			else    {trip.x  = dup.x;trip.y = dup.y;trip.z = c;}
		return trip;	
		
	}


	public static byte smallest(byte a,byte b)
	{
		if(a<=b) return a;
		return b;
	}

	public static float heur(Cube cube)	{
		if (cube.isSolved())	return 0;
		else{
			float cornerStrength=0, edgeStrength=0;
			Triplet correctPos;
			int which, deltaX, deltaY, deltaZ;
			for (int x = 0; x < 3; x++)	{
				for (int y = 0; y < 3; y++)	{
					for (int z = 0; z < 3; z++)	{
						if (x*y == 1 || y*z == 1 || z*x == 1)	continue;
						correctPos = Heuristics.getCorrectPos(cube.cubelet[x][y][z], x, y, z);
						deltaX = Math.abs(correctPos.x -x);
						deltaY = Math.abs(correctPos.y - y);
						deltaZ = Math.abs(correctPos.z -z);
						if (x != 1 && y != 1 && z != 1)	{	// corner cubie
							if (deltaX == 0 && deltaY == 0 && deltaZ == 0)	{
								if (Heuristics.face[x][y][z].x == cube.cubelet[x][y][z].getColor(Heuristics.face[x][y][z].x) && Heuristics.face[x][y][z].y == cube.cubelet[x][y][z].getColor(Heuristics.face[x][y][z].y));
								else cornerStrength += 2;
							}
							else
								cornerStrength += (deltaX + deltaY + deltaZ)/2.0+2;
						}
						else{	// edge cubie
							if (deltaX == 0 && deltaY == 0 && deltaZ == 0)	{
								if (Heuristics.face[x][y][z].x != -1)	{
									if (Heuristics.face[x][y][z].x == cube.cubelet[x][y][z].getColor(Heuristics.face[x][y][z].x));
									else edgeStrength += 3;
								}
								else{
									if (Heuristics.face[x][y][z].y == cube.cubelet[x][y][z].getColor(Heuristics.face[x][y][z].y));
									else edgeStrength += 3;
								}
							}
							else if (deltaX != 0 && deltaY != 0 && deltaZ != 0)	{
								edgeStrength += (2+3);
							}
							else{
								if ((deltaX == 0 && x == 1) || (deltaY == 0 && y == 1) && (deltaZ == 0 && z == 1))	{
									edgeStrength += deltaY + deltaZ+3;
								}
								else edgeStrength += 1;
							}
						}
					}
				}
			}
			return (cornerStrength >= edgeStrength) ? cornerStrength/(float)4: edgeStrength/(float)4;
		}
	}


	public static int whichIsZero(int a, int b, int c)	{
		if (a == 0)	return 1;
		if (b == 0)	return 2;
		if (c == 0)	return 3;
		return -1;
	}

}


class Triplet {
	int x,y,z;
	Triplet() {
		this.x = 0;
		this.y = 0;
		this.z = 0;
	}

	
	Triplet(int x, int y, int z)
	{
		this.x = x;
		this.y = y;
		this.z = z; 	
	}
}


class Duplet {
	byte x,y;
	Duplet()	{
		this.x = 0;
		this.y = 0;
        }
        Duplet(byte x,byte y)
        {
		this.x = x;
		this.y = y;
	}
	
}