TwistyPuzzleLib

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

// Copyright 2024 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.algphases;

import org.distorted.objectlib.algsolvers.MitmTable;

import org.distorted.objectlib.algsolvers.SolvedObject;

import org.distorted.objectlib.algsolvers.TargetQuats;

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

abstract public class Phase

{

  private static final int[] INDICES = {0};

  protected int[][] mCubitGroups;

  protected int mNumGroups;

  protected int mNumCubitsInThisPhase;

  protected int mNumCubits;

  protected TargetQuats mTargetQuats;

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

  Phase(SolvedObject object)

    {

    float[][] pos = object.getCubitPositions();

    mNumCubits = pos.length;

    }

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

  abstract public void prepareForSubphases();

  abstract public int[] findSolution(SolvedObject object, MitmTable table);

  abstract public boolean solveAnySubphase(SolvedObject object, MitmTable table, int[][] solution, int solIndex);

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

  public int numSubphases()

    {

    return mNumGroups;

    }

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

  public int whichSubPhase(int cubit)

    {

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

      for(int j : mCubitGroups[g])

        if( cubit==j ) return g;

    return -1;

    }

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

  public int[] endQuatIndices(SolvedObject object, int cubit)

    {

    return INDICES;

    }

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

  public void setTargetQuats(SolvedObject object, boolean[] inPreviousPhases)

    {

    int len = inPreviousPhases.length;

    int[][] target = new int[len][];

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

      {

      if( inPreviousPhases[c] ) target[c] = INDICES;

      else if( contains(c) )    target[c] = endQuatIndices(object,c);

      else                      target[c] = null;

      }

    mTargetQuats = new TargetQuats(target);

    }

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

  public boolean contains(int cubit)

    {

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

      for(int c : mCubitGroups[g])

        if( cubit==c ) return true;

    return false;

    }

}

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

// Copyright 2024 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.algphases;

import org.distorted.library.helpers.QuatHelper;

import org.distorted.library.type.Static4D;

import org.distorted.objectlib.algsolvers.SolvedObject;

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

public class PhaseCyclicOrie1 extends PhaseMitm

{

  private final int mCyclicQuat;

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

  public PhaseCyclicOrie1(SolvedObject object, int cubit, int quat)

    {

    super(object);

    Static4D[] objectQuats = object.getQuats();

    Static4D q = objectQuats[quat];

    double alpha = 2*Math.acos(q.get3());

    double numTurns = 2*Math.PI / alpha;

    mNumCubitsInThisPhase = (int)(numTurns+0.5f);

    mCubitGroups  = new int[1][mNumCubitsInThisPhase];

    mNumGroups = 1;

    mCyclicQuat = quat;

    float[][] positions = object.getCubitPositions();

    float[] pos = positions[cubit];

    float x = pos[0];

    float y = pos[1];

    float z = pos[2];

    float[] tmp = new float[4];

    mCubitGroups[0][0] = cubit;

    for(int c=1; c<mNumCubitsInThisPhase; c++)

      {

      QuatHelper.rotateVectorByQuat(tmp,x,y,z,1,q);

      x = tmp[0];

      y = tmp[1];

      z = tmp[2];

      mCubitGroups[0][c] = whichPosIsThis(positions,tmp);

      }

    }

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

  private int whichPosIsThis(float[][] positions, float[] pos)

    {

    int numPos = positions.length;

    float minErr = Float.MAX_VALUE;

    int ret=-1;

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

      {

      float[] curr = positions[i];

      float dx = curr[0] - pos[0];

      float dy = curr[1] - pos[1];

      float dz = curr[2] - pos[2];

      float err = dx*dx + dy*dy + dz*dz;

      if( err < minErr )

        {

        minErr = err;

        ret = i;

        }

      }

    return ret;

    }

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

  @Override

  public int[] endQuatIndices(SolvedObject object, int cubit)

    {

    int[] retQuats = new int[mNumCubitsInThisPhase];

    retQuats[0] = 0;

    retQuats[1] = mCyclicQuat;

    for(int i=2; i<mNumCubitsInThisPhase; i++)

      {

      retQuats[i] = object.getMultQuat(mCyclicQuat,retQuats[i-1]);

      }

    return retQuats;

    }

}

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

