TwistyPuzzleLib

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

// Copyright 2023 Leszek Koltunski                                                               //

//                                                                                               //

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

//                                                                                               //

// Magic Cube is proprietary software licensed under an EULA which you should have received      //

// along with the code. If not, check https://distorted.org/magic/License-Magic-Cube.html        //

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

package org.distorted.objectlib.tablebases;

import org.distorted.library.helpers.QuatHelper;

import org.distorted.library.type.Static3D;

import org.distorted.library.type.Static4D;

import org.distorted.objectlib.R;

import org.distorted.objectlib.helpers.OperatingSystemInterface;

import org.distorted.objectlib.helpers.QuatGroupGenerator;

import org.distorted.objectlib.objects.TwistySkewb;

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

public class TBSkewb extends TablebasesPruning

{

  public static final int[] FIXED= {0,3,5,6};

  public static final int[] FREE = {1,2,4,7};

  private static final int[][] freeIndex = { {1,3,2},{0,2,3},{3,1,0},{2,0,1} };

  // [1][] are the 3 quats the 1st 'fixed' corner will have when twisted with respectively twist 0,1,2.

  private static final int[][] fixedQuats = { {0,1,2},{0,7,8},{0,6,5},{0,4,3} };

  private static int[][] tetradPerm, divideTable, multiplyTable, locationTable;

  // centerQuats[0][1] are the two quats the 0th center might have when rotated to the position of

  // the 1st center.

  // Warning! Order of the centers follows the order from TwistySkewb, i.e. +z,-z,+y,-y,+x,-x

  private static final int[][][] centerQuats =

    {

        { {0,10},{9,11},{1,7},{4,6},{2,5},{3,8} },

        { {9,11},{0,10},{4,6},{1,7},{3,8},{2,5} },

        { {2,8},{3,5},{0,11},{9,10},{1,4},{6,7} },

        { {3,5},{2,8},{9,10},{0,11},{6,7},{1,4} },

        { {1,6},{4,7},{2,3},{5,8},{0,9},{10,11} },

        { {4,7},{1,6},{5,8},{2,3},{10,11},{0,9} }

    };

  private static Static4D[] mQuats;

  private static final Static3D[] ROT_AXIS = TwistySkewb.ROT_AXIS;

  private static final int[][] BASIC_ANGLES = { {3,3},{3,3},{3,3},{3,3} };

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

  public TBSkewb()

    {

    super();

    }

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

  public TBSkewb(OperatingSystemInterface os)

    {

    super(os,new int[] {R.raw.skew_2_pruning4,R.raw.skew_2_pruning5},new int[]{R.raw.skew_2_pruning11});

    }

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

  int[][] getBasicAngles()

    {

    return BASIC_ANGLES;

    }

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

  Static3D[] getRotationAxis()

    {

    return ROT_AXIS;

    }

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

  float[][] getPosition()

    {

    return new float[][]

         {

             { 1, 1, 1 },

             { 1, 1,-1 },

             { 1,-1, 1 },

             { 1,-1,-1 },

             {-1, 1, 1 },

             {-1, 1,-1 },

             {-1,-1, 1 },

             {-1,-1,-1 },

             { 0, 0, 1 },

             { 0, 0,-1 },

             { 0, 1, 0 },

             { 0,-1, 0 },

             { 1, 0, 0 },

             {-1, 0, 0 }

         };

    }

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

  float[][] getCuts()

    {

    float[] cut = {0};

    return new float[][] { cut,cut,cut,cut };

    }

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

  boolean[][] getRotatable()

    {

    boolean[] t1 = new boolean[] {false,true};

    boolean[] t2 = new boolean[] {true,false};

    return new boolean[][] { t1,t2,t2,t1 };

    }

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

// specifically for the tablebase

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

  int getSize()

    {

    return 3149280;  // see https://www.jaapsch.net/puzzles/skewb.htm

    }

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

  int getMinScramble()

    {

    return 9;

    }

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

  int[] getMidPruningLevels()

