Magic Cube

package org.distorted.solvers.cube3;

import android.content.res.Resources;

import java.io.InputStream;

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

// Representation of the cube on the coordinate level

class CoordCube {

	static final short N_TWIST = 2187;// 3^7 possible corner orientations

	static final short N_FLIP = 2048;// 2^11 possible edge flips

	static final short N_SLICE1 = 495;// 12 choose 4 possible positions of FR,FL,BL,BR edges

	static final short N_SLICE2 = 24;// 4! permutations of FR,FL,BL,BR edges in phase2

	static final short N_PARITY = 2; // 2 possible corner parities

	static final short N_URFtoDLF = 20160;// 8!/(8-6)! permutation of URF,UFL,ULB,UBR,DFR,DLF corners

	static final short N_FRtoBR = 11880; // 12!/(12-4)! permutation of FR,FL,BL,BR edges

	static final short N_URtoUL = 1320; // 12!/(12-3)! permutation of UR,UF,UL edges

	static final short N_UBtoDF = 1320; // 12!/(12-3)! permutation of UB,DR,DF edges

	static final short N_URtoDF = 20160; // 8!/(8-6)! permutation of UR,UF,UL,UB,DR,DF edges in phase2

	static final int N_URFtoDLB = 40320;// 8! permutations of the corners

	static final int N_URtoBR = 479001600;// 8! permutations of the corners

	static final short N_MOVE = 18;

	// All coordinates are 0 for a solved cube except for UBtoDF, which is 114

	short twist;

	short flip;

	short parity;

	short FRtoBR;

	short URFtoDLF;

	short URtoUL;

	short UBtoDF;

	int URtoDF;

	private static boolean[] init = new boolean[12];

	static 

	  {

	  for(int i=0; i<12; i++ ) init[i] = false;	

	  }

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Generate a CoordCube from a CubieCube

	CoordCube(CubieCube c) {

		twist = c.getTwist();

		flip = c.getFlip();

		parity = c.cornerParity();

		FRtoBR = c.getFRtoBR();

		URFtoDLF = c.getURFtoDLF();

		URtoUL = c.getURtoUL();

		UBtoDF = c.getUBtoDF();

		URtoDF = c.getURtoDF();// only needed in phase2

	}

	// A move on the coordinate level

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	void move(int m) {

		twist = getTwistMove(twist,m);

		flip = getFlipMove(flip,m);

		parity = parityMove[parity][m];

		FRtoBR = getFRtoBR_Move(FRtoBR,m);

		URFtoDLF = getURFtoDLF_Move(URFtoDLF,m);

		URtoUL = getURtoUL_Move(URtoUL,m);

		UBtoDF = getUBtoDF_Move(UBtoDF,m);

		if (URtoUL < 336 && UBtoDF < 336)// updated only if UR,UF,UL,UB,DR,DF

			// are not in UD-slice

			URtoDF = getMergeURtoULandUBtoDF(URtoUL,UBtoDF);

	}

	// ******************************************Phase 1 move tables*****************************************************

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Move table for the twists of the corners

	// twist < 2187 in phase 2.

	// twist = 0 in phase 2.

	private static byte[] twistMove = new byte[2*N_TWIST*N_MOVE];

	public static boolean initialize1(Resources res)

	{

		if( !init[0] )

		  {

          try

		    {

        	InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table1);

		    is.read( twistMove, 0, 2*N_TWIST*N_MOVE);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table1");

                    return false;

		    }

		  init[0]=true;

		  }

