Manual pruning table loader for Herbert Kociemba's "Twophase Algorithm" (http://kociemba.org/cube.htm)

CoordCube.java

package org.kociemba.twophase;

import org.kociemba.twophase.CubieCube;

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Representation of the cube on the coordinate level
public 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;
	
	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// 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 = twistMove[twist][m];
		flip = flipMove[flip][m];
		parity = parityMove[parity][m];
		FRtoBR = FRtoBR_Move[FRtoBR][m];
		URFtoDLF = URFtoDLF_Move[URFtoDLF][m];
		URtoUL = URtoUL_Move[URtoUL][m];
		UBtoDF = UBtoDF_Move[UBtoDF][m];
		if (URtoUL < 336 && UBtoDF < 336)// updated only if UR,UF,UL,UB,DR,DF
			// are not in UD-slice
			URtoDF = MergeURtoULandUBtoDF[URtoUL][UBtoDF];
	}
	
	/* all empty pruning tables; must be loaded with {@link PruneTableLoader} first before using the solver */
	static short[][] twistMove;
	static short[][] flipMove;
	static short[][] FRtoBR_Move;
	static short[][] URFtoDLF_Move;
	static short[][] URtoDF_Move;
	static short[][] URtoUL_Move;
	static short[][] UBtoDF_Move;
	static short[][] MergeURtoULandUBtoDF;
	static byte[] Slice_URFtoDLF_Parity_Prun;
	static byte[] Slice_URtoDF_Parity_Prun;
	static byte[] Slice_Twist_Prun;
	static byte[] Slice_Flip_Prun;
	
	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// 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 } };

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// 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);
	}
}

PruneTableLoader.java

package org.kociemba.twophase;

import static org.kociemba.twophase.CoordCube.*;

import org.kociemba.twophase.CubieCube;

/**
 * <p>This class provides (very basic) control over the loading of the pruning tables in {@link CoordCube} for Herbert Kociemba's 
 * <i>Twophase Solver</i>.
 * 
 * <p>This class will mostly be used like this:
 * <pre><code>
 * PruneTableLoader tableLoader = new PruneTableLoader();
 * while (!tableLoader.loadingFinished())
 *       loadNext();
 * </pre></code>
 * 
 * <p><i>Note</i>: For this class to have any effect, you must have replaced {@link CoordCube} with the custom 
 * implementation beforehand.
 * 
 * @author Herbert Kociemba <i>(generation of the pruning tables)</i>
 * @author Elias Frantar <i>(implementation of this class)</i>
 * @version 2014-8-16
 */
public class PruneTableLoader {
	private static final int TABLES = 12; // there are 12 different pruning tables to load
	
	private int tablesLoaded; // the number of already loaded tables
	
	/**
	 * Constructor<br>
	 * Number of tables loaded is set to 0.
	 */
	public PruneTableLoader() {
		tablesLoaded = 0;
	}
	
	/**
	 * Loads the next pruning table if and only if it is <i>null</i>.<br>
	 * Equivalent to <code>loadNext(false);</code>
	 */
	public void loadNext() { loadNext(false); }
	
	/**
	 * Loads the next pruning table.
	 * @param force if true override it even if it already exists; if false only load when it is <i>null</i>
	 */
	public void loadNext(boolean force) {
		switch(tablesLoaded++) {
			case 0:  loadTwistMoves(force);		 		 break;
			case 1:  loadFlipMoves(force);  		 	 break;
			case 2:  loadFRtoBRMoves(force);		 	 break;
			case 3:  loadURFtoDLFMoves(force);	 		 break;
			case 4:  loadURtoDFMoves(force);		 	 break;
			case 5:  loadURtoULMoves(force);		 	 break;
			case 6:  loadUBtoDFMoves(force);		 	 break;
			case 7:  mergeURtoULandUBtoDF(force); 		 break;
			case 8:  loadSliceURFtoDLFParityPrun(force); break;
			case 9:  loadSliceURtoDFParityPrun(force);	 break;
			case 10: loadSliceTwistPrune(force);		 break;
			case 11: loadSliceFlipPrune(force);			 break;
			default: break;
		}
	}
	
	/**
	 * Determines if all pruning tables have already been loaded by using this class.
	 * @return true if all tables have already been loaded; false otherwise
	 */
	public boolean loadingFinished() {
		return tablesLoaded >= TABLES;
	}
	
	/*
	 * Methods for loading each individual pruning table.
	 * @param force if true override the table even it already exists; if false only load it when it is <i>null</i>
	 * 
	 * Code and commments have been directly copied from {@author Herbert Kociemba}'s original CoordCube-class.
	 */
	
