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;

import org.distorted.objectlib.helpers.ObjectShape;

import java.util.ArrayList;

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

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;

  private static class SurfaceInfo

    {

    float[] surface;

    int[] indices;

    SurfaceInfo(float[] s) { surface = s; }

    void setIndices(int[] i) { indices = i; }

    };

  private int[][] mSurfaceTable;

  private int[][] mFaceColorTable;

  private int[][] mCubitFaceToSurfaceMap;

  private int[][] mCubitFaceColor;

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

// 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[] gq = mSolvedQuats[group];

      int numEntries= gq.length;

      int numCubits = gq[0];

      int firstCubit= gq[1];

      int firstQuat = cubits[firstCubit].mQuatIndex;

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

        {

        int currCubit= gq[cubit];

        int currQuat = cubits[currCubit].mQuatIndex;

        boolean isGood= (firstQuat==currQuat);

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

          if( firstQuat == getMultQuat(currQuat,gq[q]) ) isGood = true;

        if( !isGood ) return false;

        }

      }

    return true;

    }

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

  private int surfaceExists(ArrayList<SurfaceInfo> list, float[] newSurface)

    {

    final float MAX_ERROR = 0.01f;

    int size = list.size();

    float dnx,dny,dnz,dnw;

    for(int s=0; s<size; s++)

      {

      SurfaceInfo si = list.get(s);

      float[] surface = si.surface;

      dnx = newSurface[0] - surface[0];

      dny = newSurface[1] - surface[1];

      dnz = newSurface[2] - surface[2];

      dnw = newSurface[3] - surface[3];

      if( dnx*dnx + dny*dny + dnz*dnz + dnw*dnw < MAX_ERROR )

        {

        //android.util.Log.d("D", "1 Surface "+newSurface[0]+" "+newSurface[1]+" "+newSurface[2]+" "+newSurface[3]+" exists already at "+s);

        return s;

        }

      dnx = newSurface[0] + surface[0];

      dny = newSurface[1] + surface[1];

      dnz = newSurface[2] + surface[2];

      dnw = newSurface[3] + surface[3];

      if( dnx*dnx + dny*dny + dnz*dnz + dnw*dnw < MAX_ERROR )

        {

        //android.util.Log.d("D", "2 Surface "+newSurface[0]+" "+newSurface[1]+" "+newSurface[2]+" "+newSurface[3]+" exists already at "+s);

        return s;

        }

      }

    //android.util.Log.d("D", "Surface "+newSurface[0]+" "+newSurface[1]+" "+newSurface[2]+" "+newSurface[3]+" doesnt exist yet");

    return -1;

    }

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

  private int adjoinNewSurface(ArrayList<SurfaceInfo> list, float[] newSurface)

    {

    int index = surfaceExists(list,newSurface);

    if( index>=0 ) return index;

    //android.util.Log.d("D", "Adding new surface "+newSurface[0]+" "+newSurface[1]+" "+newSurface[2]+" "+newSurface[3]+" to "+list.size());

    SurfaceInfo si = new SurfaceInfo(newSurface);

    list.add(si);

    return list.size()-1;

    }

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

  private float[] multiplySurface( float[] surface, Static4D quat )

    {

    float[] ret = new float[4];

    QuatHelper.rotateVectorByQuat(ret,surface[0],surface[1],surface[2],0,quat);

    ret[3] = surface[3];

    return ret;

    }

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

  private void computeSurfaceTable()

    {

    int[] numLayers = mParent.getNumLayers();

    float[][] pos = mParent.getCubitPositions(numLayers);

    int numCubits = pos.length;

    int numVariants = mParent.getNumCubitVariants(numLayers);

    ObjectShape[] shapes = new ObjectShape[numVariants];

    mCubitFaceToSurfaceMap = new int[numCubits][];

    mCubitFaceColor = new int[numCubits][];

    for(int v=0; v<numVariants; v++) shapes[v] = mParent.getObjectShape(v);

    ArrayList<SurfaceInfo> tmpSurfaces = new ArrayList<>();

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

      {

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

      ObjectShape s = shapes[variant];

      int numFaces = s.getNumFaces();

      mCubitFaceColor[c] = new int[numFaces];

      mCubitFaceToSurfaceMap[c] = new int[numFaces];

      for(int f=0; f<numFaces; f++) mCubitFaceToSurfaceMap[c][f] = -1;

      Static4D cubitQuat = mParent.getCubitQuats(c,numLayers);

      float[] po = pos[c];

      int poslen = po.length/3;

      float px=0, py=0, pz=0;

      for(int p=0; p<poslen; p++)

        {

        px += po[3*p  ];

        py += po[3*p+1];

        pz += po[3*p+2];

        }

      px /= poslen;

      py /= poslen;

      pz /= poslen;

      //android.util.Log.e("D", "cubit "+c+" pos "+px+" "+py+" "+pz+" faces: "+numFaces);

      for(int f=0; f<numFaces; f++)

        {

        mCubitFaceColor[c][f] = mParent.getCubitFaceColor(c,f);

        if( !mParent.faceIsOuter(c,f) ) continue;

        //android.util.Log.e("D", "cubit "+c+" face "+f);

        float[] surface  = new float[4];

        float[] rotPoint = new float[4];

        float[] normal   = new float[4];

        float[] intPoint = new float[3];

        s.getFacePoint(f,intPoint);

        s.getFaceNormal(f,normal);

        QuatHelper.rotateVectorByQuat(rotPoint,intPoint[0],intPoint[1],intPoint[2],1,cubitQuat);

        QuatHelper.rotateVectorByQuat(surface,normal[0],normal[1],normal[2],0,cubitQuat);

        float x = rotPoint[0] + px;

        float y = rotPoint[1] + py;

        float z = rotPoint[2] + pz;

        surface[3] = x*surface[0] + y*surface[1] + z*surface[2];

        int index = surfaceExists(tmpSurfaces,surface);

        if( index>=0 )

          {

          mCubitFaceToSurfaceMap[c][f] = index;

          }

        else

          {

          SurfaceInfo si = new SurfaceInfo(surface);

          tmpSurfaces.add(si);

          mCubitFaceToSurfaceMap[c][f] = tmpSurfaces.size()-1;

          //android.util.Log.e("D", "added surface "+tmpSurfaces.size()+" cubit "+c+" face "+f+" variant "+variant);

          int[] indices = new int[mNumQuats];

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

            {

            float[] ts = multiplySurface(surface, mObjectQuats[q]);

            int ind = adjoinNewSurface(tmpSurfaces,ts);

/*

            if( ind==6 || ind==5 )

              {

              android.util.Log.e("D","SURFACE "+ind+": "+ts[0]+" "+ts[1]+" "+ts[2]+" "+ts[3] );

              }

*/

            indices[q] = ind;

            }

          si.setIndices(indices);

          }

        }

      }

    int size = tmpSurfaces.size();

    mSurfaceTable = new int[size][];

    for(int s=0; s<size; s++)

      {

      SurfaceInfo si = tmpSurfaces.get(s);

      if( si.indices == null )

        {

        float[] surface = si.surface;

        int[] indices = new int[mNumQuats];

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

          {

          float[] ts = multiplySurface(surface, mObjectQuats[q]);

          int ind = adjoinNewSurface(tmpSurfaces,ts);

          indices[q] = ind;

          }

        si.setIndices(indices);

        }

      mSurfaceTable[s] = si.indices;

      }

    }

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

  private void debugSurfaceTable(ArrayList<SurfaceInfo> surfaces)

    {

    int size = surfaces.size();

    android.util.Log.e("D", "COMPUTE size: "+size);

    for(int s=0; s<size; s++)

      {

      StringBuilder sb = new StringBuilder();

      sb.append("surface ");

      sb.append(s);

      sb.append(" : ");

      SurfaceInfo si = surfaces.get(s);

      float[] sur = si.surface;

      sb.append(sur[0]);

      sb.append(' ');

      sb.append(sur[1]);

      sb.append(' ');

      sb.append(sur[2]);

      sb.append(' ');

      sb.append(sur[3]);

      sb.append(" indices:");

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

        {

        sb.append(' ');

        sb.append(mSurfaceTable[s][q]);

        }

      android.util.Log.d("D", sb.toString() );

      }

    }

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

  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;

    }

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

  private int surfaceColor(int filled, int surface)

    {

    for(int s=0; s<filled; s++)

      if( mFaceColorTable[s][0] == surface ) return mFaceColorTable[s][1];

    return -1;

    }

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

  private boolean isSolved2(TwistyObjectCubit[] cubits)

    {

    int filled = 0;

    int max = mFaceColorTable.length;

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

      {

      int numFaces = mCubitFaceToSurfaceMap[c].length;

      int quat = cubits[c].mQuatIndex;

      for(int f=0; f<numFaces; f++)

        {

        int initSurface = mCubitFaceToSurfaceMap[c][f];

        if( initSurface>=0 )

          {

          int currSurface = mSurfaceTable[initSurface][quat];

          int currColor = mCubitFaceColor[c][f];

          int prevColor = surfaceColor(filled,currSurface);

          if( prevColor<0 )

            {

            if( filled>=max ) return false;

            mFaceColorTable[filled][0] = currSurface;

            mFaceColorTable[filled][1] = currColor;

            prevColor = currColor;

            filled++;

            }

          if( prevColor!=currColor ) return false;

          }

        }

      }

    return true;

    }

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

// 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];

    if( mFunctionIndex==2 )

      {

      computeSurfaceTable();

      int numFaces = parent.getNumFaces();

      mFaceColorTable = new int[numFaces][2];

      }

    }

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

  boolean isSolved(TwistyObjectCubit[] cubits)

    {

    switch(mFunctionIndex)

      {

      case 0: return isSolved0(cubits);

      case 1: return isSolved1(cubits);

      case 2: return isSolved2(cubits);

      }

    return false;

    }

  }