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 java.io.ByteArrayOutputStream;

import java.io.IOException;

import java.io.InputStream;

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

public abstract class TablebasesPruning extends TablebasesAbstract

{

  private final int mGodsNumber;

  private boolean mInitialized;

  private PruningTable[] mHighTables;

  private PruningTable[] mMidTables;

  private int mLowestHigh, mHighestMid, mLowestMid;

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

  abstract int[] getMidPruningLevels();

  abstract int[] getHighPruningLevels();

  abstract int getGodsNumber();

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

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

  private PruningTable createPruningTable(Resources res, int id)

    {

    InputStream stream = res.openRawResource(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(Resources res, 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(res,midIDs[i] );

    for(int i=0; i<high; i++) mHighTables[i]= createPruningTable(res,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;

      }

    }

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

  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 )

      {

      android.util.Log.e("D", "block doesn't contain index "+index);

      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 jumpMidZeroRecursive(int index, int jump, int depth, int lastA, int lastR, int[][] solution)

    {

    int[] quats   = getQuats(index);

    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( childIndex==0 )

          {

          android.util.Log.e("D", "1 jumped to mid: index="+childIndex);

          solution[0][0] = childIndex;

          solution[0][1] = 0;

          return true;

          }

        int containingTable = midTablesContain(childIndex);

        if( containingTable>=0 )

          {

          android.util.Log.e("D", "2 jumped to mid: index="+childIndex);

          solution[0][0] = childIndex;

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

          return true;

          }

        if( jump>1 && jumpMidZeroRecursive(childIndex, jump-1, depth+1, ax, layer, solution) )

          {

          return true;

          }

        }

      getNextAxisLayerAngleQuat(move);

      }

    return false;

    }

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

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

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

    {

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

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

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

      if( jumpMidZeroRecursive(index,i,1,lastA,lastR,solution) )

        {

        solution[0][0] = i;

        return solution;

        }

    return null;

    }

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

  private boolean jumpZeroRecursive(int index, int jump, int depth, int lastA, int lastR, int[][] solution)

    {

    int[] quats  = getQuats(index);

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

/*

if( index==1719861 )

  {

StringBuilder sb4 = new StringBuilder();

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

    {

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

        {

        sb4.append(mRotRow[c][a]);

        sb4.append(' ');

        }

    sb4.append("\n");

    }

  android.util.Log.e("D", "1 rotRows= \n"+sb4 );

  }

*/

    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;

            }

/*

if( depth==1 && ax==1 && layer==1 && move[2]==3 )

  {

  StringBuilder sb2 = new StringBuilder();

  for(int i=0; i<8; i++) { sb2.append(' '); sb2.append(quats[i]); }

  android.util.Log.e("D", " quats= "+sb2 );

  StringBuilder sb3 = new StringBuilder();

  for(int i=0; i<8; i++) { sb3.append(' '); sb3.append(tmp[i]); }

  android.util.Log.e("D", " tmpQuats= "+sb3 );

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

  }

if( index==1719861 )

  {

StringBuilder sb4 = new StringBuilder();

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

    {

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

        {

        sb4.append(mRotRow[c][a]);

        sb4.append(' ');

        }

    sb4.append("\n");

    }

  android.util.Log.e("D", "2 rotRows= \n"+sb4 );

  }

*/

        int childIndex = getIndex(tmp);

        if( childIndex==0 ) return true;

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

        }

      getNextAxisLayerAngleQuat(move);

      }

    return false;

    }

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

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

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

    {

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

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

      if( jumpZeroRecursive(index,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][0];

    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)

    {

    if( index==0 ) 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 = jumpToMidOrZero(index,maxJump,lastA,lastR);

    if( jump1Moves!=null )

      {

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

        {

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

        }

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

        {

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

        if( jump2Moves==null ) throw new RuntimeException("1 error jumping to 0");

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

        }

      index = jump1Moves[0][0];

      int len = jump1Moves.length;

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

      lastR = jump1Moves[len-1][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 throw new RuntimeException("error traversing mid Tables");

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

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

    if( jump2Moves==null ) throw new RuntimeException("2 error jumping to 0");

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

    }

}