	// ******************************************Phase 1 move tables*****************************************************

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// Move table for the twists of the corners
	// twist < 2187 in phase 2.
	// twist = 0 in phase 2.
	private void loadTwistMoves(boolean force) {
		/* only load if not already loaded */
		if (!force && twistMove != null)
			return;
		twistMove = new short[N_TWIST][N_MOVE];
		
		CubieCube a = new CubieCube();
		for (short i = 0; i < N_TWIST; i++) {
			a.setTwist(i);
			for (int j = 0; j < 6; j++) {
				for (int k = 0; k < 3; k++) {
					a.cornerMultiply(CubieCube.moveCube[j]);
					twistMove[i][3 * j + k] = a.getTwist();
				}
				a.cornerMultiply(CubieCube.moveCube[j]); // 4. faceturn restores a
			}
		}
	}
	
	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// Move table for the flips of the edges
	// flip < 2048 in phase 1
	// flip = 0 in phase 2.
	private void loadFlipMoves(boolean force) {
		if (!force && flipMove != null)
			return;
		flipMove = new short[N_FLIP][N_MOVE];
		
		CubieCube a = new CubieCube();
		for (short i = 0; i < N_FLIP; i++) {
			a.setFlip(i);
			for (int j = 0; j < 6; j++) {
				for (int k = 0; k < 3; k++) {
					a.edgeMultiply(CubieCube.moveCube[j]);
					flipMove[i][3 * j + k] = a.getFlip();
				}
				a.edgeMultiply(CubieCube.moveCube[j]); // a
			}
		}
	}
	
	// ***********************************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 void loadFRtoBRMoves(boolean force) {
		if (!force && FRtoBR_Move != null)
			return;
		FRtoBR_Move = new short[N_FRtoBR][N_MOVE];
		
