Magic Cube

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

// Copyright 2008 Leszek Koltunski                                                               //

//                                                                                               //

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

//                                                                                               //

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

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

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

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

//                                                                                               //

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

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

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

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

//                                                                                               //

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

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

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

package org.distorted.solvers.cube3;

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

class SolverCubieCube

  {

  private static final int[][] cnk     = new int[12][7];

  private static final int[] tmpEdge6  = new int[6];

  private static final int[] tmpEdge4  = new int[4];

  private static final int[] tmpEdge3  = new int[3];

  private static final int[] tmpCorner6= new int[6];

  // corner permutation

  int[] cp = { SolverCorner.URF, SolverCorner.UFL, SolverCorner.ULB, SolverCorner.UBR, SolverCorner.DFR, SolverCorner.DLF, SolverCorner.DBL, SolverCorner.DRB };

  // corner orientation

  byte[] co = { 0, 0, 0, 0, 0, 0, 0, 0 };

  // edge permutation

  int[] ep = { SolverEdge.UR, SolverEdge.UF, SolverEdge.UL, SolverEdge.UB, SolverEdge.DR, SolverEdge.DF, SolverEdge.DL, SolverEdge.DB, SolverEdge.FR, SolverEdge.FL, SolverEdge.BL, SolverEdge.BR };

  // edge orientation

  byte[] eo = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

  // Moves on the cubie level

  private static final int[]  cpU = { SolverCorner.UBR, SolverCorner.URF, SolverCorner.UFL, SolverCorner.ULB, SolverCorner.DFR, SolverCorner.DLF, SolverCorner.DBL, SolverCorner.DRB };

  private static final byte[] coU = { 0, 0, 0, 0, 0, 0, 0, 0 };

  private static final int[]  epU = { SolverEdge.UB, SolverEdge.UR, SolverEdge.UF, SolverEdge.UL, SolverEdge.DR, SolverEdge.DF, SolverEdge.DL, SolverEdge.DB, SolverEdge.FR, SolverEdge.FL, SolverEdge.BL, SolverEdge.BR };

  private static final byte[] eoU = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

  private static final int[]  cpR = { SolverCorner.DFR, SolverCorner.UFL, SolverCorner.ULB, SolverCorner.URF, SolverCorner.DRB, SolverCorner.DLF, SolverCorner.DBL, SolverCorner.UBR };

  private static final byte[] coR = { 2, 0, 0, 1, 1, 0, 0, 2 };

  private static final int[]  epR = { SolverEdge.FR, SolverEdge.UF, SolverEdge.UL, SolverEdge.UB, SolverEdge.BR, SolverEdge.DF, SolverEdge.DL, SolverEdge.DB, SolverEdge.DR, SolverEdge.FL, SolverEdge.BL, SolverEdge.UR };

  private static final byte[] eoR = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

  private static final int[]  cpF = { SolverCorner.UFL, SolverCorner.DLF, SolverCorner.ULB, SolverCorner.UBR, SolverCorner.URF, SolverCorner.DFR, SolverCorner.DBL, SolverCorner.DRB };

  private static final byte[] coF = { 1, 2, 0, 0, 2, 1, 0, 0 };

  private static final int[]  epF = { SolverEdge.UR, SolverEdge.FL, SolverEdge.UL, SolverEdge.UB, SolverEdge.DR, SolverEdge.FR, SolverEdge.DL, SolverEdge.DB, SolverEdge.UF, SolverEdge.DF, SolverEdge.BL, SolverEdge.BR };

  private static final byte[] eoF = { 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0 };

  private static final int[]  cpD = { SolverCorner.URF, SolverCorner.UFL, SolverCorner.ULB, SolverCorner.UBR, SolverCorner.DLF, SolverCorner.DBL, SolverCorner.DRB, SolverCorner.DFR };

  private static final byte[] coD = { 0, 0, 0, 0, 0, 0, 0, 0 };

  private static final int[]  epD = { SolverEdge.UR, SolverEdge.UF, SolverEdge.UL, SolverEdge.UB, SolverEdge.DF, SolverEdge.DL, SolverEdge.DB, SolverEdge.DR, SolverEdge.FR, SolverEdge.FL, SolverEdge.BL, SolverEdge.BR };

  private static final byte[] eoD = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

  private static final int[]  cpL = { SolverCorner.URF, SolverCorner.ULB, SolverCorner.DBL, SolverCorner.UBR, SolverCorner.DFR, SolverCorner.UFL, SolverCorner.DLF, SolverCorner.DRB };

  private static final byte[] coL = { 0, 1, 2, 0, 0, 2, 1, 0 };

  private static final int[]  epL = { SolverEdge.UR, SolverEdge.UF, SolverEdge.BL, SolverEdge.UB, SolverEdge.DR, SolverEdge.DF, SolverEdge.FL, SolverEdge.DB, SolverEdge.FR, SolverEdge.UL, SolverEdge.DL, SolverEdge.BR };

  private static final byte[] eoL = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

  private static final int[]  cpB = { SolverCorner.URF, SolverCorner.UFL, SolverCorner.UBR, SolverCorner.DRB, SolverCorner.DFR, SolverCorner.DLF, SolverCorner.ULB, SolverCorner.DBL };

  private static final byte[] coB = { 0, 0, 1, 2, 0, 0, 2, 1 };

  private static final int[]  epB = { SolverEdge.UR, SolverEdge.UF, SolverEdge.UL, SolverEdge.BR, SolverEdge.DR, SolverEdge.DF, SolverEdge.DL, SolverEdge.BL, SolverEdge.FR, SolverEdge.FL, SolverEdge.UB, SolverEdge.DB };

  private static final byte[] eoB = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1 };

  // this CubieCube array represents the 6 basic cube moves

  static SolverCubieCube[] moveCube = new SolverCubieCube[6];

  static

    {

    moveCube[0] = new SolverCubieCube();

    moveCube[0].cp = cpU;

    moveCube[0].co = coU;

    moveCube[0].ep = epU;

    moveCube[0].eo = eoU;

    moveCube[1] = new SolverCubieCube();

    moveCube[1].cp = cpR;

    moveCube[1].co = coR;

    moveCube[1].ep = epR;

    moveCube[1].eo = eoR;

    moveCube[2] = new SolverCubieCube();

    moveCube[2].cp = cpF;

    moveCube[2].co = coF;

    moveCube[2].ep = epF;

    moveCube[2].eo = eoF;

    moveCube[3] = new SolverCubieCube();

    moveCube[3].cp = cpD;

    moveCube[3].co = coD;

    moveCube[3].ep = epD;

    moveCube[3].eo = eoD;

    moveCube[4] = new SolverCubieCube();

    moveCube[4].cp = cpL;

    moveCube[4].co = coL;

    moveCube[4].ep = epL;

    moveCube[4].eo = eoL;

    moveCube[5] = new SolverCubieCube();

    moveCube[5].cp = cpB;

    moveCube[5].co = coB;

    moveCube[5].ep = epB;

    moveCube[5].eo = eoB;

    }

  static

    {

    for(int n=0; n<12; n++)

      for(int k=0; k<7; k++)

	      cnk[n][k] = -1;

    }

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

  SolverCubieCube()

    {

    }

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