// Copyright 2024 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.algphases;

import org.distorted.library.helpers.QuatHelper;

import org.distorted.library.type.Static4D;

import org.distorted.objectlib.algsolvers.SolvedObject;

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

public class PhaseCyclicOrie2 extends PhaseMitm

{

  public PhaseCyclicOrie2(SolvedObject object, int cubit, int quat)

    {

    super(object);

    Static4D[] objectQuats = object.getQuats();

    Static4D q = objectQuats[quat];

    double alpha = 2*Math.acos(q.get3());

    double numTurns = 2*Math.PI / alpha;

    mNumCubitsInThisPhase = (int)(numTurns+0.5f);

    mCubitGroups  = new int[1][mNumCubitsInThisPhase];

    mNumGroups = 1;

    float[][] positions = object.getCubitPositions();

    float[] pos = positions[cubit];

    float x = pos[0];

    float y = pos[1];

    float z = pos[2];

    float[] tmp = new float[4];

    mCubitGroups[0][0] = cubit;

    for(int c=1; c<mNumCubitsInThisPhase; c++)

      {

      QuatHelper.rotateVectorByQuat(tmp,x,y,z,1,q);

      x = tmp[0];

      y = tmp[1];

      z = tmp[2];

      mCubitGroups[0][c] = whichPosIsThis(positions,tmp);

      }

    }

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

  private int whichPosIsThis(float[][] positions, float[] pos)

    {

    int numPos = positions.length;

    float minErr = Float.MAX_VALUE;

    int ret=-1;

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

      {

      float[] curr = positions[i];

      float dx = curr[0] - pos[0];

      float dy = curr[1] - pos[1];

      float dz = curr[2] - pos[2];

      float err = dx*dx + dy*dy + dz*dz;

      if( err < minErr )

        {

        minErr = err;

        ret = i;

        }

      }

    return ret;

    }

}

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

// Copyright 2024 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.algphases;

import org.distorted.library.helpers.QuatHelper;

import org.distorted.library.type.Static4D;

import org.distorted.objectlib.algsolvers.SolvedObject;

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

public class PhaseCyclicPerm1 extends PhaseMitm

{

  private final Static4D[] mObjectQuats;

  private final float[][] mPositions;

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

  public PhaseCyclicPerm1(SolvedObject object, int cubit, int quat)

    {

    super(object);

    Static4D[] objectQuats = object.getQuats();

    Static4D q = objectQuats[quat];

    double alpha = 2*Math.acos(q.get3());

    double numTurns = 2*Math.PI / alpha;

    mNumCubitsInThisPhase = (int)(numTurns+0.5f);

    mCubitGroups  = new int[1][mNumCubitsInThisPhase];

    mNumGroups = 1;

    mObjectQuats = objectQuats;

    float[][] positions = object.getCubitPositions();

    mPositions = positions;

    float[] pos = positions[cubit];

    float x = pos[0];

    float y = pos[1];

    float z = pos[2];

    float[] tmp = new float[4];

    mCubitGroups[0][0] = cubit;

    for(int c=1; c<mNumCubitsInThisPhase; c++)

      {

      QuatHelper.rotateVectorByQuat(tmp,x,y,z,1,q);

      x = tmp[0];

      y = tmp[1];

      z = tmp[2];

      mCubitGroups[0][c] = whichPosIsThis(positions,tmp);

      }

    }

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

  private int whichPosIsThis(float[][] positions, float[] pos)

    {

    int numPos = positions.length;

    float minErr = Float.MAX_VALUE;

    int ret=-1;

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

      {

      float[] curr = positions[i];

      float dx = curr[0] - pos[0];

      float dy = curr[1] - pos[1];

      float dz = curr[2] - pos[2];

      float err = dx*dx + dy*dy + dz*dz;

      if( err < minErr )

        {

        minErr = err;

        ret = i;

        }

      }

    return ret;

    }

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

  @Override

  public int[] endQuatIndices(SolvedObject object, int cubit)

