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 android.content.res.Resources;

import org.distorted.library.main.QuatHelper;

import org.distorted.library.type.Static3D;

import org.distorted.library.type.Static4D;

import org.distorted.objectlib.helpers.QuatGroupGenerator;

import java.io.ByteArrayOutputStream;

import java.io.IOException;

import java.io.InputStream;

import java.util.ArrayList;

import java.util.Random;

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

public abstract class TablebasesAbstract

{

  private final Static3D[] mAxis;

  private final int mSize, mMinScramble;

  private final int[][] mAngles;

  private final int[] mNumLayers;

  private final int mNumQuats;

  private final Static4D[] mQuats;

  private final float[][] mCuts;

  private final int[] mNumCuts;

  private int[][] mQuatMult;

  private int[] mInvertedQuat;

  Tablebase mTablebase;

  boolean mInitialized;

  final int mScalingFactor;

  final int mNumAxis;

  final float[][] mPosition;

  final int[][] mRotRow;

  final int mNumCubits;

  final boolean[][] mRotatable;

  private static final float[] mTmp = new float[4];

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

  abstract int[][] getBasicAngles();

  abstract Static3D[] getRotationAxis();

  abstract float[][] getPosition();

  abstract float[][] getCuts();

  abstract boolean[][] getRotatable();

  abstract int getMinScramble();

  abstract int getSize();

  abstract int[] getQuats(int index);

  abstract int getIndex(int[] quats);

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

  public TablebasesAbstract()

    {

    mSize = getSize();

    mMinScramble = getMinScramble();

    mAngles = getBasicAngles();

    mAxis = getRotationAxis();

    mNumAxis = mAxis.length;

    mNumLayers = new int[mNumAxis];

    for(int i=0; i<mNumAxis; i++) mNumLayers[i] = mAngles[i].length;

    mQuats = QuatGroupGenerator.computeGroup(mAxis,mAngles);

    mNumQuats = mQuats.length;

    mPosition = getPosition();

    mNumCubits = mPosition.length;

    mRotatable = getRotatable();

    mCuts = getCuts();

    mNumCuts = new int[mNumAxis];

    int scaling = 0;

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

      {

      mNumCuts[i] = (mCuts==null || mCuts[i]==null ? 0 : mCuts[i].length);

      int numLayers = mNumLayers[i];

      for(int j=0; j<numLayers; j++) scaling+=(mAngles[i][j]-1);

      }

    mScalingFactor = scaling;

    mRotRow = new int[mNumCubits][mNumAxis];

    mInitialized = false;

    }

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

  public TablebasesAbstract(Resources res, int resource)

    {

    this();

    mInitialized = true;

    InputStream stream = res.openRawResource(resource);

    ByteArrayOutputStream buffer = new ByteArrayOutputStream();

    int nRead;

    byte[] tmp = new byte[16384];

    try

      {

      while ((nRead = stream.read(tmp, 0, tmp.length)) != -1)

        {

        buffer.write(tmp, 0, nRead);

        }

      stream.close();

      byte[] data = buffer.toByteArray();

      buffer.close();

      mTablebase = new Tablebase(data);

      }

    catch(IOException ex)

      {

      mInitialized = false;

      }

    }

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

  int computeRow(float[] pos, int quat, int axisIndex)

    {

    int ret=0;

    int len = pos.length/3;

    Static3D axis = mAxis[axisIndex];

    float axisX = axis.get0();

    float axisY = axis.get1();

    float axisZ = axis.get2();

    float casted, xoff=0, yoff=0, zoff=0;

    Static4D q = mQuats[quat];

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

      {

      QuatHelper.rotateVectorByQuat(mTmp,pos[3*i],pos[3*i+1],pos[3*i+2],1.0f,q);

      casted = (mTmp[0]+xoff)*axisX + (mTmp[1]+yoff)*axisY + (mTmp[2]+zoff)*axisZ;

      ret |= computeSingleRow(axisIndex,casted);

      }

    return ret;

    }

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