// n choose k

  static int Cnk(int n, int k)

    {

    if( cnk[n][k]<0 )

      {

      int i, j, s;

      if (k > n  ) { cnk[n][k]=0; return 0; }

      if (k > n/2) k = n-k;

      for(s=1, i=n, j=1; i!=n-k; i--, j++)

        {

	      s *= i;

	      s /= j;

        }

      cnk[n][k]= s;

      }

    return cnk[n][k];

    }

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

// Left rotation of all array elements between 0 and r

  static void rotateLeft(int[] arr, int r)

    {

    int tmp = arr[0];

    for (int i=0; i<r; i++) arr[i] = arr[i + 1];

    arr[r] = tmp;

    }

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

// Right rotation of all array elements between l and r

  static void rotateRight(int[] arr, int r)

    {

    int tmp = arr[r];

    for (int i = r; i > 0; i--) arr[i] = arr[i - 1];

    arr[0] = tmp;

    }

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

// return cube in facelet representation

  SolverFaceCube toFaceCube()

    {

    SolverFaceCube fcRet = new SolverFaceCube();

    for(int c = SolverCorner.URF; c<= SolverCorner.DRB; c++)

      {

      int j = cp[c];   // corner cubie with index j is at corner position with index i

      byte ori = co[c];// orientation of this cubie

      for( int n=0; n<3; n++)

        fcRet.f[SolverFaceCube.cornerFacelet[c][(n + ori) % 3]] = SolverFaceCube.cornerColor[j][n];

      }

    for(int e = SolverEdge.UR; e<= SolverEdge.BR; e++)

      {

      int j = ep[e];   // edge cubie with index j is at edge position with index i

      byte ori = eo[e];// orientation of this cubie

      for( int n=0; n<2; n++)

	      fcRet.f[SolverFaceCube.edgeFacelet[e][(n + ori) % 2]] = SolverFaceCube.edgeColor[j][n];

      }

    return fcRet;

    }

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

