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.objectlib.helpers.OperatingSystemInterface;

import java.io.ByteArrayOutputStream;

import java.io.IOException;

import java.io.InputStream;

import java.util.ArrayList;

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

public abstract class TablebasesPruning extends TablebasesAbstract

{

  private final int mGodsNumber;

  private PruningTable[] mHighTables;

  private PruningTable[] mMidTables;

  private int mLowestHigh, mHighestMid, mLowestMid, mMaxDistance;

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

  abstract int[] getMidPruningLevels();

  abstract int[] getHighPruningLevels();

  abstract int getGodsNumber();

  abstract boolean moveCanProceed(int lastA, int lastL, int currA, int currL);

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

  private PruningTable createPruningTable(OperatingSystemInterface os, int id)

    {

    InputStream stream = os.openLocalFile(id);

    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();

      return new PruningTable(data);

      }

    catch(IOException ex)

      {

      mInitialized = false;

      return null;

      }

    }

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

  public TablebasesPruning()

    {

    super();

    mGodsNumber = getGodsNumber();

    mInitialized = false;

    }

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

  public TablebasesPruning(OperatingSystemInterface os, int[] midIDs, int[] highIDs)

    {

    super();

    int mid = midIDs !=null ? midIDs.length  : 0;

    int high= highIDs!=null ? highIDs.length : 0;

    mMidTables = mid >0 ? new PruningTable[mid] : null;

    mHighTables= high>0 ? new PruningTable[high]: null;

    mGodsNumber = getGodsNumber();

    mInitialized = true;

    for(int i=0; i<mid ; i++) mMidTables[i] = createPruningTable(os,midIDs[i] );

    for(int i=0; i<high; i++) mHighTables[i]= createPruningTable(os,highIDs[i]);

    computeLowHigh();

    }

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

  public byte[][] getPacked()

    {

    if( !mInitialized )

      {

      int[] midLevels = getMidPruningLevels();

      int numMidLevels= midLevels!=null ? midLevels.length : 0;

      int[] highLevels = getHighPruningLevels();

      int numHighLevels= highLevels!=null ? highLevels.length : 0;

      int maxLevel = 0;

      if( highLevels!=null )

        {

        for( int l : highLevels )

          if( l>maxLevel ) maxLevel = l;

        }

      else

        {

        if( midLevels!=null )

          for( int l : midLevels )

            if( l>maxLevel ) maxLevel = l;

        }

      createTablebase(maxLevel);

      mMidTables = numMidLevels >0 ? new PruningTable[numMidLevels ] : null;

      mHighTables= numHighLevels>0 ? new PruningTable[numHighLevels] : null;

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

        mMidTables[i] = new PruningTable(mTablebase,midLevels[i]);

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

        mHighTables[i] = new PruningTable(mTablebase,highLevels[i]);

      computeLowHigh();

      mInitialized = true;

      }

    int midNum  = mMidTables !=null ? mMidTables.length  : 0;

    int highNum = mHighTables!=null ? mHighTables.length : 0;

    byte[][] data = new byte[midNum+highNum][];

    for(int i=0; i<midNum ; i++) data[i       ] = mMidTables[i].getPacked();

    for(int i=0; i<highNum; i++) data[i+midNum] = mHighTables[i].getPacked();

    return data;

    }

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

  private void computeLowHigh()

    {

    mLowestHigh = mGodsNumber+1;

    int numHigh = mHighTables==null ? 0 : mHighTables.length;

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

      {

      int level = mHighTables[i].getLevel();

      if( i==0 || level<mLowestHigh ) mLowestHigh=level;

      }

    mLowestMid = 0;

    mHighestMid= 0;

    int numMid = mMidTables==null ? 0 : mMidTables.length;

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

      {

      int level = mMidTables[i].getLevel();

      if( i==0 || level<mLowestMid  ) mLowestMid =level;

      if( i==0 || level>mHighestMid ) mHighestMid=level;

      }

    int maxHigh = (mLowestHigh-mHighestMid)/2;

    int maxMid  = mLowestMid/2;

    mMaxDistance = Math.max(maxHigh,maxMid);

    }

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

  public int traverseDownTable(int index, PruningTable[] tables, int tableIndex, int lastA, int lastR, int[] move, int[] tmpQuats)

    {

    int[] quats = getQuats(index);

    int numQuats = quats.length;

    move[0]=0;

    move[1]=0;

    move[2]=1;

    move[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    = move[0];

      int layer = move[1];

      int quat  = move[3];

      if( mRotatable[ax][layer] && moveCanProceed(lastA,lastR,move[0],move[1]) )

        {

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

        if( tableIndex>0 )

          {

          if( tables[tableIndex-1].contains(childIndex) ) return childIndex;

          }

        else if( !tables[0].contains(childIndex) )

          {

          if( tables.length<=1 || !tables[1].contains(childIndex) ) return childIndex;

          }

        }

      getNextAxisLayerAngleQuat(move);

      }

    return -1;

    }

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

  private int traversePruningBlock(int[][] moves, PruningTable[] tables, int tableIndex, int index, int lastA, int lastR)

    {

    int movesIndex = 1;

    int[] move, tmpQuats = new int[mNumCubits];

    do

      {

      move  = moves[movesIndex++];

      index = traverseDownTable(index,tables,tableIndex,lastA,lastR,move,tmpQuats);

      lastA = move[0];

      lastR = move[1];

      tableIndex--;

      }

    while( tableIndex>=0 );

    return index;

    }

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