		CubieCube a = new CubieCube();
		for (short i = 0; i < N_FRtoBR; i++) {
			a.setFRtoBR(i);
			for (int j = 0; j < 6; j++) {
				for (int k = 0; k < 3; k++) {
					a.edgeMultiply(CubieCube.moveCube[j]);
					FRtoBR_Move[i][3 * j + k] = a.getFRtoBR();
				}
				a.edgeMultiply(CubieCube.moveCube[j]);
			}
		}
	}
	
	// *******************************************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 void loadURFtoDLFMoves(boolean force) {
		if (!force && URFtoDLF_Move != null)
			return;
		URFtoDLF_Move = new short[N_URFtoDLF][N_MOVE];
		
		CubieCube a = new CubieCube();
		for (short i = 0; i < N_URFtoDLF; i++) {
			a.setURFtoDLF(i);
			for (int j = 0; j < 6; j++) {
				for (int k = 0; k < 3; k++) {
					a.cornerMultiply(CubieCube.moveCube[j]);
					URFtoDLF_Move[i][3 * j + k] = a.getURFtoDLF();
				}
				a.cornerMultiply(CubieCube.moveCube[j]);
			}
		}
	}
	
	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// 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 void loadURtoDFMoves(boolean force) {
		if (!force && URtoDF_Move != null)
			return;
		URtoDF_Move = new short[N_URtoDF][N_MOVE];
		
		CubieCube a = new CubieCube();
		for (short i = 0; i < N_URtoDF; i++) {
			a.setURtoDF(i);
			for (int j = 0; j < 6; j++) {
				for (int k = 0; k < 3; k++) {
					a.edgeMultiply(CubieCube.moveCube[j]);
					URtoDF_Move[i][3 * j + k] = (short) a.getURtoDF(); // Table values are only valid for phase 2 moves! For phase 1 moves, casting to short is not possible.
				}
				a.edgeMultiply(CubieCube.moveCube[j]);
			}
		}
	}
	
	// **************************helper move tables to compute URtoDF for the beginning of phase2************************

	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// Move table for the three edges UR,UF and UL in phase1.	
	private void loadURtoULMoves(boolean force) {
		if (!force && URtoUL_Move != null)
			return;
		URtoUL_Move = new short[N_URtoUL][N_MOVE];
		
		CubieCube a = new CubieCube();
		for (short i = 0; i < N_URtoUL; i++) {
			a.setURtoUL(i);
			for (int j = 0; j < 6; j++) {
				for (int k = 0; k < 3; k++) {
					a.edgeMultiply(CubieCube.moveCube[j]);
					URtoUL_Move[i][3 * j + k] = a.getURtoUL();
				}
				a.edgeMultiply(CubieCube.moveCube[j]);
			}
		}
	}
	
	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// Move table for the three edges UB,DR and DF in phase1.
	private void loadUBtoDFMoves(boolean force) {
		if (!force && UBtoDF_Move != null)
			return;
		UBtoDF_Move = new short[N_UBtoDF][N_MOVE];
	
		CubieCube a = new CubieCube();
		for (short i = 0; i < N_UBtoDF; i++) {
			a.setUBtoDF(i);
			for (int j = 0; j < 6; j++) {
				for (int k = 0; k < 3; k++) {
					a.edgeMultiply(CubieCube.moveCube[j]);
					UBtoDF_Move[i][3 * j + k] = a.getUBtoDF();
				}
				a.edgeMultiply(CubieCube.moveCube[j]);
			}
		}
	}
	
	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// Table to merge the coordinates of the UR,UF,UL and UB,DR,DF edges at the beginning of phase2
	private void mergeURtoULandUBtoDF(boolean force) {
		if (!force && MergeURtoULandUBtoDF != null)
			return;
		MergeURtoULandUBtoDF = new short[336][336];
		
		/* for i, j < 336 the six edges UR,UF,UL,UB,DR,DF are not in the UD-slice and the index is < 20160 */
		for (short uRtoUL = 0; uRtoUL < 336; uRtoUL++) {
			for (short uBtoDF = 0; uBtoDF < 336; uBtoDF++) {
				MergeURtoULandUBtoDF[uRtoUL][uBtoDF] = (short) CubieCube.getURtoDF(uRtoUL, uBtoDF);
			}
		}
	}
	
	// ****************************************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.
	private void loadSliceURFtoDLFParityPrun(boolean force) {
		if (!force && Slice_URFtoDLF_Parity_Prun != null)
			return;
		Slice_URFtoDLF_Parity_Prun = new byte[N_SLICE2 * N_URFtoDLF * N_PARITY / 2];

		for (int i = 0; i < N_SLICE2 * N_URFtoDLF * N_PARITY / 2; i++)
			Slice_URFtoDLF_Parity_Prun[i] = -1;
		
		int depth = 0;
		setPruning(Slice_URFtoDLF_Parity_Prun, 0, (byte) 0);
		int done = 1;
		while (done != N_SLICE2 * N_URFtoDLF * N_PARITY) {
			for (int i = 0; i < N_SLICE2 * N_URFtoDLF * N_PARITY; i++) {
				int parity = i % 2;
				int URFtoDLF = (i / 2) / N_SLICE2;
				int slice = (i / 2) % N_SLICE2;
				if (getPruning(Slice_URFtoDLF_Parity_Prun, i) == depth) {
					for (int j = 0; j < 18; j++) {
						switch (j) {
						case 3:
						case 5:
						case 6:
						case 8:
						case 12:
						case 14:
						case 15:
						case 17:
							continue;
						default:
							int newSlice = FRtoBR_Move[slice][j];
							int newURFtoDLF = URFtoDLF_Move[URFtoDLF][j];
							int newParity = parityMove[parity][j];
							if (getPruning(Slice_URFtoDLF_Parity_Prun, (N_SLICE2 * newURFtoDLF + newSlice) * 2 + newParity) == 0x0f) {
								setPruning(Slice_URFtoDLF_Parity_Prun, (N_SLICE2 * newURFtoDLF + newSlice) * 2 + newParity,
										(byte) (depth + 1));
								done++;
							}
						}
					}
				}
			}
			depth++;
		}
	}
	
	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// 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.
	private void loadSliceURtoDFParityPrun(boolean force) {
		if (!force && Slice_URtoDF_Parity_Prun != null)
			return;
		Slice_URtoDF_Parity_Prun = new byte[N_SLICE2 * N_URtoDF * N_PARITY / 2];
		
		for (int i = 0; i < N_SLICE2 * N_URtoDF * N_PARITY / 2; i++)
			Slice_URtoDF_Parity_Prun[i] = -1;
		
		int depth = 0;
		setPruning(Slice_URtoDF_Parity_Prun, 0, (byte) 0);
		int done = 1;
		while (done != N_SLICE2 * N_URtoDF * N_PARITY) {
			for (int i = 0; i < N_SLICE2 * N_URtoDF * N_PARITY; i++) {
				int parity = i % 2;
				int URtoDF = (i / 2) / N_SLICE2;
				int slice = (i / 2) % N_SLICE2;
				if (getPruning(Slice_URtoDF_Parity_Prun, i) == depth) {
					for (int j = 0; j < 18; j++) {
						switch (j) {
						case 3:
						case 5:
						case 6:
						case 8:
						case 12:
						case 14:
						case 15:
						case 17:
							continue;
						default:
							int newSlice = FRtoBR_Move[slice][j];
							int newURtoDF = URtoDF_Move[URtoDF][j];
							int newParity = parityMove[parity][j];
							if (getPruning(Slice_URtoDF_Parity_Prun, (N_SLICE2 * newURtoDF + newSlice) * 2 + newParity) == 0x0f) {
								setPruning(Slice_URtoDF_Parity_Prun, (N_SLICE2 * newURtoDF + newSlice) * 2 + newParity,
										(byte) (depth + 1));
								done++;
							}
						}
					}
				}
			}
			depth++;
		}
	}
	
	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// 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.
	private void loadSliceTwistPrune(boolean force) {
		if (!force && Slice_Twist_Prun != null)
			return;
		Slice_Twist_Prun = new byte[N_SLICE1 * N_TWIST / 2 + 1];
		
		for (int i = 0; i < N_SLICE1 * N_TWIST / 2 + 1; i++)
			Slice_Twist_Prun[i] = -1;
		
		int depth = 0;
		setPruning(Slice_Twist_Prun, 0, (byte) 0);
		int done = 1;
		while (done != N_SLICE1 * N_TWIST) {
			for (int i = 0; i < N_SLICE1 * N_TWIST; i++) {
				int twist = i / N_SLICE1, slice = i % N_SLICE1;
				if (getPruning(Slice_Twist_Prun, i) == depth) {
					for (int j = 0; j < 18; j++) {
						int newSlice = FRtoBR_Move[slice * 24][j] / 24;
						int newTwist = twistMove[twist][j];
						if (getPruning(Slice_Twist_Prun, N_SLICE1 * newTwist + newSlice) == 0x0f) {
							setPruning(Slice_Twist_Prun, N_SLICE1 * newTwist + newSlice, (byte) (depth + 1));
							done++;
						}
					}
				}
			}
			depth++;
		}
	}
	
	// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// 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.
	private void loadSliceFlipPrune(boolean force) {
		if (!force && Slice_Flip_Prun != null)
			return;
		Slice_Flip_Prun = new byte[N_SLICE1 * N_FLIP / 2];
		
		for (int i = 0; i < N_SLICE1 * N_FLIP / 2; i++)
			Slice_Flip_Prun[i] = -1;
		
		int depth = 0;
		setPruning(Slice_Flip_Prun, 0, (byte) 0);
		int done = 1;
		while (done != N_SLICE1 * N_FLIP) {
			for (int i = 0; i < N_SLICE1 * N_FLIP; i++) {
				int flip = i / N_SLICE1, slice = i % N_SLICE1;
				if (getPruning(Slice_Flip_Prun, i) == depth) {
					for (int j = 0; j < 18; j++) {
						int newSlice = FRtoBR_Move[slice * 24][j] / 24;
						int newFlip = flipMove[flip][j];
						if (getPruning(Slice_Flip_Prun, N_SLICE1 * newFlip + newSlice) == 0x0f) {
							setPruning(Slice_Flip_Prun, N_SLICE1 * newFlip + newSlice, (byte) (depth + 1));
							done++;
						}
					}
				}
			}
			depth++;
		}
	}
}