// return the twist of the 8 corners. 0 <= twist < 3^7

  short getTwist()

    {

    short ret = 0;

    for(int i = SolverCorner.URF; i< SolverCorner.DRB; i++)

      ret = (short) (3*ret+co[i]);

    return ret;

    }

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

  void setTwist(short twist)

    {

    int twistParity = 0;

    for (int i = SolverCorner.DRB-1; i>= SolverCorner.URF; i--)

      {

      twistParity += co[i] = (byte) (twist%3);

      twist /= 3;

      }

    co[SolverCorner.DRB] = (byte) ((3 - twistParity % 3) % 3);

    }

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

// return the flip of the 12 edges. 0<= flip < 2^11

  short getFlip()

    {

    short ret = 0;

    for (int i = SolverEdge.UR; i< SolverEdge.BR; i++)

      ret = (short) (2 * ret + eo[i]);

    return ret;

    }

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

  void setFlip(short flip)

    {

    int flipParity = 0;

    for (int i = SolverEdge.BR-1; i>= SolverEdge.UR; i--)

      {

      flipParity += eo[i] = (byte) (flip % 2);

      flip /= 2;

      }

    eo[SolverEdge.BR] = (byte) ((2 - flipParity % 2) % 2);

    }

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

// Parity of the corner permutation

  short cornerParity()

    {

    int s = 0;

    for (int i = SolverCorner.DRB; i>= SolverCorner.URF+1; i--)

      for (int j = i - 1; j >= SolverCorner.URF; j--)

        if (cp[j] > cp[i]) s++;

    return (short) (s%2);

    }

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

// Parity of the edges permutation. Parity of corners and edges are the same if the cube is solvable.

  short edgeParity()

    {

    int s = 0;

    for (int i = SolverEdge.BR; i >= SolverEdge.UR+1; i--)

      for (int j = i - 1; j >= SolverEdge.UR; j--)

        if (ep[j] > ep[i]) s++;

    return (short) (s%2);

    }

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

// permutation of the UD-slice edges FR,FL,BL and BR

  short getFRtoBR()

    {

    int a = 0, x = 0;

    // compute the index a < (12 choose 4) and the permutation array perm.

    for(int j = SolverEdge.BR; j >= SolverEdge.UR; j--)

      if (SolverEdge.FR <= ep[j] && ep[j] <= SolverEdge.BR)

        {

        a += Cnk(11-j, x+1);

	      tmpEdge4[3-x++] = ep[j];

	      }

    int b = 0;

    for( int j=3; j>0; j--) // compute the index b < 4! for the permutation in perm

      {

      int k = 0;

      while (tmpEdge4[j] != j+8)

        {

	      rotateLeft(tmpEdge4,j);

	      k++;

        }

      b = (j+1)*b + k;

      }

    return (short) (24*a+b);

    }

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

// Permutation of all corners except DBL and DRB

  short getURFtoDLF()

    {

    int a = 0, x = 0;

    // compute the index a < (8 choose 6) and the corner permutation.

    for(int j = SolverCorner.URF; j<= SolverCorner.DRB; j++)

      if( cp[j] <= SolverCorner.DLF )

        {

	      a += Cnk(j, x+1);

	      tmpCorner6[x++] = cp[j];

	      }

    int b = 0;

    for( int j=5; j>0; j--) // compute the index b < 6! for the permutation in corner6

      {

      int k = 0;

      while (tmpCorner6[j] != j)

        {

	      rotateLeft(tmpCorner6,j);

	      k++;

	      }

      b = (j+1)*b + k;

      }

    return (short) (720*a+b);

    }

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

// Permutation of the six edges UR,UF,UL,UB,DR,DF.

  int getURtoDF()

    {

    int a = 0, x = 0;

    // compute the index a < (12 choose 6) and the edge permutation.

    for(int j = SolverEdge.UR; j<= SolverEdge.BR; j++)

      if (ep[j] <= SolverEdge.DF)

        {

	      a += Cnk(j, x+1);

	      tmpEdge6[x++] = ep[j];

	      }

    int b = 0;

    for (int j=5; j>0; j--)// compute the index b < 6! for the permutation in edge6

      {

      int k = 0;

      while (tmpEdge6[j] != j)

        {

	      rotateLeft(tmpEdge6,j);

	      k++;

	      }

      b = (j+1)*b + k;

      }

    return 720*a+b;

    }

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