    {

    return new int[] {4,5};

    }

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

  int[] getHighPruningLevels()

    {

    return new int[] {11};

    }

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

  int getGodsNumber()

    {

    return 11;

    }

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

  boolean moveCanProceed(int lastA, int lastR, int currA, int currR)

    {

    return lastA!=currA;

    }

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

  private static int figureOutLocation(float[] loc, float[][] vectors)

    {

    float minDiff = Float.MAX_VALUE;

    int index = -1;

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

      {

      float[] v = vectors[i];

      float dx = v[0]-loc[0];

      float dy = v[1]-loc[1];

      float dz = v[2]-loc[2];

      float diff = dx*dx + dy*dy + dz*dz;

      if( diff<minDiff )

        {

        minDiff = diff;

        index = i;

        }

      }

    return index;

    }

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

  private static void generateLocation()

    {

    locationTable = new int[4][12];

    if( mQuats==null )

      mQuats = QuatGroupGenerator.computeGroup(ROT_AXIS,BASIC_ANGLES);

    float[][] vectors = new float[][]

      {

        { 1, 1,-1, 0},

        { 1,-1, 1, 0},

        {-1, 1, 1, 0},

        {-1,-1,-1, 0}

      };

    float[] output = new float[4];

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

      {

      float[] v = vectors[i];

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

        {

        Static4D quat = mQuats[q];

        QuatHelper.rotateVectorByQuat(output,v[0],v[1],v[2],v[3],quat);

        int loc = figureOutLocation(output,vectors);

        locationTable[i][q] = loc;

        }

      }

    }

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

  public static int computeLocation(int index, int quat)

    {

    if( locationTable==null ) generateLocation();

    return locationTable[index][quat];

    }

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

  private static int fixedQuatToTwist(int index, int quat)

    {

    int[] qs = fixedQuats[index];

    if( quat==qs[0]) return 0;

    if( quat==qs[1]) return 1;

    if( quat==qs[2]) return 2;

    android.util.Log.e("D", "error in fixedQuatToTwist, index="+index+" quat="+quat);

    return -1;

    }

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

  private static int fixedTwistToQuat(int index, int twist)

    {

    return fixedQuats[index][twist];

    }

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

  private static int figureOutTetrad(int q0, int q1, int q2, int q3)

    {

    int[] quats = fixedQuats[3];

    int s00 = divideFromRight(q0,quats[0]);

    int s01 = divideFromRight(q0,quats[1]);

    int s02 = divideFromRight(q0,quats[2]);

    quats = fixedQuats[1];

    int s10 = divideFromRight(q2,quats[0]);

    int s11 = divideFromRight(q2,quats[1]);

    int s12 = divideFromRight(q2,quats[2]);

    quats = fixedQuats[2];

    int s20 = divideFromRight(q1,quats[0]);

    if( s20==s00 || s20==s01 || s20==s02 )

      return ( s20==s10 || s20==s11 || s20==s12 ) ? s20 : -1;

    int s21 = divideFromRight(q1,quats[1]);

    if( s21==s00 || s21==s01 || s21==s02 )

      return ( s21==s10 || s21==s11 || s21==s12 ) ? s21 : -1;

    int s22 = divideFromRight(q1,quats[2]);

    if( s22==s00 || s22==s01 || s22==s02 )

      return ( s22==s10 || s22==s11 || s22==s12 ) ? s22 : -1;

    return -1;

    }

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

  private static void generateDivideTable()

    {

    divideTable = new int[12][12];

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

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

        {

        int res = multiplyQuat(i,j);

        divideTable[res][j] = i;

        }

    }

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

// double cover!

  private static int findQuat(Static4D quat)