// ret: [0][] --> (new index,new depth,?,?) ; [1...N-1][] --> moves. (or null if index not in High)

  private int[][] traverseBlock(int index, PruningTable[] tables, int lastA, int lastR)

    {

    int num = (tables==null) ? 0 : tables.length;

    int tableIndex = -1;

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

      if( tables[i].contains(index) )

        {

        tableIndex = i;

        break;

        }

    if( tableIndex<0 ) return null;

    int[][] ret = new int[tableIndex+2][4];

    ret[0][1] = tables[0].getLevel()-1;

    ret[0][0] = traversePruningBlock(ret,tables,tableIndex,index,lastA, lastR);

    return ret;

    }

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

  private int midTablesContain(int index)

    {

    int num = mMidTables.length;

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

      if( mMidTables[i].contains(index) )

        return i;

    return -1;

    }

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

  private boolean jumpMidSolvedRecursive(int[] quats, int jump, int depth, int lastA, int lastR, int[][] solution)

    {

    int numQuats  = quats.length;

    int[] move    = solution[depth];

    int[] tmp     = new int[mNumCubits];

    int[][] rotRow= new int[mNumCubits][mNumAxis];

    move[0]=0;

    move[1]=0;

    move[2]=1;

    move[3]=1;

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

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

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

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

      {

      int ax    = move[0];

      int layer = move[1];

      int quat  = move[3];

      if( mRotatable[ax][layer] && moveCanProceed(lastA,lastR,ax,layer) )

        {

        int bitLayer = (1<<layer);

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

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

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

            {

            int currQuat = tmp[cubit];

            int newQuat = getMultQuat(quat,currQuat);

            tmp[cubit] = newQuat;

            }

        int childIndex = getIndex(tmp);

        if( isSolved(childIndex) )

          {

          solution[0][0] = childIndex;

          solution[0][1] = 0;

          return true;

          }

        int containingTable = midTablesContain(childIndex);

        if( containingTable>=0 )

          {

          solution[0][0] = childIndex;

          solution[0][1] = mMidTables[containingTable].getLevel();

          return true;

          }

        if( jump>1 && jumpMidSolvedRecursive(tmp, jump-1, depth+1, ax, layer, solution) )

          {

          return true;

          }

        }

      getNextAxisLayerAngleQuat(move);

      }

    return false;

    }

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