    {

    float[] thisPos = mPositions[cubit];

    int numQuats = mObjectQuats.length;

    int numGoodQuats = 0;

    int[] tmpQuats = new int[numQuats];

    float[] tmp = new float[4];

    float x = thisPos[0];

    float y = thisPos[1];

    float z = thisPos[2];

    final float MAX_ERROR = 0.01f;

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

      {

      QuatHelper.rotateVectorByQuat(tmp,x,y,z,1,mObjectQuats[q]);

      float dx = tmp[0] - x;

      float dy = tmp[1] - y;

      float dz = tmp[2] - z;

      float err = dx*dx + dy*dy + dz*dz;

      if( err < MAX_ERROR )

        {

        numGoodQuats++;

        tmpQuats[q] = 1;

        }

      }

    int[] ret = new int[numGoodQuats];

    int index = 0;

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

      if( tmpQuats[q]==1 ) ret[index++] = q;

    return ret;

    }

}

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

// Copyright 2024 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.algphases;

import org.distorted.library.helpers.QuatHelper;

import org.distorted.library.type.Static4D;

import org.distorted.objectlib.algsolvers.SolvedObject;

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

public class PhaseCyclicPerm2 extends PhaseMitm

{

  public PhaseCyclicPerm2(SolvedObject object, int cubit, int quat)

    {

    super(object);

    Static4D[] objectQuats = object.getQuats();

    Static4D q = objectQuats[quat];

    double alpha = 2*Math.acos(q.get3());

    double numTurns = 2*Math.PI / alpha;

    mNumCubitsInThisPhase = (int)(numTurns+0.5f);

    mCubitGroups  = new int[1][mNumCubitsInThisPhase];

    mNumGroups = 1;

    float[][] positions = object.getCubitPositions();

    float[] pos = positions[cubit];

    float x = pos[0];

    float y = pos[1];

    float z = pos[2];

    float[] tmp = new float[4];

    mCubitGroups[0][0] = cubit;

    for(int c=1; c<mNumCubitsInThisPhase; c++)

      {

      QuatHelper.rotateVectorByQuat(tmp,x,y,z,1,q);

      x = tmp[0];

      y = tmp[1];

      z = tmp[2];

      mCubitGroups[0][c] = whichPosIsThis(positions,tmp);

      }

    }

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

  private int whichPosIsThis(float[][] positions, float[] pos)

    {

    int numPos = positions.length;

    float minErr = Float.MAX_VALUE;

    int ret=-1;

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

      {

      float[] curr = positions[i];

      float dx = curr[0] - pos[0];

      float dy = curr[1] - pos[1];

      float dz = curr[2] - pos[2];

      float err = dx*dx + dy*dy + dz*dz;

      if( err < minErr )

        {

        minErr = err;

        ret = i;

        }

      }

    return ret;

    }

}

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

// Copyright 2024 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.algphases;

import org.distorted.objectlib.algsolvers.MitmTable;

import org.distorted.objectlib.algsolvers.SolvedObject;

import org.distorted.objectlib.algsolvers.TargetQuats;

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

abstract public class PhaseMitm extends Phase

{

  private final static int MAX_MEMORY    = 6*1024*1024;  // 6MB max for the MitM table

  private final static double MAX_SEARCH = 10000000.0;   // max 10mln positions back-searched

  private boolean[] mSolved;

  private int[] mWhichSubphase;

  private int mForwardDepth, mBackwardDepth;

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

  PhaseMitm(SolvedObject object)

    {

    super(object);

    }

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

// Only attempt to find solutions which are not longer than maxlen; if not found, return null.

// Otherwise, return an array of moves; each move is an index to the MaveTable (see branchingFactor!)

//

// Algorithm:

// Meet in the Middle: first, do a depth-first search and remember each position in a table; depth of

// this search - until we fill out no more than MAX_MEMORY in the table.

// Then, from each end position (in general there can be many because in many phases there are many

// valid endQuats for a given cubit) do a back-search and try to reach any of the positions from the

// table.

  private int[] solve(SolvedObject object, MitmTable table, int depth)

    {

    float tmp = ((float)(mForwardDepth*depth))/(mForwardDepth+mBackwardDepth);

    int tmpForward = (int)Math.ceil(tmp);

    int tmpBackward= depth-tmpForward;

    table.build(object,tmpForward);

    return table.tryReaching(object,mTargetQuats,tmpBackward,tmpForward);

    }

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

  private int prepareForSubPhase(SolvedObject object, MitmTable table)