    {

    float minDiff = Float.MAX_VALUE;

    int bestindex = -1;

    float dx,dy,dz,dw,diff;

    float x= quat.get0();

    float y= quat.get1();

    float z= quat.get2();

    float w= quat.get3();

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

      {

      Static4D q = mQuats[i];

      dx = x-q.get0();

      dy = y-q.get1();

      dz = z-q.get2();

      dw = w-q.get3();

      diff = dx*dx + dy*dy + dz*dz + dw*dw;

      if( diff<minDiff )

        {

        minDiff = diff;

        bestindex = i;

        }

      dx = x+q.get0();

      dy = y+q.get1();

      dz = z+q.get2();

      dw = w+q.get3();

      diff = dx*dx + dy*dy + dz*dz + dw*dw;

      if( diff<minDiff )

        {

        minDiff = diff;

        bestindex = i;

        }

      }

    return bestindex;

    }

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

  private static void generateMultiplyTable()

    {

    multiplyTable = new int[12][12];

    if( mQuats==null )

      mQuats = QuatGroupGenerator.computeGroup(ROT_AXIS,BASIC_ANGLES);

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

      {

      Static4D q0 = mQuats[i];

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

        {

        Static4D q1 = mQuats[j];

        Static4D res= QuatHelper.quatMultiply(q0,q1);

        int index   = findQuat(res);

        multiplyTable[i][j] = index;

        }

      }

    }

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

  private static void generateTetradPerm()

    {

    tetradPerm = new int[4][4];

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

      for(int j=0; j<4; j++) tetradPerm[i][j] = -1;

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

      {

      int loc0 = computeLocation(0,q);

      int loc1 = computeLocation(1,q);

      tetradPerm[loc0][loc1] = q;

      }

    }

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

  public static int figureOutTetrad(int[] perm)

    {

    if( tetradPerm==null ) generateTetradPerm();

    return tetradPerm[perm[0]][perm[1]];

    }

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

// return (r^-1) * q

  private static int divideFromLeft(int q, int r)

    {

    if( divideTable==null ) generateDivideTable();

    return multiplyTable[divideTable[0][r]][q];

    }

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

// return q * (r^-1)

  private static int divideFromRight(int q, int r)

    {

    if( divideTable==null ) generateDivideTable();

    return divideTable[q][r];

    }

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

  private static int multiplyQuat(int q, int r)

    {

    if( multiplyTable==null ) generateMultiplyTable();

    return multiplyTable[q][r];

    }

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

// In case of the four 'fixed' corners (0,3,5,6) which do not change their location,

// the twist is natural: 0 in the init positions and increasing 1 mod 3 on each CW turn.

//

// In case of the four 'free' corners their twist is relative to the position of the 'free'

// tetrahedron. And so, for example the twist of free corner 1 (whose 0th face is orange) is equal

// to 0 if free corner 7 is on the same face like 0th face of corner 1 (which is the case in init

// position); then once free corners 2,4,7 permute CW, twist of corner 1 increases by 1 mod 3.

//

// Way to figure out the 'free' twists: notice their final quat must be a product of initial

// 'in place' quat and a common quat which rotates the tetrad of all 4 'free' corners.

// Figure out the tetrad quat and divide free quats by it, then do the same like with fixed corners.

  public static void computeCornerTwists(int[] twists, int[] quats)

    {

    for(int i=0; i<4; i++) twists[FIXED[i]] = fixedQuatToTwist(i,quats[FIXED[i]]);

    int free0 = quats[FREE[0]];

    int free1 = quats[FREE[1]];

    int free2 = quats[FREE[2]];

    int free3 = quats[FREE[3]];

    int tetradQuat = figureOutTetrad(free0,free1,free2,free3);

    if( tetradQuat>=0 )

      {

      int quat0 = divideFromLeft(free0, tetradQuat);

      int quat1 = divideFromLeft(free1, tetradQuat);

      int quat2 = divideFromLeft(free2, tetradQuat);

      int quat3 = divideFromLeft(free3, tetradQuat);

      twists[FREE[0]] = fixedQuatToTwist(3, quat0);

      twists[FREE[1]] = fixedQuatToTwist(2, quat1);

      twists[FREE[2]] = fixedQuatToTwist(1, quat2);

      twists[FREE[3]] = fixedQuatToTwist(0, quat3);

      }

    else

      {

      android.util.Log.e("D", "ERROR in computeCornerTwists: "+free0+" "+free1+" "+free2+" "+free3);

      }

    }

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

