* String solution = MagicCubeNdSolve.solve(
* " AAa AAa AAa "
* + " bBB c C c C c C Bbb "
* + " BBB C c C c C c bbb "
* + " bBB C c C c C c Bbb "
* + " Aaa Aaa Aaa "
* );
* System.out.println("Solution = \""+solution+"\"");
* which prints this:
* * Solution = "aBC aBC ABC ABC cBA cBA ABC ABC cBA cBA aCB aCB"* In your string representation of the puzzle state, * you can represent the colors by any 2*d distinct non-space characters. * List the stickers in order by the current coordinates of their centers, * lexicographically. The format is totally free form; * you can add spaces and newlines wherever you feel like it (as above), * or omit them altogether: *
* "AAaAAaAAabBBcCcCcCBbbBBBCcCcCcbbbbBBCcCcCcBbbAaaAaaAaa"*
* Each move in the solution is a 90 degree twist of a face, * represented by a 3-letter sequence: *
* That's it! * *
* Here are all the public static functions: *
* String newPuzzle(int n, int d) * boolean isSane(String puzzleString) * boolean isSolvable(String puzzleString) * - equivalent to isSolvable(puzzleString, ~0, ~0, null 0) * boolean isSolved(String puzzleString) * String solve(String puzzleString) * - equivalent to solve(puzzleString, ~0, ~0, null, 0) * String solve(String puzzleString, * int whichToPosition, * int whichToOrient, * java.io.PrintWriter progressWriter, * int debugLevel) * String apply(String moves, String puzzleString) * String scramble(String puzzleString, * int minScrambleChen, * int maxScrambleChen, * java.util.Random generator) * int n(String puzzleString) * int d(String puzzleString) * void main(String args[]) - full featured test/demo program * void simple_main(String args[]) - simple test/demo program * void trivial_main(String args[]) - trivial test/demo program * * For descriptions of these functions, use javadoc * (run "javadoc MagicCubeNdSolve.java", which will create a bunch of html * files in the current directory, including index.html) * or see the descriptions above each function * (search for the string PUBLIC in the source file). ** * *
* AAA AAA AAA * BBB C c C c C c bbb * BBB C c C c C c bbb * BBB C c C c C c bbb * aaa aaa aaa ** and after the single twist "ACB" * (i.e. twist face A 90 degrees from axis C to axis B): *
* AAA AAA AAA * CCC b B b B b B ccc * BBB C c C c C c bbb * BBB C c C c C c bbb * aaa aaa aaa ** Note that the twist ACB can also be expressed as ABc or Acb or AbC. *
* Here's a pristine 34 puzzle: *
* AAA AAA AAA * AAA AAA AAA * AAA AAA AAA * * BBB BBB BBB * CCC D d D d D d ccc * CCC D d D d D d ccc * CCC D d D d D d ccc * bbb bbb bbb * * BBB BBB BBB * CCC D d D d D d ccc * CCC D d D d D d ccc * CCC D d D d D d ccc * bbb bbb bbb * * BBB BBB BBB * CCC D d D d D d ccc * CCC D d D d D d ccc * CCC D d D d D d ccc * bbb bbb bbb * * aaa aaa aaa * aaa aaa aaa * aaa aaa aaa ** and a pristine 35 puzzle (make your window wide): *
* AAA AAA AAA AAA AAA AAA AAA AAA AAA * AAA AAA AAA AAA AAA AAA AAA AAA AAA * AAA AAA AAA AAA AAA AAA AAA AAA AAA * * BBB BBB BBB BBB BBB BBB BBB BBB BBB * CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc * CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc * CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc * bbb bbb bbb bbb bbb bbb bbb bbb bbb * BBB BBB BBB BBB BBB BBB BBB BBB BBB * CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc * CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc * CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc * bbb bbb bbb bbb bbb bbb bbb bbb bbb * BBB BBB BBB BBB BBB BBB BBB BBB BBB * CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc * CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc * CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc * bbb bbb bbb bbb bbb bbb bbb bbb bbb * * aaa aaa aaa aaa aaa aaa aaa aaa aaa * aaa aaa aaa aaa aaa aaa aaa aaa aaa * aaa aaa aaa aaa aaa aaa aaa aaa aaa * **/ // // ========================================================================== // // TODO: // - isSane needs a progressWriter for explanation, maybe // - see http://72.14.207.104/search?q=cache:S66YxvqauqYJ:rhea.redhat.com/doc/core-platform/5.0/engineering-standards/s1-exceptions.html+java+%22is+not+implemented%22+exception&hl=en&gl=us&ct=clnk&cd=7 // " It is a good practice to have one exception per package for signaling an application level error to the caller. These exceptions can be subclassed for use internally, but the methods that throw exceptions should declare that they throw this package level exception. However, if there is an exception as part of the standard Java API, such as IllegalArgumentException or IOException, it should be used." should I make one? Nah... // - use the standard IllegalArgumentException for illegal arguments to the public methods, I think. // - put in package donhatchsw? // ARGH, can't do this, since it will create // a package-level Arrays.class!!! // oh this SUCKS!!! need to rename Arrays to something else... // or, better, don't share it, make a little class // of whatever the Tester needs, probably not much // - allow comments in the files, using #? Maybe a regexp passed to the function? // - when printing timings of solve // align the timing printouts? maybe give most of the nMoves columns 4? // - allow comma-separated lists for positionMask and orientMask // - change all the INDICES functions to coords so I'm not converting back and forth so much // - expose only what's necessary // // - figure out nice way of printing with optimal whitespace like above // - make a solver object that can give partial results // and progress status messages; implement it as an iterator somehow? // - javadoc // -
variable names? nah, don't bother
// - attempt some sort of line editing in the command shell?
// - make a version of readPuzzle that knows n and d beforehand and therefore can't be fooled?
// Assert rather than assert-- these need to always be enabled;
// proper behavior in some cases depends on throwing an Error on assertion failure.
// If using the C preprocessor, uncomment the following for better messages,
// and you'll need to comment out the Assert methods in each class.
//#define Assert(expr) { if (!(expr)) throw new Error("Assertion failed at "+__FILE__+"("+__LINE__+"): " + #expr + ""); }
//#define assert ... dont use assert, use Assert! assert isn't compiled in by default ...
//#define PRINT(x) System.out.println(" " + #x + " = " + Arrays.toString(x))
public class MagicCubeNdSolve
{
// uncomment this if not using the C preprocessor...
static private void Assert(boolean condition) { if (!condition) throw new Error("Assertion failed"); }
private MagicCubeNdSolve() {} // non-instantiatable, only has static member functions
//=========================================================================
//
// Generic utility functions
// XXX should probably maybe be combined with
// XXX PuzzleManipulation since PuzzleManipulation is
// XXX a lame name, I don't know.
// XXX so far, if it has to do with slices masks,
// XXX it goes into PuzzleManipulation,
// XXX however I'm not sure if maybe the index-to-coords stuff should go there too?
//
private static class Utils
{
public static int clamp(int x, int a, int b)
{
return x <= a ? a :
x >= b ? b : x;
}
// assuming all entries of index are in the range 0..n-1,
// make a histogram.
public static int[] histogram(int n, int index[])
{
int hist[] = new int[n]; // all zero
for (int i = 0; i < index.length; ++i)
++hist[index[i]];
return hist;
}
// rounds down if the coords fall between cubies,
// e.g. to find the representative color for faces
// on even-length puzzles
public static int[] coordsToIndex(int n, int coords[])
{
int index[] = new int[coords.length];
for (int i = 0; i < coords.length; ++i)
index[i] = (coords[i]+n+1)/2;
return index;
}
public static int[] indexToCoords(int n, int index[])
{
int coords[] = new int[index.length];
for (int i = 0; i < index.length; ++i)
coords[i] = 2*index[i] - (n+1);
return coords;
}
public static Object coordssToIndexs(int n, Object coords)
{
if (coords.getClass() == int[].class)
return coordsToIndex(n, (int[])coords);
else
{
// XXX really should use reflection? not sure if it's required
Object[] coordss = (Object[])coords;
Object[] indexs = (Object[])java.lang.reflect.Array.newInstance(coordss.getClass().getComponentType(), coordss.length);
for (int i = 0; i < coordss.length; ++i)
indexs[i] = coordssToIndexs(n, coordss[i]); // recurse
return indexs;
}
}
public static Object indexsToCoordss(int n, Object index)
{
if (index.getClass() == int[].class)
return indexToCoords(n, (int[])index);
else
{
// XXX really should use reflection? not sure if it's required
Object[] indexs = (Object[])index;
Object[] coordss = (Object[])java.lang.reflect.Array.newInstance(indexs.getClass().getComponentType(), indexs.length);
for (int i = 0; i < indexs.length; ++i)
coordss[i] = indexsToCoordss(n, indexs[i]); // recurse
return coordss;
}
}
// A and B can be two sticker coords
// and/or cubie center coords.
public static boolean areOnSameCubie(int n, int A[], int B[])
{
for (int i = 0; i < A.length; ++i)
if (clamp(A[i],1,n) != clamp(B[i],1,n))
return false;
return true;
} // areOnSameCubie
public static int reverseBits(int x, int nBits)
{
int result = 0;
for (int iBit = 0; iBit < nBits; ++iBit)
result |= (((x>>iBit)&1)<<(nBits-1-iBit));
return result;
} // reverseBits
} // private static class Utils
//=========================================================================
//=========================================================================
//
// Puzzle manipulation utility functions.
// These are functions that could be generally useful
// even when not solving.
//
private static class PuzzleManipulation
{
public static int[] rot90index(int n, int fromAxis, int toAxis, int index[])
{
return Utils.coordsToIndex(n,rot90coords(fromAxis, toAxis, Utils.indexToCoords(n,index)));
}
//
// Rotate coords by the 90 degree rotation
// that takes +fromAxis to +toAxis.
//
public static int[] rot90coords(int fromAxis, int toAxis, int coords[])
{
int result[] = Arrays.copy(coords);
result[toAxis] = coords[fromAxis];
result[fromAxis] = -coords[toAxis];
return result;
} // rot90coords
public static int[][] rot90coordss(int fromAxis, int toAxis, int coordss[][])
{
int result[][] = new int[coordss.length][];
for (int i = 0; i < coordss.length; ++i)
result[i] = rot90coords(fromAxis, toAxis, coordss[i]);
return result;
} // rot90coordss
public static int[] rot90sCoords(int rots[][], int coords[])
{
for (int iRot = 0; iRot < rots.length; ++iRot)
coords = rot90coords(rots[iRot][0], rots[iRot][1], coords);
return coords;
} // rot90sCoords
//
// Apply a twist90 move to a single coords.
//
public static int[] twist90coords(int n, int faceAxis, int faceSign, int fromAxis, int toAxis, int slicesMask, int coords[])
{
int bitIndex = (-faceSign*coords[faceAxis]+n-1)/2;
// XXX this is a bit time consuming... if doing this to many coords at once, consider making an expanded bitmask by duplicating the first and last bit
bitIndex = Utils.clamp(bitIndex,0,n-1); // so stickers move with the slice
if (((slicesMask>>bitIndex)&1) == 1)
return rot90coords(fromAxis, toAxis, coords);
else
return coords;
} // twist90coords
public static int[] twist90coords(int n, int twist[], int coords[])
{
return twist90coords(n, twist[0],twist[1],twist[2],twist[3],twist[4],coords);
} // twist90coords
public static int[] twist90sCoords(int n, int twists[][], int coords[])
{
for (int i = 0; i < twists.length; ++i)
coords = twist90coords(n, twists[i], coords);
return coords;
} // twist90coords
public static int[][] twist90sCoordss(int n, int twists[][], int coordss[][])
{
int result[][] = new int[coordss.length][];
for (int i = 0; i < coordss.length; ++i)
result[i] = twist90sCoords(n, twists, coordss[i]);
return result;
/* equivalent to go the other way, but no one needed a twist90coordss in isolation
for (int i = 0; i < twists.length; ++i)
coordss = twist90coordss(n, twists[i], coords);
return coordss;
*/
} // twist90coords
//
// Rotate or twist
// part or all of the puzzle 90 degrees.
// Returns a new array without altering puz;
// the entries of the result will be the (permuted) entries of puz,
// it doesn't matter what the type of the entries were.
public static Object twist90(int n, int d,
Object puz,
int faceAxis, int faceSign,
int fromAxis,
int toAxis,
int slicesMask)
{
//System.out.println("in twist90");
//
// Canonicalize faceSign to be -1,
// by reversing the bits in slicesMask if it's +1
//
if (faceSign == 1)
{
int newMask = 0;
for (int i = 0; i < n; ++i)
newMask |= ((slicesMask>>(n-1-i))&1)<>Utils.clamp(fromIndex[faceAxis]-1,0,n-1))&1) == 1)
{
//int toIndex[] = Arrays.copy(fromIndex);
Arrays.copy(toIndex, fromIndex);
toIndex[toAxis] = fromIndex[fromAxis];
toIndex[fromAxis] = n+2-1-fromIndex[toAxis];
Arrays.set(result, toIndex, Arrays.get(puz, fromIndex));
}
else
{
Arrays.set(result, fromIndex, Arrays.get(puz, fromIndex)); // XXX note, this is probably actually slower when using an array of char than when using and array of Object, because the former has to allocate a Character for each temporary
}
}
//System.out.println("out twist90");
return result;
} // twist90
public static Object twist90(int n, int d,
Object puz,
int move[/*5*/])
{
return twist90(n, d, puz, move[0],move[1],move[2],move[3],move[4]);
} // twist90
// This is the bottleneck if done naively-- applying the moves
// was taking hundreds of times more time
// than computing the sequences.
// We speed that up by working with flat permutations,
// expressing move permutations as cycle lists,
// and caching the cycle lists of previously seen moves.
public static Object superOptimizedTwist90s(int n, int d,
Object puz,
int moves[][/*5*/])
{
int nIndices = Arrays.intpow(n+2,d);
int scratchPerm[] = new int[nIndices];
int scratchIndex[] = new int[d];
//
// Flatten...
//
Object flatPuz[] = new Object[nIndices];
for (int iIndex = 0; iIndex < nIndices; ++iIndex)
{
Arrays.unFlatIndex(scratchIndex, iIndex, n+2, d);
flatPuz[iIndex] = Arrays.get(puz, scratchIndex);
}
//
// Apply moves to flat puzzle...
//
java.util.HashMap moveToPermutationCycles = new java.util.HashMap();
int nHits = 0, nMisses = 0;
for (int iMove = 0; iMove < moves.length; ++iMove)
{
int move[] = moves[iMove];
String key = ""+move[0]+" "+move[1]+" "+move[2]+" "+move[3]+" "+move[4];
int cycles[] = (int[])moveToPermutationCycles.get(key);
if (cycles == null)
{
// Haven't seen this move before.
// Compute the permutation of the flat array...
int faceAxis = move[0];
int faceSign = move[1];
int fromAxis = move[2];
int toAxis = move[3];
int slicesMask = move[4];
//
// Canonicalize faceSign to be -1,
// by reversing the bits in slicesMask if it's +1
//
if (faceSign == 1)
{
int newMask = 0;
for (int i = 0; i < n; ++i)
newMask |= ((slicesMask>>(n-1-i))&1)<>Utils.clamp(scratchIndex[faceAxis]-1,0,n-1))&1) == 1)
{
int temp = scratchIndex[toAxis];
scratchIndex[toAxis] = scratchIndex[fromAxis];
scratchIndex[fromAxis] = n+2-1-temp;
int jIndex = Arrays.flatIndex(scratchIndex, n+2, d);
scratchPerm[iIndex] = jIndex; // scratchPerm[iIndex] is where iIndex gets taken by this permutation
}
else
{
scratchPerm[iIndex] = iIndex;
}
}
//PRINT(scratchPerm);
// And decompose the permutation into cycles...
// all cycles will have length 4.
java.util.ArrayList cyclesList = new java.util.ArrayList();
for (int iIndex = 0; iIndex < nIndices; ++iIndex)
{
int i0 = scratchPerm[iIndex];
if (i0 != iIndex)
{
int i1 = scratchPerm[i0];
int i2 = scratchPerm[i1];
int i3 = scratchPerm[i2];
Assert(i0 == scratchPerm[i3]);
Assert(i0 != i1);
Assert(i0 != i2);
Assert(i0 != i3);
Assert(i1 != i2);
Assert(i1 != i3);
Assert(i2 != i3);
cyclesList.add(new int[]{i0,i1,i2,i3});
// so we don't do them again...
scratchPerm[i0] = i0;
scratchPerm[i1] = i1;
scratchPerm[i2] = i2;
scratchPerm[i3] = i3;
}
}
// Concatenate the 4-cycles into a flat list
// to save space.
cycles = (int[])Arrays.concat(cyclesList.toArray(new int[0][8675309]));
//PRINT(cycles);
//PRINT(cycles.length);
moveToPermutationCycles.put(key, cycles);
nMisses++;
}
else
nHits++;
for (int iCycle = 0; iCycle < cycles.length; )
{
int i0 = cycles[iCycle++];
int i1 = cycles[iCycle++];
int i2 = cycles[iCycle++];
int i3 = cycles[iCycle++];
Object o0 = flatPuz[i0];
Object o1 = flatPuz[i1];
Object o2 = flatPuz[i2];
Object o3 = flatPuz[i3];
flatPuz[i1] = o0;
flatPuz[i2] = o1;
flatPuz[i3] = o2;
flatPuz[i0] = o3;
}
}
//
// Unflatten...
//
Object outPuz = Arrays.repeat(null, n+2, d);
for (int iIndex = 0; iIndex < nIndices; ++iIndex)
{
int index[] = Arrays.unFlatIndex(iIndex, n+2, d);
Arrays.set(outPuz, index, flatPuz[iIndex]);
}
//PRINT(nHits);
//PRINT(nMisses);
return outPuz;
} // superOptimizedTwist90s
// THIS IS THE BOTTLENECK!
public static Object twist90s(int n, int d,
Object puz,
int moves[][/*5*/])
{
if (true)
return superOptimizedTwist90s(n, d, puz, moves);
for (int i = 0; i < moves.length; ++i)
puz = twist90(n, d, puz, moves[i]);
return puz;
} // twist90s
public static Object twist90s(int n, int d,
Object puz,
java.util.ArrayList movesList)
{
return twist90s(n, d, puz, (int[][])movesList.toArray(new int[0][])); // gross!
} // twist90s
public static int[] randomTwist90(int n, int d, java.util.Random generator)
{
Assert(d >= 3); // otherwise we'll endless loop trying to find 3 distinct axes
int faceAxis, fromAxis, toAxis;
while (true)
{
faceAxis = generator.nextInt(d);
fromAxis = generator.nextInt(d);
toAxis = generator.nextInt(d);
if (faceAxis != fromAxis
&& fromAxis != toAxis
&& toAxis != faceAxis)
break;
}
int faceSign = generator.nextInt(2)*2-1; // -1 or 1
int slicesMask = 1; // twists just the one face
if (n >= 2)
{
int nChoices = n/2; // 2->1 3->1 4->2 5->2 6->3 7->3 etc.
slicesMask = 1<= 3)
System.out.println(" throwing away garbage int "+garbageBit);
int nScrambleChen = minScrambleChen
+ generator.nextInt(maxScrambleChen+1-minScrambleChen);
int twists[][] = randomTwists90(nScrambleChen, n, d, generator);
for (int i = 0; i < nScrambleChen; ++i)
{
if (debugLevel >= 2)
{
int faceAxis = twists[i][0];
int faceSign = twists[i][1];
int fromAxis = twists[i][2];
int toAxis = twists[i][3];
int slicesMask = twists[i][4];
System.out.print(" i="+i);
System.out.print(" face="+(faceSign<0?"-":"+")+faceAxis);
System.out.print(" from="+fromAxis);
System.out.print(" to="+toAxis);
System.out.print(" slicesMask="+slicesMask);
System.out.println();
}
}
return twists;
} // scramble
// a move is:
// {toAxis,toSign,fromAxis,fromSign,faceAxis,faceSign,slicesMask}
// its inverse simply reverses the to and from:
// {fromAxis,fromSign,toAxis,toSign,faceAxis,faceSign,slicesMask}
//
public static int[] reverseMove(int move[])
{
return new int[] {
move[0], // same faceAxis
move[1], // same faceSign
move[3], // fromAxis = original toAxis
move[2], // toAxis = original fromAxis
move[4], // same slicesMask
};
}
public static int[][] reverseMoves(int moves[][])
{
int reversed[][] = new int[moves.length][];
for (int i = 0; i < moves.length; ++i)
reversed[i] = reverseMove(moves[moves.length-1-i]);
return reversed;
}
// convenience function that figures out an equivalent
// twist in which fromSign,toSign are positive
// and can be omitted.
// XXX look for places I did this by hand before that would be clearer by using this
public static int[] makeTwist90(int faceAxis, int faceSign,
int fromAxis, int fromSign,
int toAxis, int toSign,
int slicesMask)
{
Assert(faceSign == 1 || faceSign == -1);
Assert(fromSign == 1 || fromSign == -1);
Assert(toSign == 1 || toSign == -1);
Assert(faceAxis != fromAxis);
Assert(fromAxis != toAxis);
Assert(toAxis != faceAxis);
if (fromSign == toSign)
return new int[] {faceAxis,faceSign, fromAxis,toAxis, slicesMask};
else
return new int[] {faceAxis,faceSign, toAxis,fromAxis, slicesMask};
} // makeTwist90
private static boolean isStickerIndex(int n, int d, int index[])
{
int nExtremes = 0;
for (int iDim = 0; iDim < d; ++iDim)
if (index[iDim] == 0
|| index[iDim] == n+1)
nExtremes++;
return nExtremes == 1;
} // isStickerIndex
private static boolean isCubieIndex(int n, int d, int index[])
{
for (int iDim = 0; iDim < d; ++iDim)
if (index[iDim] == 0
|| index[iDim] == n+1)
return false;
return true;
} // isCubieIndex
public static int[][] makeSoDoesntMoveFirstCubie(int n, int d, int moves[][], int debugLevel)
{
if (debugLevel >= 1) System.out.println("in makeSoDoesntMoveFirstCubie");
if (debugLevel >= 3) System.out.println(" moves = "+Arrays.toString(moves));
int movesOut[][] = new int[moves.length][];
int worldAxesInCubie0Space[] = Arrays.identityperm(d);
int worldSignsInCubie0Space[] = Arrays.repeat(1, d);
for (int iMove = 0; iMove < moves.length; ++iMove)
{
int move[] = moves[iMove];
int worldSpaceFaceAxis = move[0];
int worldSpaceFaceSign = move[1];
int worldSpaceFromAxis = move[2];
int worldSpaceFromSign = 1;
int worldSpaceToAxis = move[3];
int worldSpaceToSign = 1;
int slicesMask = move[4];
// Convert to cubie0 space...
int cubie0SpaceFaceAxis = worldAxesInCubie0Space[worldSpaceFaceAxis];
int cubie0SpaceFaceSign = worldSpaceFaceSign * worldSignsInCubie0Space[worldSpaceFaceAxis];
int cubie0SpaceFromAxis = worldAxesInCubie0Space[worldSpaceFromAxis];
int cubie0SpaceFromSign = worldSpaceFromSign * worldSignsInCubie0Space[worldSpaceFromAxis];
int cubie0SpaceToAxis = worldAxesInCubie0Space[worldSpaceToAxis];
int cubie0SpaceToSign = worldSpaceToSign * worldSignsInCubie0Space[worldSpaceToAxis];
int bit = cubie0SpaceFaceSign==-1 ? 0 : n-1;
if (((slicesMask>>bit)&1) == 1) // if it includes cubie 0
{
if (debugLevel >= 5) System.out.println(" YES it included cubie 0");
// Express as the opposite twist of the opposite face
slicesMask = Utils.reverseBits(~slicesMask, n);
cubie0SpaceFaceSign *= -1;
cubie0SpaceToSign *= -1; // negate just one of them
// Update world axes in cubie0 space
// by applying this move.
{
int temp = worldAxesInCubie0Space[worldSpaceToAxis];
worldAxesInCubie0Space[worldSpaceToAxis] = worldAxesInCubie0Space[worldSpaceFromAxis];
worldAxesInCubie0Space[worldSpaceFromAxis] = temp;
}
{
int temp = worldSignsInCubie0Space[worldSpaceToAxis];
worldSignsInCubie0Space[worldSpaceToAxis] = worldSignsInCubie0Space[worldSpaceFromAxis];
worldSignsInCubie0Space[worldSpaceFromAxis] = -temp;
}
}
else
{
if (debugLevel >= 5) System.out.println(" NO it did not include cubie 0");
}
movesOut[iMove] = makeTwist90(cubie0SpaceFaceAxis, cubie0SpaceFaceSign, cubie0SpaceFromAxis, cubie0SpaceFromSign, cubie0SpaceToAxis, cubie0SpaceToSign, slicesMask);
if (debugLevel >= 5) // super heavy duty debug with more assertions
{
System.out.println(" iMove = "+iMove);
System.out.println(" moves = "+Arrays.toString(Arrays.subArray(moves, 0, iMove+1)));
System.out.println(" movesOut = "+Arrays.toString(Arrays.subArray(movesOut, 0, iMove+1)));
System.out.println(" worldAxesInCubie0Space = "+Arrays.toString(worldAxesInCubie0Space));
System.out.println(" worldSignsInCubie0Space = "+Arrays.toString(worldSignsInCubie0Space));
// Make sure we didn't alter the meaning
// of the move sequence on any coordinate...
int nIndices = Arrays.intpow(n+2,d);
for (int iIndex = 0; iIndex < nIndices; ++iIndex)
{
int index[] = Arrays.unFlatIndex(iIndex, n+2, d);
int coords[] = Utils.indexToCoords(n, index);
int twistedCoordsInCubie0Space[] = PuzzleManipulation.twist90sCoords(n, Arrays.subArray(movesOut,0,iMove+1), coords);
int twistedCoordsInWorldSpace[] = PuzzleManipulation.twist90sCoords(n, Arrays.subArray(moves,0,iMove+1), coords);
System.out.println(" "+Arrays.toString(coords)+" -> (cubie0)"+Arrays.toString(twistedCoordsInCubie0Space)+", (world)"+Arrays.toString(twistedCoordsInWorldSpace));
int twistedCoordsInWorldSpaceMappedToCubie0Space[] = Arrays.repeat(-999, d);
for (int iDim = 0; iDim < d; ++iDim)
{
twistedCoordsInWorldSpaceMappedToCubie0Space[worldAxesInCubie0Space[iDim]] =
twistedCoordsInWorldSpace[iDim] * worldSignsInCubie0Space[iDim];
}
System.out.println(" -> (world to cubie0)"+Arrays.toString(twistedCoordsInWorldSpaceMappedToCubie0Space));
Assert(Arrays.equals(twistedCoordsInCubie0Space, twistedCoordsInWorldSpaceMappedToCubie0Space));
}
}
}
if (debugLevel >= 3) System.out.println(" movesOut = "+Arrays.toString(movesOut));
if (debugLevel >= 1) System.out.println("out makeSoDoesntMoveFirstCubie");
return movesOut;
} // makeSoDoesntMoveFirstCubie
} // private static class PuzzleManipulation
//=========================================================================
//
// Internal solve function and building blocks thereof.
//
private static class SolveStuff
{
//
// Solve the puzzle, given puz which is
// an array of sticker colors (letters).
// Returns a sequence of moves of the form
// {faceAxis,faceSign, fromAxis,toAxis, slicesMask}.
//
public static int[][/*5*/] solve(int n, int d, Object puz,
int whichToPosition, // bit mask
int whichToOrient, // bit mask
java.io.PrintWriter progressWriter,
int debugLevel)
{
if (debugLevel >= 1) System.out.println("in SolveStuff.solve");
//PRINT(puz);
// so that we flush after every newline,
// to guarantee sanity in case interspersed with debugging output...
// Note, without this, we aren't guaranteed to flush at the end
// either.
// XXX since we are going to do this,
// XXX should we even require progressWriter to be
// XXX a printWriter to begin with?
if (progressWriter != null)
progressWriter = new java.io.PrintWriter(progressWriter, true);
long time0 = System.currentTimeMillis();
long time1 = time0;
// stuff to orient must be a subset of stuff to position...
// (if the caller has positioned stuff already,
// it doesn't hurt to position again, it won't produce
// any more moves)
// XXX should we just set whichToPosition |= whichToOrient?
Assert((whichToOrient & ~whichToPosition) == 0);
//
// Figure out the indices where the stickers and cubie centers want to be.
//
Object puzzleIndices = figureOutWhereIndicesWantToBe(n,d,puz);
//PRINT(puzzleIndices);
//
// We won't modify puz,
// but we will permute puzzleIndices,
// gradually turning it into the solved state
// as we build the solution.
//
//
// Figure out whether the state is even or odd.
// (It's an odd state iff it's an odd permutation
// on the 2-sticker cubies.)
// If it's odd, then start by applying one single arbitrary 90-degree twist.
//
java.util.ArrayList solution = new java.util.ArrayList();
if (puzzleStateIsOdd(n,d,puzzleIndices))
{
if (progressWriter != null) progressWriter.print(" It's odd, applying one twist to fix parity...");
solution.add(new int[]{0,+1, 1,2, 1}); // XXX this is arbitrary-- maybe should try every possible twist and see which one helps the most?
//System.out.print("before applying parity-fixing twist: ");
//PRINT(puzzleIndices);
puzzleIndices = PuzzleManipulation.twist90s(n,d,puzzleIndices,
solution);
//System.out.print("after applying parity-fixing twist: ");
//PRINT(puzzleIndices);
//System.out.println(PuzzleIO.puzzleToString(n,d,puzzleIndices));
}
else
{
if (progressWriter != null) progressWriter.print(" It's even "); // no newline
}
if (progressWriter != null)
{
long time2 = System.currentTimeMillis();
progressWriter.println(" "+(time2-time0)/1000.+" secs");
time1 = time2;
}
//
// position the 2-sticker cubies,
// orient the 2-sticker cubies,
// position the 3-sticker cubies,
// orient the 3-sticker cubies,
// ...
// position the d-sticker cubies,
// orient the d-sticker cubies.
//
for (int k = 2; k <= d; ++k)
{
if (n < 3 && k < d)
continue; // there are no k-sticker cubies
boolean doPosition = ((whichToPosition & (1<= 2) System.out.println(" solution ="+Arrays.toString(solution));
if (debugLevel >= 1) System.out.println("out SolveStuff.solve");
return (int[][])solution.toArray(new int[0][846372622]); // if they can be retarded then I can be more retarded
} // solve
//
// Given puz which is sticker letters and spaces,
// figure out the indices where the stickers and cubie centers
// want to be. Return a multidimensional array containing,
// for each index, where the guy currently at that index wants to be.
//
private static Object figureOutWhereIndicesWantToBe(int n, int d, Object puz)
{
//
// Get the axis letters.
//
char colors[][] = PuzzleIO.getSignedAxisColors(n, d, puz);
java.util.HashMap letterToFaceCenterCubieCoords = new java.util.HashMap();
for (int iDim = 0; iDim < d; ++iDim)
{
int stickerCoords[] = Arrays.repeat(0, d);
int cubieCoords[] = Arrays.repeat(0, d);
for (int sign = -1; sign <= 1; sign += 2)
{
stickerCoords[iDim] = sign*(n+1);
cubieCoords[iDim] = sign*(n-1);
Character letter = new Character(colors[iDim][(sign+1)/2]);
Assert(!Character.isWhitespace(letter.charValue()));
Assert(!letterToFaceCenterCubieCoords.containsKey(letter));
//letterToFaceCenterCubieCoords.put(letter, Arrays.copy(cubieCoords)); // was doing this, but messes up if n==1
letterToFaceCenterCubieCoords.put(letter, Arrays.copy(stickerCoords));
}
}
//PRINT(letterToFaceCenterCubieCoords);
int nIndices = Arrays.intpow(n+2,d);
// Start by setting all answer coords of cubie centers
// to zero; we will accumulate
// into each cubie center the desired coords of the face center of each sticker
// that contributes to it.
Object answer = Arrays.repeat(null, n+2, d);
for (int iIndex = 0; iIndex < nIndices; ++iIndex)
{
int index[] = Arrays.unFlatIndex(iIndex, n+2, d);
Arrays.set(answer, index, Arrays.repeat(0, d));
}
for (int iIndex = 0; iIndex < nIndices; ++iIndex)
{
int index[] = Arrays.unFlatIndex(iIndex, n+2, d);
Character letter = (Character)Arrays.get(puz,index);
if (letter.charValue() != ' ')
{
Assert(letterToFaceCenterCubieCoords.containsKey(letter));
int contribution[] = (int[])letterToFaceCenterCubieCoords.get(letter);
int cubieCenterIndex[] = Arrays.clamp(index,1,n);
int temp[] = (int[])Arrays.get(answer, cubieCenterIndex);
temp = Arrays.plus(temp, contribution);
temp = Arrays.clamp(temp, -(n-1), n-1);
Arrays.set(answer, cubieCenterIndex, temp);
//System.out.println(" the "+letter+" at index "+Arrays.toString(index)+" contributes "+Arrays.toString(contribution)+" to the cubie center at index "+Arrays.toString(cubieCenterIndex));
}
}
//System.out.println(" coords where cubie centers want to be: "+Arrays.toString(answer));
// Okay, now we know where each cubie center wants to be (assuming n<=3).
// To figure out where each sticker wants to be,
// look at where its cubie wants to be and go 2 units in the direction of the face
// of the sticker color.
for (int iIndex = 0; iIndex < nIndices; ++iIndex)
{
int index[] = Arrays.unFlatIndex(iIndex,n+2,d);
Character letter = (Character)Arrays.get(puz,index);
if (letter.charValue() != ' ')
{
int cubieCenterIndex[] = Arrays.clamp(index,1,n);
int whereCubieCenterWantsToBe[] = (int[])Arrays.get(answer, cubieCenterIndex);
int contribution[] = (int[])letterToFaceCenterCubieCoords.get(letter);
contribution = Arrays.plus(contribution, contribution); // so at least 2 in all nonzero dirs
contribution = Arrays.clamp(contribution, -2, 2);
int whereStickerWantsToBe[] = Arrays.plus(whereCubieCenterWantsToBe, contribution);
//PRINT(index);
//PRINT(cubieCenterIndex);
//PRINT(whereCubieCenterWantsToBe);
//PRINT(contribution);
//PRINT(whereStickerWantsToBe);
//System.out.println(" ");
Arrays.set(answer, index, whereStickerWantsToBe);
}
}
//System.out.println(" coords where cubie centers and stickers want to be: "+Arrays.toString(answer));
// Convert from coords to indices, and null out the air.
for (int iIndex = 0; iIndex < nIndices; ++iIndex)
{
int index[] = Arrays.unFlatIndex(iIndex, n+2, d);
int hist[] = Utils.histogram(n+2,index);
int coords[] = (int[])Arrays.get(answer, index);
if (hist[0]+hist[n+1] > 1)
{
Assert(Arrays.isAll(coords,0));
Arrays.set(answer, index, null);
}
else
{
Arrays.set(answer, index, Utils.coordsToIndex(n,coords));
}
}
//System.out.println(" to indices, with air nulled out: "+Arrays.toString(answer));
// Make sure the mapping is 1-to-1 and onto.
{
Object inverse = Arrays.repeat(null, n+2, d);
for (int iIndex = 0; iIndex < nIndices; ++iIndex)
{
int index[] = Arrays.unFlatIndex(iIndex,n+2,d);
int hist[] = Utils.histogram(n+2,index);
int target[] = (int[])Arrays.get(answer, index);
if (target != null)
{
Assert(Arrays.equals(target, Arrays.clamp(target, 0, n+1))); // index in bounds
int targetHist[] = Utils.histogram(n+2,target);
Assert(targetHist[0]+targetHist[n+1] <= 1); // not air
Assert(Arrays.get(inverse, target) == null); // 1-to-1
Arrays.set(inverse, target, index);
}
}
}
return answer;
} // figureOutWhereIndicesWantToBe
//
// Find a sequence of moves
// that properly positions the k-sticker cubies,
// without messing up the fewer-sticker cubies,
// but freely messing up the more-sticker cubies.
// Assumes puzzle state is even.
//
private static java.util.ArrayList position_ksticker_cubies(int k, int n, int d, Object puzzleIndices, int debugLevel)
{
if (debugLevel >= 1) System.out.println(" in position_"+k+"sticker_cubies");
//
// Decompose the permutation on the k-sticker cubies
// into cycles, omitting cycles of length 1.
//
int cycles[][][] = {}; // XXX bogus O(n^2)
Object scratch = Arrays.repeat(new Object(), n+2, d); // set entries in scratch to null as we've seen them during position parity checking
int nIndices = Arrays.intpow(n+2,d);
for (int iIndex = 0; iIndex < nIndices; ++iIndex)
{
int index[] = Arrays.unFlatIndex(iIndex,n+2,d);
// It's the center of a k-sticker cubie
// iff all coords are in [1..n]
// and it's 1 or n in exactly k axis directions.
int hist[] = Utils.histogram(n+2,index);
boolean isKStickerCubieCenter = (hist[0]==0
&& hist[n+1]==0
&& hist[1]+hist[n] == k);
if (isKStickerCubieCenter)
{
int cycle[][] = {}; // XXX bogus O(n^2)
while (Arrays.get(scratch,index) != null)
{
cycle = Arrays.append(cycle,index);
Arrays.set(scratch,index,null);
index = (int[])Arrays.get(puzzleIndices,index);
}
if (cycle.length > 1) // omit cycles of length 1
cycles = Arrays.append(cycles,cycle);
}
}
if (debugLevel >= 2) System.out.println(" cycles="+Arrays.toString(cycles));
//
// Further decompose the cyclic decomposition
// into 3-cycles.
// This is possible because the puzzle state is even.
//
// XXX this code is duplicated below-- should make a common function
//
int tricycles[][][] = {}; // XXX bogus O(n^2)
for (int iCycle = 0; iCycle < cycles.length; ++iCycle)
{
//PRINT(iCycle);
// (a b c d e f g h) -> (a b c) (a d e) (a f g) (a h)
int cycle[][] = cycles[iCycle];
//PRINT(cycle);
if (cycle == null)
{
//PRINT(__LINE__);
continue; // already used this cycle
}
while (cycle.length != 1)
{
if (cycle.length == 2)
{
// Mingle with another cycle of even length,
// to get a 3-cycle and a cycle of odd length.
// XXX this can get n^2, should
int other[][] = null;
for (int jCycle = iCycle+1; jCycle < cycles.length; ++jCycle)
{
//PRINT(jCycle);
//PRINT(cycles[jCycle]);
if (cycles[jCycle] != null
&& cycles[jCycle].length % 2 == 0)
{
other = cycles[jCycle];
cycles[jCycle] = null;
break;
}
}
Assert(other != null);
//PRINT(other);
// (a b) (c d e f g h) -> (a b c) (c a d e f g h)
tricycles = Arrays.append(tricycles, Arrays.append(cycle, other[0]));
cycle = Arrays.insert(other, 1, cycle[0]);
//System.out.println(" join ->"+Arrays.toString(tricycles[tricycles.length-1])+Arrays.toString(cycle));
}
else
{
// (a b c d e f g) -> (a b c) (a d e f g)
// or, in particular,
// (a b c) -> (a b c) (a)
tricycles = Arrays.append(tricycles, Arrays.subArray(cycle,0,3));
cycle = Arrays.deleteRange(cycle, 1, 2);
//System.out.println(" split ->"+Arrays.toString(tricycles[tricycles.length-1])+Arrays.toString(cycle));
}
}
}
if (debugLevel >= 2) System.out.println(" tricycles="+Arrays.toString(tricycles));
//
// Find a sequence of moves that accomplishes the desired 3-cycles.
//
java.util.ArrayList solution = new java.util.ArrayList();
for (int i = 0; i < tricycles.length; ++i)
Arrays.addAll(solution, cycle_3_ksticker_cubies(k,n,d,tricycles[i], debugLevel));
if (debugLevel >= 2) System.out.println(" solution = "+Arrays.toString(solution));
if (debugLevel >= 1) System.out.println(" out position_"+k+"sticker_cubies");
return solution;
} // position_ksticker_cubies
// Find a sequence of moves that cycles three k-sticker cubies,
// without messing up any other cubies with k or fewer stickers,
// but freely messing up cubies with more than k stickers.
private static int[][] cycle_3_ksticker_cubies(int k, int n, int d, int tricycle[/*3*/][/*d*/], int debugLevel)
{
if (debugLevel >= 2) System.out.println(" in cycle_3_"+k+"sticker_cubies");
Object toLsequence_and_Lcycle[] = take_tricycle_to_L_of_ksticker_cubies_INDICES(k,n,d,tricycle,debugLevel);
int toLsequence[][] = (int[][])toLsequence_and_Lcycle[0];
int Lcycle[][] = (int[][])toLsequence_and_Lcycle[1];
int fromLsequence[][] = PuzzleManipulation.reverseMoves(toLsequence);
int solution[][] = Arrays.concat3(toLsequence,
cycle_L_of_ksticker_cubies_INDICES(k,n,d,
Lcycle,
debugLevel),
fromLsequence);
if (debugLevel >= 3) System.out.println(" solution = "+Arrays.toString(solution));
if (debugLevel >= 2) System.out.println(" out cycle_3_"+k+"sticker_cubies");
return solution;
} // cycle_3_ksticker_cubies
// Find a sequence of moves that cycles three k-sticker cubies
// that are in the shape of an L -- that is,
// they all lie in a single 2-plane, and the middle one
// is the knee of the L:
// A B
// C
// Don't mess up any other cubies with k or fewer stickers,
// but freely mess up cubies with more than k stickers.
private static int[][] cycle_L_of_ksticker_cubies_INDICES(int k, int n, int d,
int Lcycle[/*3*/][/*d*/],
int debugLevel)
{
if (debugLevel >= 2) System.out.println(" in cycle_L_of_"+k+"sticker_cubies");
if (debugLevel >= 3) System.out.println(" Lcycle="+Arrays.toString(Lcycle));
// argh, we are translating back and forth a lot
int A[] = Utils.indexToCoords(n,Lcycle[0]);
int B[] = Utils.indexToCoords(n,Lcycle[1]);
int C[] = (Lcycle.length==2 ? null : Utils.indexToCoords(n,Lcycle[2]));
//PRINT(A);
//PRINT(B);
//PRINT(C);
Assert(Arrays.normSqrd(A) == Arrays.normSqrd(B));
Assert(Arrays.normSqrd(B) == Arrays.normSqrd(C));
int solution[][];
Assert(k >= 2); // impossible to move the 1-sticker cubies
if (k == 2)
{
// Special case... our cycle-slabs function
// doesn't know how to cycle an L of (d-2)-slabs
// since it's awkward, but we don't need to.
// Cycling an L of 2-sticker cubies is easy,
// since we are allowed to mess up the higher-sticker
// cubies...
// On the standard Rubik's cube:
// (BU FU FD): U U F F U U F F
// Come to think of it, this does actually cycle
// the (d-2)-slabs
// (i.e. it cycles the 3 edges on the Rubik's cube)
// however it flips two of them, which would violate
// our cycle-slabs function's contract.
//
// ABface = the face containing A,B (and not C)
int ABfaceCenter[] = Arrays.average(A,B);
int ABfaceAxis = 0;
while (ABfaceCenter[ABfaceAxis] == 0)
ABfaceAxis++;
int ABfaceSign = (A[ABfaceAxis] < 0 ? -1 : 1);
// BCface = the face containing B,C (and not A)
int BCfaceCenter[] = Arrays.average(B,C);
int BCfaceAxis = 0;
while (BCfaceCenter[BCfaceAxis] == 0)
BCfaceAxis++;
int BCfaceSign = (B[BCfaceAxis] < 0 ? -1 : 1);
//PRINT(ABfaceCenter);
//PRINT(ABfaceAxis);
//PRINT(ABfaceSign);
//PRINT(BCfaceCenter);
//PRINT(BCfaceAxis);
//PRINT(BCfaceSign);
int AB[][] = find_oneface_twist_sequence_taking_these_coords_to_those_coords(ABfaceAxis,ABfaceSign, new int[][]{A}, new int[][]{B}, 1, debugLevel);
Assert(AB.length == 2); // it's a 180 degree twist
int BC[][] = find_oneface_twist_sequence_taking_these_coords_to_those_coords(BCfaceAxis,BCfaceSign, new int[][]{B}, new int[][]{C}, 1, debugLevel);
Assert(BC.length == 2); // it's a 180 degree twist
solution = (int[][])Arrays.concat4(AB, BC, AB, BC);
}
else // k >= 3
{
solution = cycle_L_of_kslabs(d-k, n, d,
A,B,C, debugLevel);
}
if (debugLevel >= 3) System.out.println(" solution = "+Arrays.toString(solution));
if (debugLevel >= 2) System.out.println(" out cycle_L_of_"+k+"sticker_cubies");
return solution;
} // cycle_L_of_ksticker_cubies
//
// A 0-slab is a corner cubie,
// a 1-slab is the set of n cubies along some edge,
// a 2-slab is the set of n^2 cubies on some 2-face, etc.
// a (d-1)-slab is a face,
// a d-slab is the whole puzzle.
// Three k-slabs are said to form an L
// if they are the extrusion (in some consistent set of k dimensions)
// of three corner cubies that form an L (see above).
// This function finds a sequence of moves
// that moves the k-slabs a to b, b to c, and c to a,
// keeping the orientations of the slabs consistent
// in the slab directions,
// and without messing up the rest of the puzzle.
// Only works for k <= d-3
// (cycling three (d-2)-slabs while keeping their orientations
// consistent is more awkward, so we do something else
// in that case instead, in the calling function).
//
// We represent a k-slab by the coordinates of its center
// (which will be zero in k coordinates
// and nonzero in d-k coordinates).
//
private static int[][] cycle_L_of_kslabs(int k, int n, int nDims,
int a[], int b[], int c[],
int debugLevel)
{
if (debugLevel >= 2) System.out.println(" in cycle_L_of_"+k+"slabs");
Assert(k <= nDims-3); // assumption, see above
int solution[][];
if (k == nDims-3)
{
//
// Base case of the recursion--
// this is essentially the case
// of cycling three corner (3-sticker) cubies
// on a standard Rubik's cube, which can be done in 8 moves.
// From Tom Davis's "Permutation Groups and Rubik's Cube":
// http://mathcircle.berkeley.edu/BMC3/perm/node15.html:
// (LUF RUB LUB): U R U' L' U R' U' L
// (where unprimed means clockwise,
// primed means counterclockwise)
//
// Looking top-down at the cube:
//
// b = LUB<-RUB = a
// | ^
// | /
// v /
// c = LUF
//
// The face U is the unique face containing a,b,c...
int UfaceAxis = 0;
while (a[UfaceAxis] == 0
|| a[UfaceAxis] != b[UfaceAxis]
|| b[UfaceAxis] != c[UfaceAxis])
UfaceAxis++;
int UfaceSign = (a[UfaceAxis] < 0 ? -1 : 1);
// The face L is the unique face containing b,c but not a.
int LfaceAxis = 0;
while (a[LfaceAxis] == 0
|| a[LfaceAxis] == b[LfaceAxis]
|| b[LfaceAxis] != c[LfaceAxis])
LfaceAxis++;
int LfaceSign = (b[LfaceAxis] < 0 ? -1 : 1);
// The face F is the unique face containing c but not a,b.
int FfaceAxis = 0;
while (a[FfaceAxis] == 0
|| a[FfaceAxis] != b[FfaceAxis]
|| b[FfaceAxis] == c[FfaceAxis])
FfaceAxis++;
int FfaceSign = (c[FfaceAxis] < 0 ? -1 : 1);
// The face R is the face opposite L.
int RfaceAxis = LfaceAxis;
int RfaceSign = -LfaceSign;
int U[] = PuzzleManipulation.makeTwist90(UfaceAxis,UfaceSign, FfaceAxis,FfaceSign, LfaceAxis,LfaceSign, 1);
int L[] = PuzzleManipulation.makeTwist90(LfaceAxis,LfaceSign, UfaceAxis,UfaceSign, FfaceAxis,FfaceSign, 1);
int R[] = PuzzleManipulation.makeTwist90(RfaceAxis,RfaceSign, FfaceAxis,FfaceSign, UfaceAxis,UfaceSign, 1);
int Uprime[] = PuzzleManipulation.reverseMove(U);
int Lprime[] = PuzzleManipulation.reverseMove(L);
int Rprime[] = PuzzleManipulation.reverseMove(R);
solution = new int[][] {U,R,Uprime,Lprime,U,Rprime,Uprime,L};
}
else // k < nDims-2
{
//
// Assume (inductive step) that we know how
// to cycle any L of (k+1)-slabs.
// We want to cycle the L of k-slabs a,b,c.
// Let d = a-b+c (i.e. the 4th corner of the square);
// d will be used as a helper k-slab.
//
// Take any axis orthogonal to these k-slabs,
// and extrude a,b,c,d along that axis
// to form (k+1)-slabs A,B,C,D.
//
// Observe that the L-tricycle (a b c)
// can be expressed as the composition
// of two L-tricycles (d a b) (a d c)
// (the first in the original direction,
// the second in the opposite direction).
// Since the second one (a d c) is in the opposite direction
// from the first one (d a b),
// it is the conjugation of (a d c)^-1 by a rotation
// of the square, namely:
// (a d c) = (a b c d) (d a b)^-1 (a b c d)^-1
// Putting these facts together,
// we get a useful decomposition of the desired cycle:
// (a b c) = (d a b) (a b c d) (d a b)^-1 (a b c d)^-1
//
// We will do the (d a b) and (d a b)^-1 parts
// as (D A B) and (D A B)^-1 (which we know
// how to do recursively), and we will do
// the (a b c d) and (a b c d)^-1 parts
// by simply twisting the face
// that contains a,b,c,d but none of the rest
// of A,B,C,D.
// The result: (a b c) get cycled as desired
// and the rest of the puzzle is back to the way it was.
// Woo hoo!
//
// So:
// foo = cycle_L_of_kslabs(D,A,B)
// bar = twist of the face containing a,b,c,d
// but not any of the rest of A,B,C,D,
// that cycles (a b c d).
// and the answer is foo bar foo^-1 bar^-1.
//
int d[] = Arrays.plus(Arrays.minus(a,b),c);
// faceAxis = any axis in which a,b,c,d are nonzero
// and have the same coordinate
int faceAxis = 0;
while (a[faceAxis] == 0
|| a[faceAxis] != b[faceAxis]
|| b[faceAxis] != c[faceAxis])
faceAxis++;
int faceSign = (a[faceAxis] < 0 ? -1 : 1);
// Extrude the k-slabs a,b,c,d
// in the direction normal to faceAxis
// to get the (k+1)-slabs A,B,C,D...
int A[] = Arrays.copy(a); A[faceAxis] = 0;
int B[] = Arrays.copy(b); B[faceAxis] = 0;
int C[] = Arrays.copy(c); C[faceAxis] = 0;
int D[] = Arrays.copy(d); D[faceAxis] = 0;
// foo is the sequence of moves that cycles
// the L of (k+1)-slabs (D A B)
int foo[][] = cycle_L_of_kslabs(k+1, n, nDims, D,A,B, debugLevel);
// bar is the single 90 degree twist of this face that takes
// a to b and b to c (and c to d and d to a)...
int bar[][] = find_oneface_twist_sequence_taking_these_coords_to_those_coords(faceAxis, faceSign, new int[][]{a,b}, new int[][]{b,c}, 1, debugLevel);
Assert(bar.length == 1);
// Assert that bar does indeed cycle (a b c d)...
Assert(Arrays.equals(PuzzleManipulation.twist90coords(n,bar[0],a), b));
Assert(Arrays.equals(PuzzleManipulation.twist90coords(n,bar[0],b), c));
Assert(Arrays.equals(PuzzleManipulation.twist90coords(n,bar[0],c), d));
Assert(Arrays.equals(PuzzleManipulation.twist90coords(n,bar[0],d), a));
solution = (int[][])Arrays.concat4(foo,
bar,
PuzzleManipulation.reverseMoves(foo),
PuzzleManipulation.reverseMoves(bar));
} // k < nDims-2 inductive case
if (debugLevel >= 2) System.out.println(" out cycle_L_of_"+k+"slabs");
return solution;
} // cycle_L_of_kslabs
// Take the given three cubie centers to an L,
// freely messing up everything else.
// Tricycle is allowed to be of length 2 as well, meaning
// just take them to an I.
private static Object[] take_tricycle_to_L_of_ksticker_cubies_INDICES(int k, int n, int d, int tricycle[][], int debugLevel)
{
if (debugLevel >= 2) System.out.println(" in take_tricycle_to_L_of_"+k+"sticker_cubies");
int A[] = Utils.indexToCoords(n,tricycle[0]);
int B[] = Utils.indexToCoords(n,tricycle[1]);
int C[] = (tricycle.length == 2 ? null : Utils.indexToCoords(n,tricycle[2]));
if (debugLevel >= 3)
{
System.out.println(" tricycle = "+Arrays.toString(tricycle));
System.out.println(" A = "+Arrays.toString(A));
System.out.println(" B = "+Arrays.toString(B));
System.out.println(" C = "+Arrays.toString(C));
}
Assert(!Arrays.equals(A,B));
if (C != null)
{
Assert(!Arrays.equals(B,C));
Assert(!Arrays.equals(C,A));
}
int solution[][] = {};
//PRINT(__LINE__);
// Move B so it's next to A, without perturbing A
{
// Goal is to make B differ from A
// in exactly one coordinate axis.
int nIndicesDifferent = Arrays.nIndicesDifferent(A,B);
//PRINT(nIndicesDifferent);
Assert(nIndicesDifferent >= 1);
if (nIndicesDifferent > 1)
{
// BtargetFaceAxis = any axis in which A is nonzero
// (doesn't matter what B is along that axis)
int BtargetFaceAxis = 0;
while (A[BtargetFaceAxis] == 0)
BtargetFaceAxis++;
int BtargetFaceSign = (A[BtargetFaceAxis] < 0 ? 1 : -1); // opposite A
int Btarget[] = Arrays.copy(A);
Btarget[BtargetFaceAxis] = -A[BtargetFaceAxis];
//PRINT(BtargetFaceAxis);
//PRINT(BtargetFaceSign);
//PRINT(Btarget);
// Get B onto BtargetFace, if it's not already there...
if (B[BtargetFaceAxis] != Btarget[BtargetFaceAxis])
{
// BhelperFace = any face that contains B but not A
int BhelperFaceAxis = 0;
while (B[BhelperFaceAxis] == 0
|| A[BhelperFaceAxis] == B[BhelperFaceAxis])
BhelperFaceAxis++;
int BhelperFaceSign = (B[BhelperFaceAxis] < 0 ? -1 : 1);
//PRINT(BhelperFaceAxis);
//PRINT(BhelperFaceSign);
Assert(BhelperFaceAxis != BtargetFaceAxis);
// Bwaystation = a point of the right type
// that is on both BhelperFace and BtargetFace
// and is as close as possible to B.
// Start by shooting straight from B to BtargetFace...
int Bwaystation[] = Arrays.copy(B);
Bwaystation[BtargetFaceAxis] = Btarget[BtargetFaceAxis];
//PRINT(Bwaystation);
// But if we changed a coordinate
// from zero to nonzero, we destroyed the type...
// to get it back, we need to change some other
// coordinate from nonzero (in fact the same
// absolute value) to zero.
// But be careful not to leave BhelperFace
// when doing this; i.e. don't choose BhelperFaceAxis
// as the axis to zero out.
if (B[BtargetFaceAxis] == 0)
{
int axisToZeroOut = 0;
while (axisToZeroOut == BhelperFaceAxis
|| axisToZeroOut == BtargetFaceAxis
|| Bwaystation[axisToZeroOut] == 0
|| Math.abs(Bwaystation[axisToZeroOut]) != Math.abs(Bwaystation[BtargetFaceAxis]))
axisToZeroOut++;
Bwaystation[axisToZeroOut] = 0;
}
//PRINT(Bwaystation);
solution = Arrays.concat(solution, find_oneface_twist_sequence_taking_these_coords_to_those_coords(BhelperFaceAxis, BhelperFaceSign, new int[][]{B}, new int[][]{Bwaystation}, 1, debugLevel));
B = Bwaystation;
}
// Okay, now B is on BtargetFace...
// twist that face as necessary to move it to Btarget.
solution = Arrays.concat(solution, find_oneface_twist_sequence_taking_these_coords_to_those_coords(BtargetFaceAxis, BtargetFaceSign, new int[][]{B}, new int[][]{Btarget}, 1, debugLevel));
B = Btarget;
}
Assert(Arrays.nIndicesDifferent(A,B) == 1);
Assert(Arrays.normSqrd(A) == Arrays.normSqrd(B));
}
if (C != null)
{
// Apply what we've got so far to C...
for (int i = 0; i < solution.length; ++i)
{
//System.out.print(" "+Arrays.toString(solution[i])+" takes "+Arrays.toString(C)+" to ");
C = PuzzleManipulation.twist90coords(n, solution[i], C);
// System.out.println(Arrays.toString(C));
}
//PRINT(__LINE__);
//PRINT(solution);
//PRINT(A);
//PRINT(B);
//PRINT(C);
Assert(Arrays.nIndicesDifferent(A,B) == 1);
Assert(!Arrays.equals(B,C));
Assert(!Arrays.equals(C,A));
// A and B are good;
// now move C so it's next to B, without perturbing A or B.
// XXX this is very similar to the above, should think about how to combine into one section of code to be cleaner
{
// Goal is to make C differ from B
// in exactly one coordinate axis
// (and that axis can't be the axis in which A and B differ).
int nIndicesDifferent = Arrays.nIndicesDifferent(B,C);
//PRINT(nIndicesDifferent);
Assert(nIndicesDifferent >= 1);
if (nIndicesDifferent > 1)
{
// CtargetFaceAxis = any axis in which B is nonzero
// and equal to A
// (doesn't matter what C is along that axis)
int CtargetFaceAxis = 0;
while (B[CtargetFaceAxis] == 0
|| B[CtargetFaceAxis] != A[CtargetFaceAxis])
CtargetFaceAxis++;
int CtargetFaceSign = (B[CtargetFaceAxis] < 0 ? 1 : -1); // opposite B
int Ctarget[] = Arrays.copy(B);
Ctarget[CtargetFaceAxis] = -B[CtargetFaceAxis];
//PRINT(CtargetFaceAxis);
//PRINT(CtargetFaceSign);
//PRINT(Ctarget);
// Get C onto CtargetFace, if it's not already there...
if (C[CtargetFaceAxis] != Ctarget[CtargetFaceAxis])
{
// ChelperFace = any face that contains C but not B or A
int ChelperFaceAxis = 0;
while (C[ChelperFaceAxis] == 0
|| B[ChelperFaceAxis] == C[ChelperFaceAxis]
|| A[ChelperFaceAxis] == C[ChelperFaceAxis])
ChelperFaceAxis++;
int ChelperFaceSign = (C[ChelperFaceAxis] < 0 ? -1 : 1);
//PRINT(ChelperFaceAxis);
//PRINT(ChelperFaceSign);
Assert(ChelperFaceAxis != CtargetFaceAxis);
// Cwaystation = a point of the right type
// that is on both ChelperFace and CtargetFace
// and is as close as possible to C.
// Start by shooting straight from C to CtargetFace...
int Cwaystation[] = Arrays.copy(C);
Cwaystation[CtargetFaceAxis] = Ctarget[CtargetFaceAxis];
//PRINT(Cwaystation);
// But if we changed a coordinate
// from zero to nonzero, we destroyed the type...
// to get it back, we need to change some other
// coordinate from nonzero (in fact the same
// absolute value) to zero.
// But be careful not to leave ChelperFace
// when doing this; i.e. don't choose ChelperFaceAxis
// as the axis to zero out.
if (C[CtargetFaceAxis] == 0)
{
int axisToZeroOut = 0;
while (axisToZeroOut == ChelperFaceAxis
|| axisToZeroOut == CtargetFaceAxis
|| Cwaystation[axisToZeroOut] == 0
|| Math.abs(Cwaystation[axisToZeroOut]) != Math.abs(Cwaystation[CtargetFaceAxis]))
axisToZeroOut++;
Cwaystation[axisToZeroOut] = 0;
}
//PRINT(Cwaystation);
solution = Arrays.concat(solution, find_oneface_twist_sequence_taking_these_coords_to_those_coords(ChelperFaceAxis, ChelperFaceSign, new int[][]{C}, new int[][]{Cwaystation}, 1, debugLevel));
C = Cwaystation;
}
// Okay, now C is on CtargetFace...
// twist that face as necessary to move it to Ctarget.
solution = Arrays.concat(solution, find_oneface_twist_sequence_taking_these_coords_to_those_coords(CtargetFaceAxis, CtargetFaceSign, new int[][]{C}, new int[][]{Ctarget}, 1, debugLevel));
C = Ctarget;
}
}
//PRINT(__LINE__);
Assert(Arrays.nIndicesDifferent(A,B) == 1);
Assert(Arrays.normSqrd(A) == Arrays.normSqrd(B));
Assert(Arrays.nIndicesDifferent(B,C) == 1);
Assert(Arrays.nIndicesDifferent(C,A) == 2);
Assert(Arrays.normSqrd(B) == Arrays.normSqrd(C));
}
int Lcycle[][] = {
Utils.coordsToIndex(n,A),
Utils.coordsToIndex(n,B),
};
if (C != null)
Lcycle = Arrays.append(Lcycle,
Utils.coordsToIndex(n,C));
if (debugLevel >= 3) System.out.println(" solution = "+Arrays.toString(solution));
if (debugLevel >= 2) System.out.println(" out take_tricycle_to_L_of_"+k+"sticker_cubies");
return new Object[]{solution, Lcycle};
} // take_tricycle_to_L_of_ksticker_cubies
// A 90 degree rotation of the whole puzzle is expressed
// simply as a {fromAxis,toAxis} pair. Return a list of such.
// Throws an exception on failure (i.e. don't do that!),
// unless it's a mirror image and
// returnNullOnIfFailedButIsMirrorImage is true,
// in which case it returns null.
private static int[][] find_rotation_sequence_taking_these_coords_to_those_coords(
int theseCoords[][],
int thoseCoords[][],
boolean returnNullIfFailedButIsMirrorImage,
int debugLevel)
{
if (debugLevel >= 2) System.out.println(" in find_rotation_sequence_taking_these_coords_to_those_coords");
if (debugLevel >= 3) System.out.println(" theseCoords = "+Arrays.toString(theseCoords));
if (debugLevel >= 3) System.out.println(" thoseCoords = "+Arrays.toString(thoseCoords));
int originalTheseCoords[][] = theseCoords;
theseCoords = Arrays.shallowCopy(theseCoords); // so we can modify them
Assert(theseCoords.length == thoseCoords.length);
int nCoords = theseCoords.length;
int d = (nCoords == 0 ? 0 : theseCoords[0].length);
// Simple (though not complete) sanity check on these and those--
// assert they are equal distances from the origin.
for (int i = 0; i < nCoords; ++i)
Assert(Arrays.normSqrd(theseCoords[i])
== Arrays.normSqrd(thoseCoords[i]));
// Keep track of which axes are happy
// and anti-happy...
boolean happy[] = new boolean[d];
boolean antihappy[] = new boolean[d];
for (int i = 0; i < d; ++i)
{
happy[i] = Arrays.columnEquals(theseCoords,i, thoseCoords,i, 1);
antihappy[i] = Arrays.columnEquals(theseCoords,i, thoseCoords,i, -1);
}
int solution[][] = {}; // quadratic time to build by appending repeatedly to an array, but solution length is bounded by bounded by at most d (or so) (I think) so we're it's okay
//
// First pass: get all columns happy-or-antihappy
// using 90 degree rotations (column swaps negating one of them).
//
if (debugLevel >= 4) System.out.println(" first pass");
for (int i = 0; i < d; ++i)
{
if (debugLevel >= 4) System.out.println(" theseCoords = "+Arrays.toString(theseCoords));
if (debugLevel >= 4) System.out.println(" thoseCoords = "+Arrays.toString(thoseCoords));
if (debugLevel >= 4) System.out.println(" happy = "+Arrays.toString(happy));
if (debugLevel >= 4) System.out.println(" antihappy = "+Arrays.toString(antihappy));
//if (debugLevel >= 4) System.out.println(" happy["+i+"] = "+happy[i]+", antihappy["+i+"] = "+antihappy[i]);
if (debugLevel >= 4) System.out.println(" happy["+i+"] = "+happy[i]);
if (debugLevel >= 4) System.out.println(" antihappy["+i+"] = "+antihappy[i]);
// axis permutation is now right for 0..i-1.
if (happy[i] || antihappy[i])
continue;
//
// Get totally happy via a 90 degree rotation
// with some other later neither-happy-nor-antihappy guy.
// First preference is to make the other guy happy in the process.
// Second preference is to just make me happy
// (which will make him a different neither-happy-nor-antihappy).
//
for (int iPicky = 0; iPicky < 2; ++iPicky)
{
boolean picky = (iPicky == 0 ? true : false);
if (debugLevel >= 4) System.out.println(" picky = "+picky);
for (int j = i+1; j < d; ++j)
{
if (happy[j] || antihappy[j])
continue;
if (Arrays.columnEquals(theseCoords,j, thoseCoords,i, 1)
&& (!picky || Arrays.columnEquals(theseCoords,i, thoseCoords,j, -1)))
{
// j->i
if (debugLevel >= 4) System.out.println(" "+j+"->"+i);
solution = Arrays.append(solution, new int[]{j, i});
theseCoords = PuzzleManipulation.rot90coordss(j, i, theseCoords);
happy[i] = true;
antihappy[i] = Arrays.columnEquals(theseCoords,i, thoseCoords,i, -1);
if (picky)
happy[j] = true;
antihappy[j] = Arrays.columnEquals(theseCoords,j, thoseCoords,j, -1);
break;
}
else if (Arrays.columnEquals(theseCoords,j, thoseCoords,i, -1)
&& (!picky || Arrays.columnEquals(theseCoords,i, thoseCoords,j, 1)))
{
// i->j
if (debugLevel >= 4) System.out.println(" "+i+"->"+j);
solution = Arrays.append(solution, new int[]{i, j});
theseCoords = PuzzleManipulation.rot90coordss(i, j, theseCoords);
happy[i] = true;
antihappy[i] = Arrays.columnEquals(theseCoords,i, thoseCoords,i, -1);
if (picky)
happy[j] = true;
antihappy[j] = Arrays.columnEquals(theseCoords,j, thoseCoords,j, -1);
break;
}
}
if (happy[i])
break;
}
// We definitely made i happy (not antihappy)...
if (!happy[i])
throw new Error("theseCoords = "+Arrays.toString(originalTheseCoords)+" can't be rotated to thoseCoords = "+Arrays.toString(thoseCoords));
}
// Second pass: all columns are now happy or antihappy
// (or both, if zero).
// Fix pairs of antihappy-but-not-happy ones
// with 180 degree rotations.
if (debugLevel >= 4) System.out.println(" second pass");
int remainingUnhappyAxis = -1;
for (int i = 0; i < d; ++i)
{
if (happy[i])
continue;
for (int j = i+1; j < d; ++j)
{
if (happy[j])
continue;
// i->j twice
if (debugLevel >= 4) System.out.println(" "+i+"->"+j+" twice");
for (int iTwice = 0; iTwice < 2; ++iTwice)
{
solution = Arrays.append(solution, new int[]{i, j});
theseCoords = PuzzleManipulation.rot90coordss(i, j, theseCoords);
}
happy[i] = true;
antihappy[i] = false;
happy[j] = true;
antihappy[j] = false;
break;
}
if (!happy[i])
remainingUnhappyAxis = i;
}
// Third pass: there is at most one remaining unhappy column,
// and it's antihappy.
// There are three possible tricks for fixing
// this last antihappy-but-not-happy column,
// requiring 1, 2, or 3 moves respectively.
if (remainingUnhappyAxis != -1)
{
if (debugLevel >= 4) System.out.println(" "+remainingUnhappyAxis+" is still not right");
int i = remainingUnhappyAxis;
//
// Trick #1 (1 move):
// Find another column j that's equal or anti-equal
// to the unhappy column i.
// Then the 90-degree rotation i->j or j->i
// makes i happy and keeps j happy.
//
Assert(!happy[i]);
{
if (debugLevel >= 3) System.out.println(" Trying trick #1");
for (int j = 0; j < d; ++j)
{
if (j == i)
continue;
int sign;
if (Arrays.columnEquals(theseCoords,i, theseCoords,j, sign=1)
|| Arrays.columnEquals(theseCoords,i, theseCoords,j, sign=-1))
{
int fromAxis = sign==1 ? i : j;
int toAxis = sign==1 ? j : i;
// fromAxis->toAxis
if (debugLevel >= 4) System.out.println(" "+fromAxis+"->"+toAxis+"");
solution = Arrays.append(solution, new int[]{fromAxis, toAxis});
theseCoords = PuzzleManipulation.rot90coordss(fromAxis, toAxis, theseCoords);
happy[i] = true;
antihappy[i] = false;
break;
}
}
}
//
// Trick #2 (2 moves):
// Find a happy-and-antihappy (i.e. zero) column j
// and do a 180-degree rotation of i,j to make i happy
// while keeping j happy (and antihappy).
//
if (!happy[i])
{
if (debugLevel >= 3) System.out.println(" Trying trick #2");
for (int j = 0; j < d; ++j)
{
if (j == i)
continue;
if (Arrays.columnEquals(theseCoords,j, theseCoords,j, -1))
{
// i->j twice
if (debugLevel >= 4) System.out.println(" "+i+"->"+j+" twice");
for (int iTwice = 0; iTwice < 2; ++iTwice)
{
solution = Arrays.append(solution, new int[]{i, j});
theseCoords = PuzzleManipulation.rot90coordss(i, j, theseCoords);
}
happy[i] = true;
antihappy[i] = false;
break;
}
}
}
//
// Trick #3 (3 moves):
// Find two other columns j,k which are equal
// or anti-equal to each other (and happy of course).
// Rotate j->k, which makes one of j,k antihappy,
// and then 180-degree rotate that now-antihappy one
// with i.
//
if (!happy[i])
{
if (debugLevel >= 3) System.out.println(" Trying trick #3");
for (int j = 0; j < d; ++j)
{
if (j == i)
continue;
for (int k = 0; k < d; ++k)
{
if (k == i || k == j)
continue;
int sign;
if (Arrays.columnEquals(theseCoords,j, theseCoords,k, sign=1)
|| Arrays.columnEquals(theseCoords,j, theseCoords,k, sign=-1))
{
//j->k
if (debugLevel >= 4) System.out.println(" "+j+"->"+k+"");
solution = Arrays.append(solution, new int[]{j, k});
theseCoords = PuzzleManipulation.rot90coordss(j, k, theseCoords);
int otherAntihappyAxis = (sign==1 ? j : k);
//i -> otherAntihappyAxis twice
if (debugLevel >= 4) System.out.println(" "+i+"->"+otherAntihappyAxis+" twice");
for (int iTwice = 0; iTwice < 2; ++iTwice)
{
solution = Arrays.append(solution, new int[]{i, otherAntihappyAxis});
theseCoords = PuzzleManipulation.rot90coordss(i, otherAntihappyAxis, theseCoords);
}
happy[i] = true;
antihappy[i] = false;
break;
}
}
if (happy[i])
break;
}
}
if (!happy[i])
{
// All the tricks for reversing this axis failed--
// it's inside out.
if (returnNullIfFailedButIsMirrorImage)
{
if (debugLevel >= 2) System.out.println(" out find_rotation_sequence_taking_these_coords_to_those_coords (returning null because it's inside out)");
return null;
}
else
throw new Error("theseCoords = "+Arrays.toString(originalTheseCoords)+" can't be rotated to thoseCoords = "+Arrays.toString(thoseCoords)+" (inside out!)");
}
}
// Assert that we kept track of happy and antihappy right
// and that everyone is now happy...
for (int i = 0; i < d; ++i)
{
Assert(happy[i] == Arrays.columnEquals(theseCoords,i, thoseCoords,i, 1));
Assert(antihappy[i] == Arrays.columnEquals(theseCoords,i, thoseCoords,i, -1));
Assert(happy[i]);
}
if (debugLevel >= 3) System.out.println(" solution = "+Arrays.toString(solution));
//
// Assert that solution applied to originalTheseCoords
// are in fact thoseCoords (i.e. that we did
// what we were contracted to do)...
//
for (int iThese = 0; iThese < theseCoords.length; ++iThese)
Assert(Arrays.equals(PuzzleManipulation.rot90sCoords(solution, originalTheseCoords[iThese]),
thoseCoords[iThese]));
if (debugLevel >= 2) System.out.println(" out find_rotation_sequence_taking_these_coords_to_those_coords");
return solution;
} // find_rotation_sequence_taking_these_coords_to_those_coords
// Finds a sequence of twists of a single face
// that take these coords to those coords.
// This is accomplished by using the generic rot function
// on the original constraints with one more constraint added:
// don't move the face center.
// Note, we do NOT sanity-check whether the coords in question
// are actually within slicesMask
//
private static int[][] find_oneface_twist_sequence_taking_these_coords_to_those_coords(
int faceAxis, int faceSign,
int theseCoords[][],
int thoseCoords[][],
int slicesMask,
int debugLevel)
{
//System.out.println(" in find_oneface_twist_sequence_taking_these_coords_to_those_coords");
//PRINT(faceAxis);
//PRINT(faceSign);
//PRINT(theseCoords);
//PRINT(thoseCoords);
//PRINT(slicesMask);
if (theseCoords.length == 0) return new int[0][5]; // protects the d calculation
int d = theseCoords[0].length;
int faceCenter[] = Arrays.repeat(0, d);
faceCenter[faceAxis] = faceSign; // actually not necessarily the face center but it's in the right direction which is what matters
int theseCoordsAndFaceCenter[][] =
Arrays.append(theseCoords, faceCenter);
int thoseCoordsAndFaceCenter[][] =
Arrays.append(thoseCoords, faceCenter);
int rots[][] = find_rotation_sequence_taking_these_coords_to_those_coords(
theseCoordsAndFaceCenter,
thoseCoordsAndFaceCenter,
false,
debugLevel);
int twists[][] = new int[rots.length][];
for (int i = 0; i < rots.length; ++i)
twists[i] = new int[] {faceAxis, faceSign, rots[i][0], rots[i][1],slicesMask};
//PRINT(twists);
//System.out.println(" out find_oneface_twist_sequence_taking_these_coords_to_those_coords");
return twists;
} // find_oneface_twist_sequence_taking_these_coords_to_those_coords
//
// Assuming the k-sticker cubies are positioned correctly,
// find a sequence of moves that orients them correctly,
// without messing up the fewer-sticker cubies,
// but freely messing up the more-sticker cubies.
//
private static java.util.ArrayList orient_ksticker_cubies(int k, int n, int d, Object puzzleIndices, int debugLevel)
{
if (debugLevel >= 1) System.out.println(" in orient_"+k+"sticker_cubies");
java.util.ArrayList solution = new java.util.ArrayList();
//
// Decompose the permutation on the k-sticker cubie stickers
// into cycles, omitting cycles of length 1.
//
java.util.ArrayList cyclesArrayList = new java.util.ArrayList();
Object scratch = Arrays.repeat(new Object(), n+2, d); // set entries in scratch to null as we've seen them during position parity checking
int nIndices = Arrays.intpow(n+2,d);
for (int iIndex = 0; iIndex < nIndices; ++iIndex)
{
int index[] = Arrays.unFlatIndex(iIndex,n+2,d);
// It's a sticker of a k-sticker cubie
// iff it's a sticker index (i.e. it's 0 or n+1 in exactly 1 axis)
// and <=1 or >=n in exactly k axis directions.
int hist[] = Utils.histogram(n+2,index);
boolean isKStickerCubieSticker = (hist[0]+hist[n+1] == 1
&& hist[0]+hist[1]+hist[n]+hist[n+1] == k);
if (isKStickerCubieSticker)
{
int cycle[][] = {}; // quadratic time to build by appending repeatedly to an array, but grows to at most d so it's fine
while (Arrays.get(scratch,index) != null)
{
cycle = Arrays.append(cycle,index);
Arrays.set(scratch,index,null);
index = (int[])Arrays.get(puzzleIndices,index);
}
if (cycle.length > 1) // omit cycles of length 1
cyclesArrayList.add(cycle);
}
}
int cycles[][][] = (int[][][])cyclesArrayList.toArray(new int[0][][]); // gross!
if (debugLevel >= 2) System.out.println(" cycles="+Arrays.toString(cycles));
// Assert that each cycle stayed within a single cubie...
for (int i = 0; i < cycles.length; ++i)
for (int j = 1; j < cycles[i].length; ++j)
Assert(Utils.areOnSameCubie(n,cycles[i][j],
cycles[i][0]));
//
// The primitives we will use for orienting are;
// For corners:
// twirl (i.e. cycle 3 stickers on) two corner cubies
// in opposite directions
// (although for d>=5 twirls of corners don't have a sign, so the
// "in opposite directions" clause is only meaningful
// for d==3 and d==4)
// For non-corners:
// flip (i.e. swap 2 stickers on) two non-corner cubies
// So grind up the cycles until they are of the appropriate
// form, depending on whether we are working on corners or not.
//
if (k < d) // non-corners
{
// Need all sticker cycles to occur
// in pairs of flips (a b) (c d)
// where stickers a,b are on one (non-corner) cubie
// and stickers c,d are on a different one.
java.util.ArrayList flipPairs = new java.util.ArrayList(); // int flipPairs[][/*2*/][/*2*/][/*d*/];
int happyHelperFlip[][] = null;
for (int iCycle = 0; iCycle < cycles.length; ++iCycle)
{
int cycle[][] = cycles[iCycle];
int cubieCenter[] = Arrays.clamp(cycle[0],1,n);
while (cycle.length != 1)
{
if (happyHelperFlip != null)
{
// Extract one swap from cycle
// and pair it with happyHelperFlip.
// Before: (a b c d e)
// After: (a b) (a c d e)
flipPairs.add(new int[][][] {{cycle[0],cycle[1]}, happyHelperFlip});
cycle = Arrays.delete(cycle,1);
}
else
{
// Try to find a helper cycle, that is,
// a cycle that needs to be done that's
// on some other cubie.
// If there is none, then we will have to
// recruit some happy other cubie as a helper
// and mess it up temporarily.
int iHelperCycle = -1;
for (int iHelperCycleMaybe = iCycle+1;
iHelperCycleMaybe < cycles.length;
iHelperCycleMaybe++)
{
if (cycles[iHelperCycleMaybe].length == 1)
continue; // it's tired of helping
if (!Utils.areOnSameCubie(n,cycles[iHelperCycleMaybe][0],
cycle[0]))
{
iHelperCycle = iHelperCycleMaybe;
break;
}
}
if (iHelperCycle != -1)
{
int helperCycle[][] = cycles[iHelperCycle];
// Extract one swap from cycle
// and one swap from helpercycle.
// Before: (a b c d e) (f g h i j)
// After: (a b) (f g) (a c d e) (f h i j)
flipPairs.add(new int[][][] {
{cycle[0],cycle[1]},
{helperCycle[0],helperCycle[1]},
});
cycle = Arrays.delete(cycle,1);
helperCycle = Arrays.delete(helperCycle,1);
cycles[iHelperCycle] = helperCycle;
}
else
{
// There was no other cycle to help;
// need to take a happy cubie
// and create a flip on it temporarily.
// If this happens, it means this cycle
// and ALL other remaining cycles
// are on the same single cubie,
// so we choose some other flip
// on some other cubie,
// call it the happyHelperFlip,
// and use it for all the rest of the cycles.
//
// We arbitrarily choose the cubie of
// happyHelperFlip to be any cubie of
// the same type as this cubie.
// We find such a cubie by rotating cubieCenter
// using fromAxis,toAxis directions
// such that cubieCenter is nonzero
// in at least one of the two axes
// (so that we don't rotate it to itself).
//
int fromAxis = 0, toAxis = 1;
while (cubieCenter[fromAxis] == 0 && cubieCenter[toAxis] == 0)
toAxis++;
// Actually we don't even need to know the happy helper cubie's center,
// we just need two stickers on it... so use
// the rotated images of the first two stickers on cycle. Simple!
happyHelperFlip = new int[][] {
PuzzleManipulation.rot90index(n,fromAxis,toAxis,cycle[0]),
PuzzleManipulation.rot90index(n,fromAxis,toAxis,cycle[1]),
};
// Now when we get back to the top of the loop
// we will hit the happyHelperFlip!=null case
// and be able to proceed.
} // if there was no other cycle to help
} // if happyHelperFlip was null beforehand
} // while cycle.length != 1
} // for iCycle
if (debugLevel >= 2) System.out.println(" flipPairs="+Arrays.toString(flipPairs));
int nFlipPairs = flipPairs.size();
for (int i = 0; i < nFlipPairs; ++i)
{
int flipPair[][][] = (int[][][])flipPairs.get(i);
int A[][] = (int[][])Utils.indexsToCoordss(n,flipPair[0]);
int B[][] = (int[][])Utils.indexsToCoordss(n,flipPair[1]);
solution.addAll(flip_two_noncorner_cubies_COORDS(k, n, d,
A, B,
debugLevel));
}
} // non-corners case
else // k == d, i.e. corners case
{
Assert(k == d);
// Need all sticker cycles to occur
// in pairs of twirls (a b c) (d e f)
// where stickers a,b,c are on one (corner) cubie
// and stickers d,e,f are on a different one.
// Furthermore if d == 3 or 4, then (a b c) and (d e f)
// must be in opposite directions (a meaningless concept when d >= 5).
// Even-length cycles are a pain in the ass here,
// so get rid of them by doing a first pass
// in which we replace pairs of even-length cycles
// on the same cubie with an equivalent pair of odd-length cycles
// (which means the cycles will no longer be disjoint
// after this pass).
// (I don't think we could have done the same thing
// back in the positioning code where I went through contortions to deal with 2-cycles when trying to make 3-cycles-- because in that case the cycles not being disjoint could really mess us up when we look for helpers later (see "subtlety" below))
for (int iCycle = 0; iCycle < cycles.length; ++iCycle)
{
if (cycles[iCycle].length % 2 == 0) // if this one's even
for (int jCycle = iCycle+1; jCycle < cycles.length; ++jCycle)
if (cycles[jCycle].length % 2 == 0 // if that one's even
&& Utils.areOnSameCubie(n,cycles[iCycle][0],
cycles[jCycle][0]))
{
// Before: (a b c d) (e f g h i j)
// After: (a b c d e) (e a f g h i j)
// in particular:
// Before: (a b) (c d e f)
// After: (a b c) (c a d e f)
cycles[iCycle] = Arrays.append(cycles[iCycle],
cycles[jCycle][0]);
cycles[jCycle] = Arrays.insert(cycles[jCycle], 1,
cycles[iCycle][0]);
break;
}
Assert(cycles[iCycle].length % 2 == 1);
}
java.util.ArrayList twirlPairs = new java.util.ArrayList(); // int twirlPairs[][/*2*/][/*2*/][/*d*/];
int happyHelperTwirl[][] = null;
int happyHelperUnTwirl[][] = null;
int timesHappyHelperTwirlHelped = 0;
for (int iCycle = 0; iCycle < cycles.length; ++iCycle)
{
int cycle[][] = cycles[iCycle];
int cubieCenter[] = Arrays.clamp(cycle[0],1,n);
while (cycle.length != 1)
{
Assert(cycle.length >= 3);
if (happyHelperTwirl != null)
{
// Extract one twirl from cycle
// and pair it with happyHelperTwirl
// either forwards or backwards,
// whichever is in the opposite direction
// from the extracted twirl.
//
// If d >= 5 then it doesn't matter;
// there is no concept of twirl direction,
// since any 3 stickers on one cubie
// can always be rotated to any 3 stickers
// on any other cubie of the same type.
// But we check anyway for sanity.
//
int abc[][] = {cycle[0],cycle[1],cycle[2]};
boolean cycleIsSameOrientationAsHappyHelperTwirl = (find_rotation_sequence_taking_these_coords_to_those_coords((int[][])Utils.indexsToCoordss(n,abc), (int[][])Utils.indexsToCoordss(n,happyHelperTwirl), true, debugLevel) != null);
boolean cycleIsSameOrientationAsHappyHelperUnTwirl = (find_rotation_sequence_taking_these_coords_to_those_coords((int[][])Utils.indexsToCoordss(n,abc), (int[][])Utils.indexsToCoordss(n,happyHelperUnTwirl), true, debugLevel) != null);
if (d == 3 || d == 4)
{
// One way works and the other doesn't
Assert(cycleIsSameOrientationAsHappyHelperTwirl
!= cycleIsSameOrientationAsHappyHelperUnTwirl);
}
else // d >= 5, so the rotation should always succeed
{
// Both ways work.
Assert(cycleIsSameOrientationAsHappyHelperTwirl
&& cycleIsSameOrientationAsHappyHelperUnTwirl);
}
int happyHelperTwirlOrUnTwirl[][];
if (cycleIsSameOrientationAsHappyHelperTwirl)
{
happyHelperTwirlOrUnTwirl = happyHelperUnTwirl;
timesHappyHelperTwirlHelped--;
}
else
{
happyHelperTwirlOrUnTwirl = happyHelperTwirl;
timesHappyHelperTwirlHelped++;
}
twirlPairs.add(new int[][][] {
{cycle[0],cycle[1],cycle[2]},
happyHelperTwirlOrUnTwirl,
});
// (a b c d e f g) -> (a b c) (a d e f g)
cycle = Arrays.deleteRange(cycle, 1, 2);
}
else
{
// Try to find a helper cycle, that is,
// a cycle that needs to be done that's
// on some other cubie.
// If there is none, then we will have to
// recruit some happy other cubie as a helper
// and mess it up temporarily.
int iHelperCycle = -1;
for (int iHelperCycleMaybe = iCycle+1;
iHelperCycleMaybe < cycles.length;
iHelperCycleMaybe++)
{
if (cycles[iHelperCycleMaybe].length == 1)
continue; // it's tired of helping
if (!Utils.areOnSameCubie(n,cycles[iHelperCycleMaybe][0],
cycle[0]))
{
iHelperCycle = iHelperCycleMaybe;
break;
}
}
if (iHelperCycle != -1)
{
// Extract one twirl from cycle
// and one anti-twirl from helpercycle.
// this might end up simply reversing helpercycle,
// which is sort of lame (if we
// were being ambitious, we should really
// try to get a helper that we actually
// help in the process of being helped, instead),
// but whatever.
int helperCycle[][] = cycles[iHelperCycle];
// Extract one twirl from cycle
// and one anti-twirl from helpercycle.
// This will be one of the following two cases,
// depending on whether (h i j) is a twirl
// or an anti-twirl with respect to (a b c):
//
// Case 1: (a b c) is opposite (h i j)
// Before: (a b c d e f g) (h i j k l m n)
// After: (a b c) (a d e f g) (h i j) (h k l m n)
// Case 2: (a b c) is opposite (j i h)
// Before: (a b c d e f g) (h i j k l m n)
// After: (a b c) (a d e f g) (j i h) (h j i k l m n)
//
// Subtlety: can't it be the case that
// cycle and helpercycle are not disjoint,
// due to the first pass where we mingled
// even cycles to form odd ones?
// NO-- we only mingled within a cubie,
// whereas cycle and helperCycle are on different
// cubies (phew!)
// Check the orientation
// of the twirls-- we always need to pair
// with a twirl of the opposite direction.
// See the comments above for an explanation
// of this, where we did the same thing
// for happyHelperCycle.
int abc[][] = {cycle[0],cycle[1],cycle[2]};
int hij[][] = {helperCycle[0],helperCycle[1],helperCycle[2]};
int jih[][] = {helperCycle[2],helperCycle[1],helperCycle[0]};
boolean abc_isSameOrientationAs_hij = (find_rotation_sequence_taking_these_coords_to_those_coords((int[][])Utils.indexsToCoordss(n,abc), (int[][])Utils.indexsToCoordss(n,hij), true, debugLevel) != null);
boolean abc_isSameOrientationAs_jih = (find_rotation_sequence_taking_these_coords_to_those_coords((int[][])Utils.indexsToCoordss(n,abc), (int[][])Utils.indexsToCoordss(n,jih), true, debugLevel) != null);
if (d == 3 || d == 4)
{
// One way works and the other doesn't
Assert(abc_isSameOrientationAs_hij
!= abc_isSameOrientationAs_jih);
}
else // d >= 5, so the rotation should always succeed
{
// Both ways work.
Assert(abc_isSameOrientationAs_hij
&& abc_isSameOrientationAs_jih);
}
if (abc_isSameOrientationAs_jih)
{
// case 1 as described above:
// Before: (a b c d e f g) (h i j k l m n)
// After: (a b c) (a d e f g) (h i j) (h k l m n)
twirlPairs.add(new int[][][] {abc, hij});
cycle = Arrays.deleteRange(cycle, 1,2);
helperCycle = Arrays.deleteRange(helperCycle, 1,2);
}
else
{
// case 2 as described above:
// Before: (a b c d e f g) (h i j k l m n)
// After: (a b c) (a d e f g) (j i h) (h j i k l m n)
twirlPairs.add(new int[][][] {abc, jih});
cycle = Arrays.deleteRange(cycle, 1,2);
// just swap helperCycle[1] and helperCycle[2] in place (it's not shared)
int temp[] = helperCycle[1];
helperCycle[1] = helperCycle[2];
helperCycle[2] = temp;
}
cycles[iHelperCycle] = helperCycle;
}
else
{
// There was no other cycle to help;
// need to take a happy cubie
// and create a twirl on it temporarily.
// If this happens, it means this cycle
// and ALL other remaining cycles
// are on the same single cubie,
// so we choose some other twirl
// on some other cubie,
// call it the happyHelperTwirl,
// and use it for all the rest of the cycles.
//
// We arbitrarily choose the cubie of
// happyHelperTwirl to be any cubie of
// the same type as this cubie.
// We find such a cubie by rotating cubieCenter
// using fromAxis,toAxis directions
// such that cubieCenter is nonzero
// in at least one of the two axes
// (so that we don't rotate it to itself).
int fromAxis = 0, toAxis = 1;
while (cubieCenter[fromAxis] == 0 && cubieCenter[toAxis] == 0)
toAxis++;
// Actually we don't even need to know the happy helper cubie's center,
// we just need two stickers on it... so use
// the rotated images of the first three stickers on cycle. Simple!
happyHelperTwirl = new int[][] {
PuzzleManipulation.rot90index(n,fromAxis,toAxis,cycle[0]),
PuzzleManipulation.rot90index(n,fromAxis,toAxis,cycle[1]),
PuzzleManipulation.rot90index(n,fromAxis,toAxis,cycle[2]),
};
happyHelperUnTwirl = new int[][] {
happyHelperTwirl[2],
happyHelperTwirl[1],
happyHelperTwirl[0],
};
// Now when we get back to the top of the loop
// we will hit the happyHelperTwirl!=null case
// and be able to proceed.
} // if there was no other cycle to help
} // if happyHelperTwirl was null beforehand
} // while cycle.length != 1
} // for iCycle
//
// If d>=5, it may now be the case
// that we used happyHelperTwirl
// a nonzero-mod-3 number of times,
// in which case we now need to fix it.