  private int computeSingleRow(int axisIndex,float casted)

    {

    int num = mNumCuts[axisIndex];

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

      {

      if( casted<mCuts[axisIndex][i] ) return (1<<i);

      }

    return (1<<num);

    }

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

// remember about the double cover or unit quaternions!

  private int mulQuat(int q1, int q2)

    {

    Static4D result = QuatHelper.quatMultiply(mQuats[q1],mQuats[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 = mQuats[i].get0() - rX;

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

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

      dW = mQuats[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 = mQuats[i].get0() + rX;

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

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

      dW = mQuats[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;

    }

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

  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 -2;

    }

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

  int getInvertedQuat(int index)

    {

    if( mInvertedQuat==null )

      {

      mInvertedQuat = new int[mNumQuats];

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

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

          {

          int result = getMultQuat(i,j);

          if( result==0 )

            {

            mInvertedQuat[i] = j;

            break;

            }

          }

      }

    return mInvertedQuat[index];

    }

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

// assumption: all layers have the same basicAngles!

  private int insertAllChildren(int index, byte level)

    {

    int ret = 0;

    int[] quats = getQuats(index);

    int numQuats = quats.length;

    int[] tmpQuats = new int[numQuats];

    byte newLevel = (byte)(level+1);

    int quatBasis = 0;

    for(int ax=0; ax<mNumAxis; ax++)

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

        mRotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax);

    for(int ax=0; ax<mNumAxis; ax++)

      {

      for(int layer=0; layer<mNumLayers[ax]; layer++)

        {

        if( !mRotatable[ax][layer] ) continue;

        int bitLayer = (1<<layer);

        int maxAngle = mAngles[ax][layer];

        for(int angle=1; angle<maxAngle; angle++ )

          {

          System.arraycopy(quats, 0, tmpQuats, 0, numQuats);

          int quat = quatBasis + angle;

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

            if( mRotRow[cubit][ax]==bitLayer )

              {

              int currQuat = tmpQuats[cubit];

              int newQuat = getMultQuat(quat,currQuat);

              tmpQuats[cubit] = newQuat;

              }

          int childIndex = getIndex(tmpQuats);

          if( mTablebase.insertUnpacked(childIndex,newLevel) ) ret++;

          }

        }

      quatBasis += (mAngles[ax][0]-1);

      }

    return ret;

    }

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

  public void createTablebase(int maxLevel)

    {

    mTablebase = new Tablebase(mSize);

    int[] solved = getSolvedIndices();

    int numSolved = solved.length;

    for(int s : solved ) mTablebase.insertUnpacked(s,(byte)0);

    int numInserted, totalInserted=numSolved;

    byte insertingLevel = 0;

    android.util.Log.e("D", "creating tablebase of size "+mSize);

    do

      {

      numInserted = 0;

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

        {

        byte level = mTablebase.retrieveUnpacked(i);

        if( level==insertingLevel ) numInserted += insertAllChildren(i,level);

        }

      insertingLevel++;

      totalInserted += numInserted;

      android.util.Log.e("D", "inserted "+numInserted+" positions at level "+insertingLevel);

      }

    while( numInserted>0 && insertingLevel!=maxLevel );

    android.util.Log.e("D", "total Inserted: "+totalInserted);

    }

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

  int[] getSolvedIndices()

    {

    return new int[] {0};

    }

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

  boolean isSolved(int index)

    {

    return index==0;

    }

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

  public void pack()

    {

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

    mTablebase.pack();

    android.util.Log.e("D", "all done");

    mInitialized = true;

    }

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

  public byte[][] getPacked()

    {

    if( !mInitialized )

      {

      createTablebase(-1);

      pack();

      }

    byte[] data = mTablebase.getPacked();

    return new byte[][] { data };

    }

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

  void convertMoves(int[][] moves)

    {

    for(int[] move : moves )

      {

      int[] newMove = newMove(move[0],move[1],move[2]);

      move[0] = newMove[0];

      move[1] = newMove[1];

      move[2] = newMove[2];

      }

    }

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

  int[] newMove(int axis, int layer, int angle)

    {

    int maxAngle = mAngles[axis][layer];

    angle = maxAngle-angle;

    if( angle> 0.5f*maxAngle ) angle -= maxAngle;

    return new int[] { axis, (1<<layer), angle };

    }

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

  private int[][] convertMoves(ArrayList<int[]> moves)

    {

    int len = moves.size();

    int[][] ret = new int[len][];

    for(int i=0; i<len; i++) ret[i] = moves.get(i);

    return ret;

    }

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

  void getNextAxisLayerAngleQuat(int[] data)

    {

    int axis = data[0];

    int layer= data[1];

    int angle= data[2];

    if( angle< mAngles[axis][layer]-1 ) data[2]++;

    else

      {

      data[2] = 1;

      if( layer< mNumLayers[axis]-1 ) data[1]++;

      else

        {

        data[1] = 0;

        data[0] = (axis<mNumAxis-1) ? axis+1 : 0;

        }

      }

    data[3] = data[2];

    for(int i=0; i<data[0]; i++) data[3] += (mAngles[i][0]-1);

    }

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

  int[][] extraInfo(int[][] moves, int[] extra)

    {

    return moves;

    }

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

  public int[][] solution(int index, int[] extra)

    {

    if( !mInitialized ) return null;

    int[] data = new int[4];

    byte level = mTablebase.retrievePacked(index);

    ArrayList<int[]> moves = new ArrayList<>();

    int[] quats = getQuats(index);

    int numQuats = quats.length;

    int[] tmpQuats = new int[numQuats];

    while( !isSolved(index) )

      {

      boolean found = false;

      data[0]=0;

      data[1]=0;

      data[2]=1;

      data[3]=1;

      for(int ax=0; ax<mNumAxis; ax++)

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

          mRotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax);

      for(int s=0; s<mScalingFactor && !found; s++)

        {

        int ax    = data[0];

        int layer = data[1];

        int angle = data[2];

        int quat  = data[3];

        if( mRotatable[ax][layer] )

          {

          int bitLayer = (1<<layer);

          System.arraycopy(quats, 0, tmpQuats, 0, numQuats);

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

            if( mRotRow[cubit][ax]==bitLayer )

              {

              int currQuat = tmpQuats[cubit];

              int newQuat = getMultQuat(quat,currQuat);

              tmpQuats[cubit] = newQuat;

              }

          int childIndex = getIndex(tmpQuats);

          byte newLevel = mTablebase.retrievePacked(childIndex);

          if( ((newLevel-level+1)%3) == 0 )

            {

            int[] tmpMove = newMove(ax,layer,angle);

            moves.add(tmpMove);

            index = childIndex;

            level = (level==0 ? 2 : (byte)(level-1));

            found = true;

            }

          }

        getNextAxisLayerAngleQuat(data);

        }

      quats = getQuats(index);

      if( !found )

        {

        android.util.Log.e("D", "----> solution error: no move found!");

        return null;

        }

      }

    int[][] ret = convertMoves(moves);

    return extraInfo(ret,extra);

    }

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

  public void scramble(Random rnd, int depth, int[][] scramble)

    {

    if( !mInitialized ) return;

    int solDepth = 0;

    int scraLen = scramble.length;

    if( depth>mMinScramble ) depth = mMinScramble;

    int[] cornerTwist = new int[4];

    for(int i=0; i<4; i++) cornerTwist[i] = (rnd.nextInt(3)-1);

    while( solDepth<depth )

      {

      int randomPosition = rnd.nextInt(mSize-1);

      int[][] sol = solution(randomPosition,cornerTwist);

      solDepth = sol.length;

      if( solDepth>=depth )

        {

        int num = Math.min(scraLen,solDepth);

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

          {

          int[] source = sol[solDepth-1-i];

          scramble[i][0] = source[0];

          scramble[i][1] = source[1];

          scramble[i][2] =-source[2];

          }

        }

      }

    }

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

// TESTING

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

  public boolean test(int index)

    {

    if( !mInitialized ) return false;

    int[] data = new int[4];

    byte level = mTablebase.retrievePacked(index);

    int[] quats = getQuats(index);

    int numQuats = quats.length;

    int[] tmpQuats = new int[numQuats];

    data[0]=0;

    data[1]=0;

    data[2]=1;

    data[3]=1;

    for(int ax=0; ax<mNumAxis; ax++)

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

        mRotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax);

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

      {

      int ax    = data[0];

      int layer = data[1];

      int quat  = data[3];

      if( mRotatable[ax][layer] )

        {

        int bitLayer = (1<<layer);

        System.arraycopy(quats, 0, tmpQuats, 0, numQuats);

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

          if( mRotRow[cubit][ax]==bitLayer )

            {

            int currQuat = tmpQuats[cubit];

            int newQuat = getMultQuat(quat,currQuat);

            tmpQuats[cubit] = newQuat;

            }

        int childIndex = getIndex(tmpQuats);

        byte newLevel = mTablebase.retrievePacked(childIndex);

        if( ((newLevel-level+1)%3) == 0 ) return true;

        }

      getNextAxisLayerAngleQuat(data);

      }

    return false;

    }

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