// Permutation of the three edges UR,UF,UL

  short getURtoUL()

    {

    int a=0, x=0;

    // compute the index a < (12 choose 3) and the edge permutation.

    for(int j = SolverEdge.UR; j<= SolverEdge.BR; j++)

      if (ep[j] <= SolverEdge.UL)

        {

	      a += Cnk(j, x + 1);

	      tmpEdge3[x++] = ep[j];

	      }

    int b=0;

    for( int j=2; j>0; j--)// compute the index b < 3! for the permutation in edge3

      {

      int k = 0;

      while (tmpEdge3[j] != j)

        {

	      rotateLeft(tmpEdge3,j);

	      k++;

	      }

      b = (j+1)*b+k;

      }

    return (short) (6*a+b);

    }

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

// Permutation of the three edges UB,DR,DF

  short getUBtoDF()

    {

    int a=0, x=0;

    // compute the index a < (12 choose 3) and the edge permutation.

    for(int j = SolverEdge.UR; j<= SolverEdge.BR; j++)

      if (SolverEdge.UB <= ep[j] && ep[j] <= SolverEdge.DF)

        {

	      a += Cnk(j, x+1);

	      tmpEdge3[x++] = ep[j];

	      }

    int b=0;

    for (int j=2; j>0; j--) // compute the index b < 3! for the permutation in edge3

      {

      int k=0;

      while (tmpEdge3[j] != SolverEdge.UB + j)

        {

	      rotateLeft(tmpEdge3,j);

	      k++;

	      }

      b = (j+1)*b+k;

      }

    return (short) (6*a+b);

    }

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

  void setURFtoDLB(int idx)

    {

    int[] perm = { SolverCorner.URF, SolverCorner.UFL, SolverCorner.ULB, SolverCorner.UBR, SolverCorner.DFR, SolverCorner.DLF, SolverCorner.DBL, SolverCorner.DRB };

    int k;

    for( int j=1; j<8; j++)

      {

      k = idx % (j+1);

      idx /= j+1;

      while (k-- > 0) rotateRight(perm,j);

      }

    int x=7;// set corners

    for( int j=7; j>=0; j--) cp[j] = perm[x--];

    }

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

  void setURtoBR(int idx)

    {

    int[] perm = { SolverEdge.UR, SolverEdge.UF, SolverEdge.UL, SolverEdge.UB, SolverEdge.DR, SolverEdge.DF, SolverEdge.DL, SolverEdge.DB, SolverEdge.FR, SolverEdge.FL, SolverEdge.BL, SolverEdge.BR };

    int k;

    for( int j=1; j<12; j++)

      {

      k = idx % (j+1);

      idx /= j+1;

      while (k-- > 0) rotateRight(perm,j);

      }

    int x=11;// set edges

    for( int j=11; j>=0; j--) ep[j] = perm[x--];

    }

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

// Check a cubie cube for solvability. Return the error code.

// 0: Cube is solvable

// -2: Not all 12 edges exist exactly once

// -3: Flip error: One edge has to be flipped

// -4: Not all corners exist exactly once

// -5: Twist error: One corner has to be twisted

// -6: Parity error: Two corners ore two edges have to be exchanged

  int verify()

    {

    int sum = 0;

    int[] edgeCount = new int[12];

    for (int e = SolverEdge.UR; e <= SolverEdge.BR; e++) edgeCount[ep[e]]++;

    for( int i=0; i<12; i++)

      if (edgeCount[i] != 1) return -2;

    for( int i=0; i<12; i++) sum += eo[i];

    if( (sum%2) != 0) return -3;

    int[] cornerCount = new int[8];

    for(int c = SolverCorner.URF; c<= SolverCorner.DRB; c++) cornerCount[cp[c]]++;

    for (int i = 0; i < 8; i++)

      if (cornerCount[i] != 1) return -4;// missing corners

    sum = 0;

    for( int i=0; i<8; i++) sum += co[i];

    if( (sum%3) != 0) return -5;// twisted corner

    if( (edgeParity()^cornerParity()) != 0) return -6;// parity error

    return 0;// cube ok

    }

}