Magic Cube

///////////////////////////////////////////////////////////////////////////////////////////////////

// Copyright 2008 Leszek Koltunski                                                               //

//                                                                                               //

// This file is part of Magic Cube.                                                              //

//                                                                                               //

// Magic Cube is free software: you can redistribute it and/or modify                            //

// it under the terms of the GNU General Public License as published by                          //

// the Free Software Foundation, either version 2 of the License, or                             //

// (at your option) any later version.                                                           //

//                                                                                               //

// Magic Cube is distributed in the hope that it will be useful,                                 //

// but WITHOUT ANY WARRANTY; without even the implied warranty of                                //

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the                                 //

// GNU General Public License for more details.                                                  //

//                                                                                               //

// You should have received a copy of the GNU General Public License                             //

// along with Magic Cube.  If not, see <http://www.gnu.org/licenses/>.                           //

///////////////////////////////////////////////////////////////////////////////////////////////////

package org.distorted.solvers.cube3;

import java.io.InputStream;

import android.content.res.Resources;

///////////////////////////////////////////////////////////////////////////////////////////////////

class SolverCoordCube

{

	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 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 final boolean[] init = new boolean[12];

	static 

	  {

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

	  }

  // Phase 1 move tables

  // Move table for the twists of the corners. twist < 2187 in phase 2; twist = 0 in phase 2.

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

	// Move table for the flips of the edges. flip < 2048 in phase 1; flip = 0 in phase 2.

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

  // 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 final byte[] FRtoBR_Move = new byte[2*N_FRtoBR*N_MOVE];

	// 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 final byte[] URFtoDLF_Move = new byte[2*N_URFtoDLF*N_MOVE];

	// 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 final byte[] URtoDF_Move = new byte[2*N_URtoDF*N_MOVE];

	// 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 final byte[] URtoUL_Move = new byte[2*N_URtoUL*N_MOVE];

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

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

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

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

	// 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];

	// 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];

	// 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];

	// 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];

  private static final int[] resourceTable = new int[]

			{

			org.distorted.main.R.raw.cube3solver_table1,

			org.distorted.main.R.raw.cube3solver_table2,

			org.distorted.main.R.raw.cube3solver_table3,

			org.distorted.main.R.raw.cube3solver_table4,

			org.distorted.main.R.raw.cube3solver_table5,

			org.distorted.main.R.raw.cube3solver_table6,

			org.distorted.main.R.raw.cube3solver_table7,

			org.distorted.main.R.raw.cube3solver_table8,

			org.distorted.main.R.raw.cube3solver_table9,

			org.distorted.main.R.raw.cube3solver_table10,

			org.distorted.main.R.raw.cube3solver_table11,

			org.distorted.main.R.raw.cube3solver_table12

			};

  private static final byte[][] tableOfTables = new byte[][]

			{

			twistMove,

			flipMove,

			FRtoBR_Move,

			URFtoDLF_Move,

			URtoDF_Move,

			URtoUL_Move,

			UBtoDF_Move,

			MergeURtoULandUBtoDF,

			Slice_URFtoDLF_Parity_Prun,

			Slice_URtoDF_Parity_Prun,

			Slice_Twist_Prun,

			Slice_Flip_Prun

			};

///////////////////////////////////////////////////////////////////////////////////////////////////

// Generate a CoordCube from a CubieCube

	SolverCoordCube(SolverCubieCube 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

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

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

	  {

	  byte ret = table[index/2];

	  return (byte) ( ((index&1)==0) ? (ret&0x0f) : ((ret&0xf0)>>>4) );

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

	public static short getTwistMove(int a,int b)

	  {

	  return getTable(a,b,twistMove,N_MOVE);

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

	public static short getFlipMove(int a,int b)

	  {

	  return getTable(a,b,flipMove,N_MOVE);

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

	public static short getFRtoBR_Move(int a,int b)

	  {

	  return getTable(a,b,FRtoBR_Move,N_MOVE);

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

	public static short getURFtoDLF_Move(int a,int b)

	  {

	  return getTable(a,b,URFtoDLF_Move,N_MOVE);

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

	public static short getURtoDF_Move(int a,int b)

	  {

	  return getTable(a,b,URtoDF_Move,N_MOVE);

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

	public static short getURtoUL_Move(int a,int b)

	  {

	  return getTable(a,b,URtoUL_Move,N_MOVE);

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

	public static short getUBtoDF_Move(int a,int b)

	  {

	  return getTable(a,b,UBtoDF_Move,N_MOVE);

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

	public static short getMergeURtoULandUBtoDF(int a,int b)

	  {

	  return getTable(a,b,MergeURtoULandUBtoDF,336);

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

	private static short getTable(int a,int b, byte[] table, int size)

	  {

		short upperS = table[2*(a*size+b)];

		short lowerS = table[2*(a*size+b)+1];

		if( upperS<0 ) upperS+=256;

		if( lowerS<0 ) lowerS+=256;

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

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

	public static void initialize(Resources res, int index)

		{

		if( !init[index] )

		  {

		  try

		    {

		    byte[] table = tableOfTables[index];

			  InputStream is = res.openRawResource(resourceTable[index]);

		    is.read( table, 0, table.length);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table"+index);

		    }

		  init[index]=true;

		  }

		}

}