    {

    table.prepareForSubPhase(mTargetQuats);

    int bytesPerEntry = table.getBytesPerEntry();

    int branchingFactor = object.getBranchingFactor();

    mForwardDepth  = computeForwardDepth(bytesPerEntry,branchingFactor);

    mBackwardDepth = computeBackwardDepth(branchingFactor);

    return mForwardDepth+mBackwardDepth;

    }

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

  private int computeForwardDepth(int bytesPerEntry, int branchingFactor)

    {

    int numEntries = MAX_MEMORY/bytesPerEntry;

    double maxDepth = Math.log(numEntries) / Math.log(branchingFactor);

    return (int)maxDepth;

    }

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

// how deep we can search our tree of moves 'backward' (from any one of the positions described by

// 'endQuats')

  private int computeBackwardDepth(int branchingFactor)

    {

    int multiplier = mTargetQuats.computeNumCombinations();

    double maxDepth = Math.log(MAX_SEARCH/multiplier) / Math.log(branchingFactor);

    return (int)maxDepth;

    }

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

// Find solution and modify the non-null initQuats to match the situation after applying it.

  private int[] findSol(SolvedObject object, MitmTable table, int depth)

    {

    int[] s = solve(object,table,depth);

    if( s!=null )

      {

      int len = s.length;

      for(int m=1; m<len; m++) object.makeMove(s[m]);

      }

    return s;

    }

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

  @Override

  public void prepareForSubphases()

    {

    mSolved = new boolean[mNumGroups];

    mWhichSubphase = new int[mNumCubits];

    for(int c=0; c<mNumCubits; c++) mWhichSubphase[c] = whichSubPhase(c);

    for(int s=0; s<mNumGroups; s++) mSolved[s] = false;

    }

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

// a) find solution moves which take us from 'initQuats' position to a position which satisfies the

//    'endQuats' criteria

// b) overwrite 'initQuats' with the found position

// c) return solution moves

//

// Of course this works only if there exists a solution with reasonable length (10 moves?) so we

// need to define our phases accurately.

//

// initQuats: quats of the cubits at the start of the phase. Index table to mObjectQuats.

// endQuats: describes what the quats should be at the end of the phase.

// If endQuat[i]==null, then this mean we do not care about the state of cubit i.

// Otherwise, the cubit must end up in state described by one of the ints from array 'endQuats[i]'.

//

// Here we try to find a single solution in one phase, i.e. solve at once all 'endQuats'.

// (example: the white cross phase of the beginner's 3x3 - all four edges solved at once)

  @Override

  public int[] findSolution(SolvedObject object, MitmTable table)

    {

    int maxdepth = prepareForSubPhase(object,table);

    for(int l=0; l<=maxdepth; l++)

      {

      int[] ret = findSol(object,table,l);

      if( ret!=null ) return ret;

      }

    return null;

    }

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

  @Override

  public boolean solveAnySubphase( SolvedObject object, MitmTable table, int[][] solution, int subPhase)

    {

    int maxDepth = 0;

    TargetQuats tmp = new TargetQuats(mTargetQuats);

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

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

        if( !mSolved[g] )

          {

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

            {

            // -1 means that the cubit doesn't belong to the current phase. Cubits belonging to

            // the next phase already have their targetQuats set to null (see Phase.setTargetQuats)

            // Here we set to null (mark that we do not care about) the quats of all cubits which

            // belong to the current phase and haven't been solved yet (except the current subphase!).

            int sp = mWhichSubphase[q];

            mTargetQuats.set( (sp==-1 || sp==g || mSolved[sp]) ? tmp : null , q);

            }

          maxDepth = prepareForSubPhase(object,table);

          solution[subPhase] = findSol(object,table,d);

          if( solution[subPhase]!=null )

            {

            mTargetQuats.set(tmp);

            mSolved[g] = true;

            return true;

            }

          }

    mTargetQuats.set(tmp);

    return false;

    }

}

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

// Copyright 2024 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.algphases;

import org.distorted.objectlib.algsolvers.SolvedObject;

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

public class PhaseNotCyclic extends PhaseMitm

{

  public PhaseNotCyclic(SolvedObject object, int[][] cubitgroups)