  public void testPruning(int level)

    {

    for( int supp : PruningTable.SUPPORTED )

      {

      PruningTable table = new PruningTable(mTablebase, level, supp);

      int size = mTablebase.getSize();

      StringBuilder sb = new StringBuilder();

      int num = 0;

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

        {

        if (table.contains(i))

          {

          if ((num % 10) == 0) sb.append("\n");

          num++;

          sb.append(i);

          sb.append(' ');

          }

        }

      android.util.Log.e("D", "numbers: " + sb);

      }

    }

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

  private void printQuats(int[] quats)

    {

    StringBuilder sb = new StringBuilder();

    for(int q : quats )

      {

      sb.append(' ');

      sb.append(q);

      }

    android.util.Log.e("D", "quats: "+sb);

    }

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

  public void test()

    {

    int[] p0 = {0,5,6,10, 2,3,11,9, 1,4,7,8};

    int[] q0 = TBDino6.getQuatsFromPerm(p0);

    int index0 = getIndex(q0);

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

    int[] p1 = {0,3,11,6,  7,8,10,2,  1,4,9,5};

    int[] q1 = TBDino6.getQuatsFromPerm(p1);

    int index1 = getIndex(q1);

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

    int[] p2 = {0,3,2,1,  7,6,5,4,  8,11,10,9};

    int[] q2 = TBDino6.getQuatsFromPerm(p2);

    int index2 = getIndex(q2);

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

    }

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

  private void printPerm(int index)

    {

    int[] perm11 = new int[11];

    TablebaseHelpers.getEvenPermutationFromNum(perm11,index);

    int[] perm = new int[12];

    for(int i=1; i<12; i++) perm[i] = perm11[i-1]+1;

    StringBuilder sb = new StringBuilder();

    sb.append(index);

    sb.append(" : ");

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

      {

      sb.append(' ');

      sb.append(perm[i]);

      }

    android.util.Log.e("D", "PERM: "+sb);

    }

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

  private void printQuat(int index)

    {

    int[] perm11 = new int[11];

    TablebaseHelpers.getEvenPermutationFromNum(perm11,index);

    int[] perm = new int[12];

    for(int i=1; i<12; i++) perm[i] = perm11[i-1]+1;

    int[] quats = TBDino6.getQuatsFromPerm(perm);

    StringBuilder sb = new StringBuilder();

    sb.append(index);

    sb.append(" : ");

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

      {

      sb.append(' ');

      sb.append(quats[i]);

      }

    android.util.Log.e("D", "QUATS: "+sb);

    }

}