This is a very simple implementation of a manual loader for the pruning tables of Herbert Kociemba's Twophase Algorithm.
This is required when using this algorithm on, for example Android because auto-loading the tables is for some reason far too slow there ...

---

How to use this:

1. Replace the original CoordCube.java with this CoordCube.java.
2. Copy PruneTableLoader.java into the package org.kociemba.twophase
3. Done. Use PruneTableLoader for example like this:

PruneTableLoader tableLoader = new PruneTableLoader();
while (!tableLoader.loadingFinished())
    tableLoader.loadNext();

(You will probably want to run this in an AsyncTask in a loading-Activity with a ProgressBar.)

---

On my Samsung Galaxy S3 with 250 MB RAM remaining, loading all tables with this utility needs about 40s.
When letting them load automatically, it needs well over 2min and often results in a crash ...

---

All credit for the implementation of the pruning table generation goes to Herbert Kociemba.

If anyone is still interested. I was facing a similar problem with automatically loading the prune tables taking about 10 minutes on my device. With this program, I was able to bring the loading time down to 1 minute. However, it was still not sufficient for my purposes. I then pre-generated the tables on my computer and provided them as res/raw files in my code. Then, on each startup of the app, the reading of the tables into their respective variables only took about 4 seconds.

This program still takes 10 mins to load 12 pruning tables on Samsung Galaxy J3 with >680 mb ram available. Will mounting an additional SD card speed things up??