                return true;

	}

	public static short getTwistMove(int a,int b)

	{

		short upperS = twistMove[2*(a*N_MOVE+b)];

		short lowerS = twistMove[2*(a*N_MOVE+b)+1];

		if( upperS<0 ) upperS+=256;

		if( lowerS<0 ) lowerS+=256;

		return  (short)( (upperS<<8) + lowerS );

	}

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Move table for the flips of the edges

	// flip < 2048 in phase 1

	// flip = 0 in phase 2.

	private static byte[] flipMove = new byte[2*N_FLIP*N_MOVE];

	public static boolean initialize2(Resources res)

	{

		if( !init[1] )

		  {

		  try

		    {

			InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table2);

		    is.read( flipMove, 0, 2*N_FLIP*N_MOVE);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table2");

                    return false;

		    }

		  init[1]=true;

		  }

                return true;

	}

	public static short getFlipMove(int a,int b)

	{

		short upperS = flipMove[2*(a*N_MOVE+b)];

		short lowerS = flipMove[2*(a*N_MOVE+b)+1];

		if( upperS<0 ) upperS+=256;

		if( lowerS<0 ) lowerS+=256;

		return  (short)( (upperS<<8) + lowerS );

	}

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Parity of the corner permutation. This is the same as the parity for the edge permutation of a valid cube.

	// parity has values 0 and 1

	static short[][] parityMove = { { 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },

			{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0 } };

	// ***********************************Phase 1 and 2 movetable********************************************************

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Move table for the four UD-slice edges FR, FL, Bl and BR

	// FRtoBRMove < 11880 in phase 1

	// FRtoBRMove < 24 in phase 2

	// FRtoBRMove = 0 for solved cube

	private static byte[] FRtoBR_Move = new byte[2*N_FRtoBR*N_MOVE];

	public static boolean initialize3(Resources res)

	{

		if( !init[2] )

		  {

		  try

		    {

			InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table3);

		    is.read( FRtoBR_Move, 0, 2*N_FRtoBR*N_MOVE);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table3");

                    return true;

		    }

		  init[2]=true;

		  }

                return false;

	}

	public static short getFRtoBR_Move(int a,int b)

	{

		short upperS = FRtoBR_Move[2*(a*N_MOVE+b)];

		short lowerS = FRtoBR_Move[2*(a*N_MOVE+b)+1];

		if( upperS<0 ) upperS+=256;

		if( lowerS<0 ) lowerS+=256;

		return  (short)( (upperS<<8) + lowerS );

	}

	// *******************************************Phase 1 and 2 movetable************************************************

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Move table for permutation of six corners. The positions of the DBL and DRB corners are determined by the parity.

	// URFtoDLF < 20160 in phase 1

	// URFtoDLF < 20160 in phase 2

	// URFtoDLF = 0 for solved cube.

	private static byte[] URFtoDLF_Move = new byte[2*N_URFtoDLF*N_MOVE];

	public static boolean initialize4(Resources res)

	{

		if( !init[3] )

		  {

		  try

		    {

			InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table4);

		    is.read( URFtoDLF_Move, 0, 2*N_URFtoDLF*N_MOVE);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table4");

                    return false;

		    }

		  init[3]=true;

		  }

                return true;

	}

	public static short getURFtoDLF_Move(int a,int b)

	{

		short upperS = URFtoDLF_Move[2*(a*N_MOVE+b)];

		short lowerS = URFtoDLF_Move[2*(a*N_MOVE+b)+1];

		if( upperS<0 ) upperS+=256;

		if( lowerS<0 ) lowerS+=256;

		return  (short)( (upperS<<8) + lowerS );

	}

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Move table for the permutation of six U-face and D-face edges in phase2. The positions of the DL and DB edges are

	// determined by the parity.

	// URtoDF < 665280 in phase 1

	// URtoDF < 20160 in phase 2

	// URtoDF = 0 for solved cube.

	private static byte[] URtoDF_Move = new byte[2*N_URtoDF*N_MOVE];

	public static boolean initialize5(Resources res)

	{

		if( !init[4] )

		  {

		  try

		    {

			InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table5);

		    is.read( URtoDF_Move, 0, 2*N_URtoDF*N_MOVE);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table5");

                    return false;

		    }

		  init[4]=true;

		  }

                return true;

	}

	public static short getURtoDF_Move(int a,int b)

	{

		short upperS = URtoDF_Move[2*(a*N_MOVE+b)];

		short lowerS = URtoDF_Move[2*(a*N_MOVE+b)+1];

		if( upperS<0 ) upperS+=256;

		if( lowerS<0 ) lowerS+=256;

		return  (short)( (upperS<<8) + lowerS );

	}

	// **************************helper move tables to compute URtoDF for the beginning of phase2************************

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Move table for the three edges UR,UF and UL in phase1.

	private static byte[] URtoUL_Move = new byte[2*N_URtoUL*N_MOVE];

	public static boolean initialize6(Resources res)

	{

		if( !init[5] )

		  {

		  try

		    {

			InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table6);

		    is.read( URtoUL_Move, 0, 2*N_URtoUL*N_MOVE);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table6");

                    return false;

		    }

		  init[5]=true;

		  }

                return true;

	}

	public static short getURtoUL_Move(int a,int b)

	{

		short upperS = URtoUL_Move[2*(a*N_MOVE+b)];

		short lowerS = URtoUL_Move[2*(a*N_MOVE+b)+1];

		if( upperS<0 ) upperS+=256;

		if( lowerS<0 ) lowerS+=256;

		return  (short)( (upperS<<8) + lowerS );

	}

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Move table for the three edges UB,DR and DF in phase1.

	private static byte[] UBtoDF_Move = new byte[2*N_UBtoDF*N_MOVE];

	public static boolean initialize7(Resources res)

	{

		if( !init[6] )

		  {

		  try

		    {

			InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table7);

		    is.read( UBtoDF_Move, 0, 2*N_UBtoDF*N_MOVE);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table7");

                    return false;

		    }

		  init[6]=true;

		  }

                return true;

	}

	public static short getUBtoDF_Move(int a,int b)

	{

		short upperS = UBtoDF_Move[2*(a*N_MOVE+b)];

		short lowerS = UBtoDF_Move[2*(a*N_MOVE+b)+1];

		if( upperS<0 ) upperS+=256;

		if( lowerS<0 ) lowerS+=256;

		return  (short)( (upperS<<8) + lowerS );

	}

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Table to merge the coordinates of the UR,UF,UL and UB,DR,DF edges at the beginning of phase2

	private static byte[] MergeURtoULandUBtoDF = new byte[2*336*336];

	public static boolean initialize8(Resources res)

	{

		if( !init[7] )

		  {

		  try

		    {

			InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table8);

		    is.read( MergeURtoULandUBtoDF, 0, 2*336*336);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table8");

                    return false;

		    }

		  init[7]=true;

		  }

                return true;

	}

	public static short getMergeURtoULandUBtoDF(int a,int b)

	{

		short upperS = MergeURtoULandUBtoDF[2*(a*336+b)];

		short lowerS = MergeURtoULandUBtoDF[2*(a*336+b)+1];

		if( upperS<0 ) upperS+=256;

		if( lowerS<0 ) lowerS+=256;

		return  (short)( (upperS<<8) + lowerS );

	}

	// ****************************************Pruning tables for the search*********************************************

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Pruning table for the permutation of the corners and the UD-slice edges in phase2.

	// The pruning table entries give a lower estimation for the number of moves to reach the solved cube.

	public static byte[] Slice_URFtoDLF_Parity_Prun = new byte[N_SLICE2 * N_URFtoDLF * N_PARITY / 2];

	public static boolean initialize9(Resources res)

	{

		if( !init[8] )

		  {

		  try

		    {

			  InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table9);

		    is.read( Slice_URFtoDLF_Parity_Prun, 0, N_SLICE2 * N_URFtoDLF * N_PARITY / 2);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table9");

                    return false;

		    }

		  init[8]=true;

		  }

    return true;

	}

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Pruning table for the permutation of the edges in phase2.

	// The pruning table entries give a lower estimation for the number of moves to reach the solved cube.

	public static byte[] Slice_URtoDF_Parity_Prun = new byte[N_SLICE2 * N_URtoDF * N_PARITY / 2];

	public static boolean initialize10(Resources res)

	{

		if( !init[9] )

		  {

		  try

		    {

			InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table10);

		    is.read( Slice_URtoDF_Parity_Prun, 0, N_SLICE2 * N_URtoDF * N_PARITY / 2);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table10");

                    return false;

		    }

		  init[9]=true;

		  }

                return true;

	}

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Pruning table for the twist of the corners and the position (not permutation) of the UD-slice edges in phase1

	// The pruning table entries give a lower estimation for the number of moves to reach the H-subgroup.

	public static byte[] Slice_Twist_Prun = new byte[N_SLICE1 * N_TWIST / 2 + 1];

	public static boolean initialize11(Resources res)

	{

		if( !init[10] )

		  {

		  try

		    {

			InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table11);

		    is.read( Slice_Twist_Prun, 0, N_SLICE1 * N_TWIST / 2 + 1);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table11");

                    return false;

		    }

		  init[10]=true;

		  }

                return true;

	}

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Pruning table for the flip of the edges and the position (not permutation) of the UD-slice edges in phase1

	// The pruning table entries give a lower estimation for the number of moves to reach the H-subgroup.

	public static byte[] Slice_Flip_Prun = new byte[N_SLICE1 * N_FLIP / 2];

	public static boolean initialize12(Resources res)

	{

		if( !init[11] )

		  {

		  try

		    {

			InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table12);

		    is.read( Slice_Flip_Prun, 0, N_SLICE1 * N_FLIP / 2);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table12");

                    return false;

		    }

		  init[11]=true;

		  }

                return true;

	}

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Set pruning value in table. Two values are stored in one byte.

	static void setPruning(byte[] table, int index, byte value) {

		if ((index & 1) == 0)

			table[index / 2] &= 0xf0 | value;

		else

			table[index / 2] &= 0x0f | (value << 4);

	}

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	// Extract pruning value

	static byte getPruning(byte[] table, int index) {

		if ((index & 1) == 0)

			return (byte) (table[index / 2] & 0x0f);

		else

			return (byte) ((table[index / 2] & 0xf0) >>> 4);

	}

}