    {

    super(object);

    mCubitGroups = cubitgroups;

    mNumGroups = cubitgroups.length;

    int numCubits = 0;

    for(int g=0; g<mNumGroups; g++) numCubits += mCubitGroups[g].length;

    mNumCubitsInThisPhase = numCubits;

    }

}

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

// Copyright 2024 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.algphases;

import org.distorted.objectlib.algsolvers.MitmTable;

import org.distorted.objectlib.algsolvers.MoveRegex;

import org.distorted.objectlib.algsolvers.SolvedObject;

import org.distorted.objectlib.algsolvers.TargetQuats;

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

public class PhaseRegex extends Phase

{

  private final MoveRegex mRegex;

  private final boolean[] mSolved;

  private final int[][] mMoves;

  private final int[][] mBasicAngles;

  private int[] mWhichSubphase;

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

  public PhaseRegex(SolvedObject object, String regex, int[][] cubitgroups)

    {

    super(object);

    mCubitGroups = cubitgroups;

    mNumGroups = cubitgroups.length;

    mRegex = new MoveRegex(object,regex);

    mMoves = object.getMoveTable();

    mBasicAngles = object.getBasicAngles();

    int numCubits = 0;

    for(int g=0; g<mNumGroups; g++) numCubits += mCubitGroups[g].length;

    mNumCubitsInThisPhase = numCubits;

    mSolved = new boolean[mNumGroups];

    }

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

  private int findMove(int ax, int row, int angle)

    {

    int numMoves = mMoves.length;

    for(int m=0; m<numMoves; m++)

      {

      int[] move = mMoves[m];

      if( move[0]==ax && move[1]==row && move[2]==angle )

        return m;

      }

    return -1;

    }

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

  private int[] collapseMoves(int[] moves, int start, int end)

    {

    int numCut = end-start;

    int len = moves.length;

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

    ret[0] = len-numCut-1;

    int index=1;

    for(int i=1; i<start; i++) ret[index++] = moves[i];

    for(int i=end; i<len; i++) ret[index++] = moves[i];

    return ret;

    }

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

  private int[] simplifyOnce(int[] moves)

    {

    int len = moves.length;

    int start, end;

    for(start=1; start<len; start++)

      {

      int[] m1 = mMoves[moves[start]];

      int totalAngle = m1[2];

      int ax = m1[0];

      int row= m1[1];

      for(end=start+1; end<len; end++)

        {

        int[] m2 = mMoves[moves[end]];

        if( ax!=m2[0] || row!=m2[1] ) break;

        totalAngle += m2[2];

        }

      if( end>start+1 )

        {

        int basicAngle = mBasicAngles[ax][row];

        totalAngle %= basicAngle;

        if( totalAngle> basicAngle/2 ) totalAngle -= basicAngle;

        if( totalAngle<-basicAngle/2 ) totalAngle += basicAngle;

        if( totalAngle==0 )

          {

          return collapseMoves(moves,start,end);

          }

        else

          {

          moves[start] = findMove(ax,row,totalAngle);

          return collapseMoves(moves,start+1,end);

          }

        }

      }

    return moves;

    }

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

  private int[] simplify(int[] moves)

    {

    int lenB, lenA;

    do

      {

      lenB = moves.length;

      moves = simplifyOnce(moves);

      lenA = moves.length;

      }

    while(lenB>lenA);

    return moves;

    }

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

  public void prepareForSubphases()

    {

    mWhichSubphase = new int[mNumCubits];

    for(int c=0; c<mNumCubits; c++) mWhichSubphase[c] = whichSubPhase(c);

    for(int s=0; s<mNumGroups; s++) mSolved[s] = false;

    }

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

// take the object, the regex and try to reach one of the mEndQuats

  public int[] findSolution(SolvedObject object, MitmTable table)

    {

    int[] moveSeq = mRegex.getFirst();

    int[] quats = object.getCopiedCubitQuats();

    do

      {

      int numMoves = (moveSeq==null ? 0 : moveSeq.length);

      for(int m=1; m<numMoves; m++) object.makeMove(moveSeq[m]);

      int[] qts = object.getCubitQuats();

      boolean solved = mTargetQuats.matchesQuats(qts);

      object.setUpStartingQuats(quats);

      if( solved ) return simplify(moveSeq);

      moveSeq = mRegex.getNext();

      }

    while( moveSeq!=null );

    return null;

    }

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