// ret: [0][] --> (new index,new depth,num moves,?) ; [1...N-1][] --> moves.

  private int[][] jumpToMidOrSolved(int index, int maxJump, int lastA, int lastR)

    {

    if( midTablesContain(index)>=0 ) return null;

    int[][] solution = new int[maxJump+1][4];

    int[] quats = getQuats(index);

    for(int i=1; i<=maxJump; i++)

      if( jumpMidSolvedRecursive(quats,i,1,lastA,lastR,solution) )

        {

        solution[0][2] = i;

        return solution;

        }

    return null;

    }

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

  private boolean jumpToSolvedRecursive(int[] quats, int jump, int depth, int lastA, int lastR, int[][] solution)

    {

    int numQuats = quats.length;

    int[] move   = solution[depth];

    int[] tmp    = new int[mNumCubits];

    int[][]rotRow= new int[mNumCubits][mNumAxis];

    move[0]=0;

    move[1]=0;

    move[2]=1;

    move[3]=1;

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

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

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

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

      {

      int ax    = move[0];

      int layer = move[1];

      int quat  = move[3];

      if( mRotatable[ax][layer] && moveCanProceed(lastA,lastR,move[0],move[1]) )

        {

        int bitLayer = (1<<layer);

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

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

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

            {

            int currQuat = tmp[cubit];

            int newQuat = getMultQuat(quat,currQuat);

            tmp[cubit] = newQuat;

            }

        int childIndex = getIndex(tmp);

        if( isSolved(childIndex) ) return true;

        if( jump>1 && jumpToSolvedRecursive(tmp, jump-1, depth+1, ax, layer, solution) ) return true;

        }

      getNextAxisLayerAngleQuat(move);

      }

    return false;

    }

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

// ret: [0][] --> (numMoves,old depth,?,?) ; [1...N-1][] --> moves.

  private int[][] jumpToSolved(int index, int maxJump, int lastA, int lastR)

    {

    int[][] solution = new int[maxJump+1][4];

    int[] quats = getQuats(index);

    for(int i=1; i<=maxJump; i++)

      if( jumpToSolvedRecursive(quats,i,1,lastA,lastR,solution) )

        {

        solution[0][0] = i;

        return solution;

        }

    return null;

    }

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

  private int[][] concatenateMoves(int[][] high, int[][] jump1, int[][] mid, int[][] jump2)

    {

    int len1 = high ==null ? 0 : high.length-1;

    int len2 = jump1==null ? 0 : jump1[0][2];

    int len3 = mid  ==null ? 0 : mid.length-1;

    int len4 = jump2==null ? 0 : jump2[0][0];

    int[][] moves = new int[len1+len2+len3+len4][];

    int index = 0;

    for(int i=0; i<len1; i++) moves[index++] =  high[i+1];

    for(int i=0; i<len2; i++) moves[index++] = jump1[i+1];

    for(int i=0; i<len3; i++) moves[index++] =   mid[i+1];

    for(int i=0; i<len4; i++) moves[index++] = jump2[i+1];

    convertMoves(moves);

    return moves;

    }

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

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

    {

    if( isSolved(index) ) return null;

    int lastA=-1, lastR=0;

    int[][] highMoves = traverseBlock(index,mHighTables,lastA,lastR);

    if( highMoves!=null )

      {

      index = highMoves[0][0];

      int len = highMoves.length;

      lastA = highMoves[len-1][0];

      lastR = highMoves[len-1][1];

      }

    int maxJump = Math.max(mLowestHigh-1-mHighestMid,mLowestMid/2);

    int[][] jump1Moves = jumpToMidOrSolved(index,maxJump,lastA,lastR);

    if( jump1Moves!=null )

      {

      if( isSolved(jump1Moves[0][0]) )

        {

        return concatenateMoves(null,jump1Moves,null,null);

        }

      if( jump1Moves[0][1]==mLowestMid )

        {

        int[][] jump2Moves = jumpToSolved(index,mLowestMid-1,-1,0);

        if( jump2Moves==null )

          {

          if( osi!=null ) osi.reportError("1 error jumping to Solved: "+index);

          return null;

          }

        return concatenateMoves(null,null,null,jump2Moves);

        }

      index = jump1Moves[0][0];

      int len = jump1Moves[0][2];

      lastA = jump1Moves[len][0];

      lastR = jump1Moves[len][1];

      }

    int[][] midMoves = traverseBlock(index,mMidTables,lastA,lastR);

    if( midMoves!=null )

      {

      index = midMoves[0][0];

      int len = midMoves.length;

      lastA = midMoves[len-1][0];

      lastR = midMoves[len-1][1];

      }

    else

      {

      if( osi!=null ) osi.reportError("error traversing mid Tables: "+index);

      return null;

      }

    int[][] jump2Moves = jumpToSolved(index,mLowestMid-1,lastA,lastR);

    if( jump2Moves==null )

      {

      if( osi!=null ) osi.reportError("2 error jumping to Solved: "+index);

      return null;

      }

    return concatenateMoves(highMoves,jump1Moves,midMoves,jump2Moves);

    }