  public static void fillInQuats(int[] quats, int[] perm, int[] twist)

    {

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

      {

      int fixed = FIXED[i];

      int twFi  = twist[fixed];

      quats[fixed] = fixedQuats[i][twFi];

      }

    int q0 = fixedTwistToQuat(3,twist[FREE[0]]);

    int q1 = fixedTwistToQuat(2,twist[FREE[1]]);

    int q2 = fixedTwistToQuat(1,twist[FREE[2]]);

    int q3 = fixedTwistToQuat(0,twist[FREE[3]]);

    int tetradQuat = figureOutTetrad(perm);

    quats[FREE[0]] = multiplyQuat(tetradQuat,q0);

    quats[FREE[1]] = multiplyQuat(tetradQuat,q1);

    quats[FREE[2]] = multiplyQuat(tetradQuat,q2);

    quats[FREE[3]] = multiplyQuat(tetradQuat,q3);

    }

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

  private int[] computeCenterPerm(int[] quats)

    {

    int[] output = new int[6];

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

      {

      output[i] = -1;

      int[][] c = centerQuats[i];

      int q = quats[8+i];

      for(int j=0; j<6; j++)

        if( c[j][0]==q || c[j][1]==q )

          {

          output[i] = j;

          break;

          }

      }

    return output;

    }

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

  private void fillCenterQuats(int[] quats, int[] perm)

    {

    for(int i=0; i<6; i++) quats[8+i] = centerQuats[i][perm[i]][0];

    }

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

  private void fillUpToEvenPerm(int[] perm)

    {

    int min, max;

         if( perm[0]!=0 && perm[1]!=0 ) min=0;

    else if( perm[0]!=1 && perm[1]!=1 ) min=1;

    else                                min=2;

         if( perm[0]!=3 && perm[1]!=3 ) max=3;

    else if( perm[0]!=2 && perm[1]!=2 ) max=2;

    else                                max=1;

    int diff = perm[1]-perm[0];

    if( diff==-2 || diff==1 || diff==3 ) { perm[2]=min; perm[3]=max; }

    else                                 { perm[2]=max; perm[3]=min; }

    }

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

  public static int permFree1(int permFree0, int sumFixedTwists)

    {

    return freeIndex[permFree0][sumFixedTwists%3];

    }

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

  int[] getQuats(int index)

    {

    int[] permFree = new int[4];

    int center_perm_num = (index%360);

    index /= 360;

    int totalTwist = (index%2187);

    permFree[0] = (index/2187);

    int[] quats = new int[14];

    int[] center_perm = new int[6];

    int[] twist = new int[8];

    TablebaseHelpers.getEvenPermutationFromNum(center_perm, center_perm_num);

    fillCenterQuats(quats,center_perm);

    int total = 0;

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

      {

      twist[i] = (totalTwist%3);

      totalTwist /= 3;

      total += twist[i];

      }

    twist[7] = ((24-total)%3);

    int sumFixedTwists = twist[FIXED[0]]+twist[FIXED[1]]+twist[FIXED[2]]+twist[FIXED[3]];

    permFree[1] = permFree1(permFree[0],sumFixedTwists);

    fillUpToEvenPerm(permFree);

    fillInQuats(quats,permFree,twist);

    return quats;

    }

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

  int getIndex(int[] quats)

    {

    int[] center_perm = computeCenterPerm(quats);

    int center_perm_num = TablebaseHelpers.computeEvenPermutationNum(center_perm);

    int[] twist = new int[8];

    computeCornerTwists(twist,quats);

    int totalTwist = twist[0]+ 3*(twist[1]+ 3*(twist[2]+ 3*(twist[3]+ 3*(twist[4]+ 3*(twist[5]+ 3*twist[6])))));

    int locationOfFree0 = computeLocation(0,quats[1]);

    return center_perm_num+ 360*(totalTwist + 2187*locationOfFree0);

    }

}