  public boolean solveAnySubphase(SolvedObject object, MitmTable table, int[][] solution, int solIndex)

    {

    TargetQuats tmp = new TargetQuats(mTargetQuats);

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

      if( !mSolved[g] )

        {

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

          {

          // -1 means that the cubit belongs to the previous (or next) phase. Cubits belonging to the

          // next phase already have their endQuats set to null (see PhasedSolver.figureOutEndQuatIndices)

          // Here we set to null (i.e. - mark that we do not care about) the quats of all cubits which

          // belong to the current phase and haven't been solved yet (except the current subphase!).

          int sp = mWhichSubphase[q];

          mTargetQuats.set( (sp==-1 || sp==g || mSolved[sp]) ? tmp : null , q);

          }

        solution[solIndex] = findSolution(object,table);

        if( solution[solIndex]!=null )

          {

          mTargetQuats.set(tmp);

          mSolved[g] = true;

          return true;

          }

        }

    mTargetQuats.set(tmp);

    return false;

    }

}

public class MitmTable

  public MitmTable(int numCubits, int numQuats)

  public static String getQuatString(int[] quats)

  public static String getMultiQuatString(int[][] quats)

  public static String getSigString(byte[] sig)

  public int getBytesPerEntry()

  public void prepareForSubPhase(TargetQuats quats)

  public void build(SolvedObject object, int depth)

      int branchingFactor = object.getBranchingFactor();

      buildRecursive(object,branchingFactor,-1,depth);

  public int[] tryReaching(SolvedObject object, TargetQuats target, int lenb, int lenf)

    int branching = object.getBranchingFactor();

      byte[] reached = tryReachingRecursive(object,branching,lenb,backward);

        int numMoves = reachForward(object,reached,forward,lenf);

  private byte[] tryReachingRecursive(SolvedObject object, int branching, int len, int[] ret)

      for(int m=0; m<branching; m++)

        if( object.movesDontClash(m,previousMove) )

          {

          object.backMove(m);

          ret[len-1] = m;

          byte[] reached = tryReachingRecursive(object,branching,len-1,ret);

          object.makeMove(m);

          if( reached!=null ) return reached;

  private int reachForward(SolvedObject object, byte[] signature, int[] ret, int len)

      int branching = object.getBranchingFactor();

      for(int m=0; m<branching; m++)

        object.makeMove(m);

        ret[0] = m;

        int numMoves = reachForwardRecursive(object,quats,ret,1,len-1);

        object.backMove(m);

        if( numMoves>=0 ) return numMoves+1;

  private int reachForwardRecursive(SolvedObject object, int[] quats, int[] ret, int index, int len)

      int branching = object.getBranchingFactor();

      int previousM = ret[index-1];

      for(int m=0; m<branching; m++)

        if(object.movesDontClash(m,previousM) )

          {

          object.makeMove(m);

          ret[index] = m;

          int numMoves = reachForwardRecursive(object,quats,ret,index+1,len-1);

          object.backMove(m);

          if( numMoves>=0 ) return numMoves+1;

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

  private void buildRecursive(SolvedObject object, int branching, int previousMove, int depth)

    {

    int[] quats = object.getCubitQuats();

    byte[] signature = pack(quats);

    mData.add(signature);

    if( depth>0 )

      for(int m=0; m<branching; m++)

        if( object.movesDontClash(m,previousMove) )

          {

          object.makeMove(m);

          buildRecursive(object,branching,m,depth-1);

          object.backMove(m);

          }

    }

  MitmTableDataStructure()

    {

    mData = new HashSet<>();

    }

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

  void clear()

    {

    mData.clear();

    }

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

  boolean contains(byte[] bytes)

    {

    return mData.contains(new ByteArray(bytes));

    }

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

  void add(byte[] bytes)

    {

    mData.add(new ByteArray(bytes));

    }

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

// Copyright 2024 Leszek Koltunski                                                               //

//                                                                                               //

// This file is part of Magic Cube.                                                              //

//                                                                                               //

// Magic Cube is proprietary software licensed under an EULA which you should have received      //