/*

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

  private int getDistanceSingle(int[] quats)

    {

    int index = getIndex(quats);

    if( isSolved(index) ) return 0;

    int numMid = mMidTables.length;

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

      if( mMidTables[i].contains(index) ) return mLowestMid+i;

    if( mHighTables!=null )

      {

      int numHigh = mHighTables.length;

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

        if( mHighTables[i].contains(index) )

          {

          //android.util.Log.e("D", "high tables contain "+index);

          return mLowestHigh+i;

          }

      //android.util.Log.e("D", "high tables do not contain "+index);

      }

    return -1;

    }

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

  private int getDistance(int[] quats, int depth)

    {

    if( depth==0 ) return getDistanceSingle(quats);

    final int MAX = 1000;

    int[] data = new int[4];

    int numQuats = quats.length;

    int[] tmpQuats = new int[numQuats];

    int[][] rotRow = new int[mNumCubits][mNumAxis];

    int ret = MAX;

    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++)

        rotRow[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( rotRow[cubit][ax]==bitLayer )

            {

            int currQuat = tmpQuats[cubit];

            int newQuat = getMultQuat(quat,currQuat);

            tmpQuats[cubit] = newQuat;

            }

//android.util.Log.e("D", "getDistance: trying ax="+ax+" layer="+layer+" angle="+data[2]+" quat="+quat);

//TablebaseHelpers.displayTable(tmpQuats, "tmpQuats");

        int dist = getDistance(tmpQuats,depth-1);

//android.util.Log.e("D", "dist="+dist);

        if( dist>=0 && dist<ret ) ret=dist;

        }

      getNextAxisLayerAngleQuat(data);

      }

    return ret<MAX ? ret : -1;

    }

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

  private int getDepth(int[] quats, OperatingSystemInterface osi)

    {

    for(int d=0; d<=mMaxDistance; d++)

      {

//TablebaseHelpers.displayTable(quats, "quats, d="+d);

      int res = getDistance(quats,d);

//osi.reportError("getDistance res="+res+" d="+d);

      if( res>=0 )

        {

        if( res==0 ) return d;

        if( res==mLowestMid ) return mLowestMid-d;

        if( res>mLowestMid && res<mHighestMid )

          {

          if( d>0 )

            {

            osi.reportError("1 IMPOSSIBLE!!");

            return -1;

            }

          else return res;

          }

        if( res==mHighestMid ) return mHighestMid+d;

        if( res==mLowestHigh ) return mLowestHigh-d;

        if( res >mLowestHigh )

          {

          if( d>0 )

            {

            osi.reportError("2 IMPOSSIBLE!!");

            return -1;

            }

          else return res;

          }

        }

      }

    int index=getIndex(quats);

    osi.reportError("3 IMPOSSIBLE "+index);

    return -1;

    }

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

  public int[][] solutionNew(int index, int[] extra, OperatingSystemInterface osi)

    {

    int[] data = new int[4];

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

    int[] quats = getQuats(index);

    int depth = getDepth(quats,osi);

    int numQuats = quats.length;

    int[] tmpQuats = new int[numQuats];

    while( depth>0 )

      {

      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 newDepth = getDepth(tmpQuats,osi);

          if( newDepth==depth-1 )

            {

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

            moves.add(tmpMove);

            quats = new int[numQuats];

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

            depth = newDepth;

            found = true;

            }

          }

        getNextAxisLayerAngleQuat(data);

        }

      }

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

    return extraInfo(ret,extra);

    }

 */

}