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.main;

import org.distorted.library.helpers.QuatHelper;

import org.distorted.library.type.Static3D;

import org.distorted.library.type.Static4D;

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

class TwistyObjectSolved

  {

  private final TwistyObject mParent;

  private final Static4D[] mObjectQuats;

  private final int mNumQuats;

  private final float[][] mOrigPos;

  private final int mNumCubits;

  private final int mFunctionIndex;

  private final int[] mTmpQuats;

  private int[][] mSolvedQuats;

  private int[][] mQuatMult;

  private int[] mFaceMap;

  private int[][] mScramble;

  private int[] mColors;

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

// remember about the double cover or unit quaternions!

  private int mulQuat(int q1, int q2)

    {

    Static4D result = QuatHelper.quatMultiply(mObjectQuats[q1],mObjectQuats[q2]);

    float rX = result.get0();

    float rY = result.get1();

    float rZ = result.get2();

    float rW = result.get3();

    final float MAX_ERROR = 0.1f;

    float dX,dY,dZ,dW;

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

      {

      dX = mObjectQuats[i].get0() - rX;

      dY = mObjectQuats[i].get1() - rY;

      dZ = mObjectQuats[i].get2() - rZ;

      dW = mObjectQuats[i].get3() - rW;

      if( dX<MAX_ERROR && dX>-MAX_ERROR &&

          dY<MAX_ERROR && dY>-MAX_ERROR &&

          dZ<MAX_ERROR && dZ>-MAX_ERROR &&

          dW<MAX_ERROR && dW>-MAX_ERROR  ) return i;

      dX = mObjectQuats[i].get0() + rX;

      dY = mObjectQuats[i].get1() + rY;

      dZ = mObjectQuats[i].get2() + rZ;

      dW = mObjectQuats[i].get3() + rW;

      if( dX<MAX_ERROR && dX>-MAX_ERROR &&

          dY<MAX_ERROR && dY>-MAX_ERROR &&

          dZ<MAX_ERROR && dZ>-MAX_ERROR &&

          dW<MAX_ERROR && dW>-MAX_ERROR  ) return i;

      }

    return -1;

    }

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

  private int getMultQuat(int index1, int index2)

    {

    if( mQuatMult==null )

      {

      mQuatMult = new int[mNumQuats][mNumQuats];

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

        for(int j=0; j<mNumQuats; j++) mQuatMult[i][j] = -1;

      }

    if( index1<mNumQuats && index2<mNumQuats )

      {

      if( mQuatMult[index1][index2]==-1 ) mQuatMult[index1][index2] = mulQuat(index1,index2);

      return mQuatMult[index1][index2];

      }

    return -1;

    }

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

  private int computeScramble(int quatNum, int centerNum)

    {

    float MAXDIFF = 0.01f;

    float[] center= mOrigPos[centerNum];

    Static4D sc = new Static4D(center[0], center[1], center[2], 1.0f);

    Static4D result = QuatHelper.rotateVectorByQuat(sc,mObjectQuats[quatNum]);

    float x = result.get0();

    float y = result.get1();

    float z = result.get2();

    for(int c=0; c<mNumCubits; c++)

      {

      float[] cent = mOrigPos[c];

      float qx = cent[0] - x;

      float qy = cent[1] - y;

      float qz = cent[2] - z;

      if( qx>-MAXDIFF && qx<MAXDIFF &&

          qy>-MAXDIFF && qy<MAXDIFF &&

          qz>-MAXDIFF && qz<MAXDIFF  ) return c;

      }

    return -1;

    }

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

// This is used to build internal data structures for the generic 'isSolved()'

//

// if this is an internal cubit (all faces black): return -1

// if this is a face cubit (one non-black face): return the color index of the only non-black face.

// Color index, i.e. the index into the 'FACE_COLORS' table.

// else (edge or corner cubit, more than one non-black face): return -2.

  private int retCubitSolvedStatus(int cubit, int[] numLayers, int numCubitFaces, int[][] cubitFaceColors)

    {

    int numNonBlack=0, nonBlackIndex=-1, stiShape, cubColor;

    int variant = mParent.getCubitVariant(cubit,numLayers);

    for(int face=0; face<numCubitFaces; face++)

      {

      stiShape = mParent.getVariantStickerShape(variant,face);

      int numFaces = cubitFaceColors[cubit].length;

      cubColor = face<numFaces ? cubitFaceColors[cubit][face] : -1;

      if( stiShape>=0 && cubColor>=0 )

        {

        numNonBlack++;

        nonBlackIndex = cubColor;

        }

      }

    if( numNonBlack==0 ) return -1;

    if( numNonBlack>=2 ) return -2;

    return nonBlackIndex;

    }

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

  private int[] buildSolvedQuats(Static3D faceAx)

    {

    final float MAXD = 0.0001f;

    float x = faceAx.get0();

    float y = faceAx.get1();

    float z = faceAx.get2();

    float a,dx,dy,dz,qx,qy,qz;

    Static4D quat;

    int place = 0;

    for(int q=1; q<mNumQuats; q++)

      {

      quat = mObjectQuats[q];

      qx = quat.get0();

      qy = quat.get1();

      qz = quat.get2();

           if( x!=0.0f ) { a = qx/x; }

      else if( y!=0.0f ) { a = qy/y; }

      else               { a = qz/z; }

      dx = a*x-qx;

      dy = a*y-qy;

      dz = a*z-qz;

      if( dx>-MAXD && dx<MAXD && dy>-MAXD && dy<MAXD && dz>-MAXD && dz<MAXD )

        {

        mTmpQuats[place++] = q;

        }

      }

    if( place!=0 )

      {

      int[] ret = new int[place];

      System.arraycopy(mTmpQuats,0,ret,0,place);

      return ret;

      }

    return null;

    }

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

// special SolvedQuats for the case where there are no corner of edge cubits.

// first row {0} - means there are no corners or edges.

// each next defines all cubits of a singe face (numCubits, firstCubit, cubit1,..,cubitN-1, quat0,..., quatM

  private boolean isSolvedCentersOnly(TwistyObjectCubit[] cubits)

    {

    int numGroups = mSolvedQuats.length;

    for(int group=1; group<numGroups; group++)

      {

      int numEntries= mSolvedQuats[group].length;

      int numCubits = mSolvedQuats[group][0];

      int firstCubit= mSolvedQuats[group][1];

      int firstQuat = cubits[firstCubit].mQuatIndex;

      for(int cubit=2; cubit<=numCubits; cubit++)

        {

        int currCubit= mSolvedQuats[group][cubit];

        int currQuat = cubits[currCubit].mQuatIndex;

        boolean isGood= (firstQuat==currQuat);

        for(int q=numCubits+1; !isGood && q<numEntries; q++)

          {

          int quat = mSolvedQuats[group][q];

          if( firstQuat == getMultQuat(currQuat,quat) ) isGood = true;

          }

        if( !isGood ) return false;

        }

      }

    return true;

    }

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

  private boolean isSolved0(TwistyObjectCubit[] cubits)

    {

    if( mSolvedQuats[0][0]==0 ) return isSolvedCentersOnly(cubits);

    for( int[] solvedQuat : mSolvedQuats )

      {

      int numCubits = solvedQuat[0];

      int firstCubit= solvedQuat[1];

      int quat = cubits[firstCubit].mQuatIndex;

      for( int cubit=2; cubit<=numCubits; cubit++ )

        {

        int c = solvedQuat[cubit];

        if( quat != cubits[c].mQuatIndex ) return false;

        }

      }

    int cubit= mSolvedQuats[0][1];

    int quat0= cubits[cubit].mQuatIndex;

    int numGroups = mSolvedQuats.length;

    for(int group=1; group<numGroups; group++)

      {

      int firstCubit= mSolvedQuats[group][1];

      int currQuat  = cubits[firstCubit].mQuatIndex;

      if( quat0==currQuat ) continue;

      boolean isGood= false;

      int numEntries= mSolvedQuats[group].length;

      int numCubits = mSolvedQuats[group][0];

      for(int q=numCubits+1; q<numEntries; q++)

        {

        int quat = mSolvedQuats[group][q];

        if( quat0 == getMultQuat(currQuat,quat) )

          {

          isGood = true;

          break;

          }

        }

      if( !isGood ) return false;

      }

    return true;

    }

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

// Dino4 uses this. It is solved if and only if groups of cubits

// (0,3,7), (1,2,5), (4,8,9), (6,10,11)

// or

// (0,1,4), (2,3,6), (5,9,10), (7,8,11)

// are all the same color.

  private boolean isSolved1(TwistyObjectCubit[] cubits)

    {

    if( mScramble==null )

      {

      mScramble = new int[mNumQuats][mNumCubits];

      mColors   = new int[mNumCubits];

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

        for(int c=0; c<mNumCubits; c++) mScramble[q][c] = computeScramble(q,c);

      }

    if( mFaceMap==null )

      {

      mFaceMap = new int[] { 4, 2, 2, 4, 0, 2, 1, 4, 0, 0, 1, 1 };

      }

    for(int c=0; c<mNumCubits; c++)

      {

      int index = mScramble[cubits[c].mQuatIndex][c];

      mColors[index] = mFaceMap[c];

      }

    if( mColors[0]==mColors[3] && mColors[0]==mColors[7] &&

        mColors[1]==mColors[2] && mColors[1]==mColors[5] &&

        mColors[4]==mColors[8] && mColors[4]==mColors[9]  ) return true;

    if( mColors[0]==mColors[1] && mColors[0]==mColors[4] &&

        mColors[2]==mColors[3] && mColors[2]==mColors[6] &&

        mColors[5]==mColors[9] && mColors[5]==mColors[10] ) return true;

    return false;

    }

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

// Called from TwistyObject

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

  int[][] getSolvedQuats(int[] numLayers, int numCubitFaces, int[][] cubitFaceColors)

    {

    int[] groups = new int[mNumCubits];

    int numGroups = 1;

    int numFirst  = 0;

    for(int cubit=0; cubit<mNumCubits; cubit++)

      {

      groups[cubit] = retCubitSolvedStatus(cubit,numLayers,numCubitFaces,cubitFaceColors);

      if( groups[cubit]>=0 ) numGroups++;

      else                   numFirst++;

      }

    int firstIndex = 1;

    int groupIndex = 1;

    int[][] solvedQuats = new int[numGroups][];

    solvedQuats[0] = new int[1+numFirst];

    solvedQuats[0][0] = numFirst;

    Static3D[] axis = mParent.getFaceAxis();

    for(int cubit=0; cubit<mNumCubits; cubit++)

      {

      int group = groups[cubit];

      if( group<0 )

        {

        solvedQuats[0][firstIndex] = cubit;

        firstIndex++;

        }

      else

        {

        int[] quats = buildSolvedQuats(axis[group]);

        int len = quats==null ? 0 : quats.length;

        solvedQuats[groupIndex] = new int[2+len];

        solvedQuats[groupIndex][0] = 1;

        solvedQuats[groupIndex][1] = cubit;

        for(int i=0; i<len; i++) solvedQuats[groupIndex][i+2] = quats[i];

        groupIndex++;

        }

      }

/*

    String dbg = "SOLVED GROUPS:\n";

    for(int g=0; g<numGroups; g++)

      {

      int len = solvedQuats[g].length;

      for(int i=0; i<len; i++) dbg += (" "+solvedQuats[g][i]);

      dbg+="\n";

      }

    android.util.Log.e("D", dbg);

*/

    return solvedQuats;

    }

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

  void setupSolvedQuats(int[][] quats)

    {

    mSolvedQuats = quats;

    }

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

  TwistyObjectSolved(TwistyObject parent, float[][] orig, int index)

    {

    mParent = parent;

    mObjectQuats = mParent.mObjectQuats;

    mNumQuats = mObjectQuats.length;

    mOrigPos = orig;

    mNumCubits = orig.length;

    mFunctionIndex = index;

    mTmpQuats = new int[mNumQuats];

    }

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

  boolean isSolved(TwistyObjectCubit[] cubits)

    {

    if( mFunctionIndex==0 ) return isSolved0(cubits);

    if( mFunctionIndex==1 ) return isSolved1(cubits);

    return false;

    }

  }