TwistyPuzzleLib

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

// Copyright 2021 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.scrambling;

import java.util.ArrayList;

import java.util.Random;

import org.distorted.objectlib.helpers.ObjectSignature;

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

public class ObjectScrambler

  {

  private final ScrambleState[] mStates;

  private final int mType;

  private final int mNumAxis;

  private final int[] mNumLayers;

  private final int[][] mAlgorithms;

  // type=0, i.e. main

  private int mCurrState;

  private int mAxisExcluded;

  private int[][] mScrambleTable;

  private int[] mNumOccurences;

  private int[] mResult;

  private int mCurrAlgorithm;

  private int mCurrStep;

  // type=1, i.e. the exception: Square-1

  private static final int BASIC_ANGLE = 12;

  private static final int LAST_SL = 0; // automatic rotations: last rot was a 'slash' i.e. along ROT_AXIS[1]

  private static final int LAST_UP = 1; // last rot was along ROT_AXIS[0], upper layer and forelast was a slash

  private static final int LAST_LO = 2; // last rot was along ROT_AXIS[0], lower layer and forelast was a slash

  private static final int LAST_UL = 3; // two last rots were along ROT_AXIS[0] (so the next must be a slash)

  private int[][] mPermittedAngles;

  private int[] mCornerQuat;

  private int mPermittedUp, mPermittedDo;

  private int[][] mBadCornerQuats;

  private int mLastRot;

  private int[][] mQuatMult;

  // type=2 , i.e. locally created bandaged cuboids

  private ArrayList<ScrambleStateBandagedCuboid> mStatesHistory;

  private BlacklistedSignatures mBlacklisted;

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

  public ObjectScrambler(int type, int numAxis, int[] numLayers, int[][] algorithms, int[][] edges)

    {

    mType       = type;

    mNumAxis    = numAxis;

    mNumLayers  = numLayers;

    mAlgorithms = algorithms;

    if( mType==0 )

      {

      mResult = new int[2];

      }

    if( edges!=null )

      {

      int numEdges = edges.length;

      mStates = new ScrambleState[numEdges];

      for(int i=0; i<numEdges; i++) mStates[i] = new ScrambleState(edges[i],algorithms);

      }

    else mStates = null;

    if( mType==1 )

      {

      mPermittedAngles = new int[2][BASIC_ANGLE];

      mCornerQuat = new int[8];

      mLastRot = LAST_SL;

      }

    }

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

  private void initializeScrambling()

    {

    if( mScrambleTable==null )

      {

      mScrambleTable = new int[mNumAxis][];

      }

    if( mNumOccurences==null )

      {

      int max=0;

      for (ScrambleState mState : mStates)

        {

        int tmp = mState.getTotal();

        if (max < tmp) max = tmp;

        }

      mNumOccurences = new int[max];

      }

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

      {

      int len = mNumLayers[i];

      mScrambleTable[i] = new int[len];

      for(int j=0; j<len; j++) mScrambleTable[i][j] = 0;

      }

    }

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

// PUBLIC API

  private void randomizeNewScramble0(int[][] scramble, Random rnd, int curr)

    {

    if( curr==0 )

      {

      mCurrState    = 0;

      mAxisExcluded =-1;

      initializeScrambling();

      }

    if( mCurrStep+6 <= mAlgorithms[mCurrAlgorithm].length )

      {

      mCurrStep += 3;

      }

    else

      {

      mStates[mCurrState].getRandom(rnd, mAlgorithms, mAxisExcluded, mScrambleTable, mNumOccurences, mResult);

      mCurrAlgorithm = mResult[0];

      mCurrState     = mResult[1];

      mCurrStep      = 0;

      }

    int[] algorithm = mAlgorithms[mCurrAlgorithm];

    scramble[curr][0] = algorithm[mCurrStep  ];

    scramble[curr][1] = algorithm[mCurrStep+1];

    scramble[curr][2] = algorithm[mCurrStep+2];

    mAxisExcluded = algorithm[0];

    }

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

// TYPE 1

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

// QUATS[i]*QUATS[j] = QUATS[QUAT_MULT[i][j]]

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

  void initializeQuatMult()

    {

    mQuatMult = new int[][]

      {

        {  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,},

        {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11,  0, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 12,},

        {  2,  3,  4,  5,  6,  7,  8,  9, 10, 11,  0,  1, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 12, 13,},

        {  3,  4,  5,  6,  7,  8,  9, 10, 11,  0,  1,  2, 15, 16, 17, 18, 19, 20, 21, 22, 23, 12, 13, 14,},

        {  4,  5,  6,  7,  8,  9, 10, 11,  0,  1,  2,  3, 16, 17, 18, 19, 20, 21, 22, 23, 12, 13, 14, 15,},

        {  5,  6,  7,  8,  9, 10, 11,  0,  1,  2,  3,  4, 17, 18, 19, 20, 21, 22, 23, 12, 13, 14, 15, 16,},

        {  6,  7,  8,  9, 10, 11,  0,  1,  2,  3,  4,  5, 18, 19, 20, 21, 22, 23, 12, 13, 14, 15, 16, 17,},

        {  7,  8,  9, 10, 11,  0,  1,  2,  3,  4,  5,  6, 19, 20, 21, 22, 23, 12, 13, 14, 15, 16, 17, 18,},

        {  8,  9, 10, 11,  0,  1,  2,  3,  4,  5,  6,  7, 20, 21, 22, 23, 12, 13, 14, 15, 16, 17, 18, 19,},

        {  9, 10, 11,  0,  1,  2,  3,  4,  5,  6,  7,  8, 21, 22, 23, 12, 13, 14, 15, 16, 17, 18, 19, 20,},

        { 10, 11,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 22, 23, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,},

        { 11,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 23, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,},

        { 12, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13,  0, 11, 10,  9,  8,  7,  6,  5,  4,  3,  2,  1,},

        { 13, 12, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14,  1,  0, 11, 10,  9,  8,  7,  6,  5,  4,  3,  2,},

        { 14, 13, 12, 23, 22, 21, 20, 19, 18, 17, 16, 15,  2,  1,  0, 11, 10,  9,  8,  7,  6,  5,  4,  3,},

        { 15, 14, 13, 12, 23, 22, 21, 20, 19, 18, 17, 16,  3,  2,  1,  0, 11, 10,  9,  8,  7,  6,  5,  4,},

        { 16, 15, 14, 13, 12, 23, 22, 21, 20, 19, 18, 17,  4,  3,  2,  1,  0, 11, 10,  9,  8,  7,  6,  5,},

        { 17, 16, 15, 14, 13, 12, 23, 22, 21, 20, 19, 18,  5,  4,  3,  2,  1,  0, 11, 10,  9,  8,  7,  6,},

        { 18, 17, 16, 15, 14, 13, 12, 23, 22, 21, 20, 19,  6,  5,  4,  3,  2,  1,  0, 11, 10,  9,  8,  7,},

        { 19, 18, 17, 16, 15, 14, 13, 12, 23, 22, 21, 20,  7,  6,  5,  4,  3,  2,  1,  0, 11, 10,  9,  8,},

        { 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22, 21,  8,  7,  6,  5,  4,  3,  2,  1,  0, 11, 10,  9,},

        { 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22,  9,  8,  7,  6,  5,  4,  3,  2,  1,  0, 11, 10,},

        { 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 10,  9,  8,  7,  6,  5,  4,  3,  2,  1,  0, 11,},

        { 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3,  2,  1,  0,}

      };

    }

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

// TYPE 1

  private boolean cornerIsUp(int index)

    {

    return ((index<4) ^ (mCornerQuat[index]>=12));

    }

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

// TYPE 1

  private boolean cornerIsLeft(int index)

    {

    int q = mCornerQuat[index];

    switch(index)

      {

      case 0:

      case 4: return ((q>=3 && q<= 7) || (q>=18 && q<=22));

      case 1:

      case 5: return ((q>=6 && q<=10) || (q>=15 && q<=19));

      case 2:

      case 6: return ((q==0 || q==1 || (q>=9 && q<=11)) || (q>=12 && q<=16));

      case 3:

      case 7: return ((q>=0 && q<=4) || (q==12 || q==13 || (q>=21 && q<=23)));

      }

    return false;

    }

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

// TYPE 1

  private boolean quatIsBad(int quatIndex, int corner)

    {

    if( mBadCornerQuats ==null )

      {

      // quat indices that make corner cubits bandage the puzzle.

      mBadCornerQuats = new int[][] { { 2, 8,17,23}, { 5,11,14,20} };

      }

    int index = (corner%2);

    return ( quatIndex== mBadCornerQuats[index][0] ||

             quatIndex== mBadCornerQuats[index][1] ||

             quatIndex== mBadCornerQuats[index][2] ||

             quatIndex== mBadCornerQuats[index][3]  );

    }

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

// TYPE 1

  private boolean isPermittedDo(int angle)

    {

    if( mQuatMult==null ) initializeQuatMult();

    for(int corner=0; corner<8; corner++)

      {

      if( !cornerIsUp(corner) )

        {

        int currQuat = mCornerQuat[corner];

        int finalQuat= mQuatMult[angle][currQuat];

        if( quatIsBad(finalQuat,corner) ) return false;

        }

      }

    return true;

    }

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

// TYPE 1

  private boolean isPermittedUp(int angle)

    {

    if( mQuatMult==null ) initializeQuatMult();

    for(int corner=0; corner<8; corner++)

      {

      if( cornerIsUp(corner) )

        {

        int currQuat = mCornerQuat[corner];

        int finalQuat= mQuatMult[angle][currQuat];

        if( quatIsBad(finalQuat,corner) ) return false;

        }

      }

    return true;

    }

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

// TYPE 1

  private void computePermittedAngles()

    {

    mPermittedDo = 0;

    for(int angle=0; angle<BASIC_ANGLE; angle++)

      {

      if( isPermittedDo(angle ) ) mPermittedAngles[0][mPermittedDo++] = angle;

      }

    mPermittedUp = 0;

    for(int angle=0; angle<BASIC_ANGLE; angle++)

      {

      if( isPermittedUp(angle ) ) mPermittedAngles[1][mPermittedUp++] = angle;

      }

    }

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

// TYPE 1

  private int getNextAngle(Random rnd, int layer)

    {

    int num = layer==0 ? mPermittedDo:mPermittedUp;

    int index = rnd.nextInt(num);

    int angle = mPermittedAngles[layer][index];

    return angle<BASIC_ANGLE/2 ? -angle : BASIC_ANGLE-angle;

    }

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

// TYPE 1

  private int getNextAngleNotZero(Random rnd, int layer)

    {

    int num = layer==0 ? mPermittedDo:mPermittedUp;

    int index = rnd.nextInt(num-1);

    int angle = mPermittedAngles[layer][index+1];

    return angle<BASIC_ANGLE/2 ? -angle : BASIC_ANGLE-angle;

    }

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

// TYPE 1

  private int makeQuat(int axis,int index)

    {

    if( axis==1 ) return 13;

    if( index<0 ) index+=12;

    return index;

    }

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

// TYPE 1

  private boolean cornerBelongs(int index, int axis, int layer)

    {

    if( axis==0 )

      {

      boolean up = cornerIsUp(index);

      return ((up && layer==2) || (!up && layer==0));

      }

    else

      {

      boolean le = cornerIsLeft(index);

      return ((le && layer==0) || (!le && layer==1));

      }

    }

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

// TYPE 1

  private void updateCornerQuats(int[] rotInfo)

    {

    if( mQuatMult==null ) initializeQuatMult();

    int axis = rotInfo[0];

    int layer= rotInfo[1];

    int index=-rotInfo[2];

    int quat = makeQuat(axis,index);

    for(int corner=0; corner<8; corner++)

      {

      if( cornerBelongs(corner,axis,layer) )

        {

        int curr = mCornerQuat[corner];

        mCornerQuat[corner] = mQuatMult[quat][curr];

        }

      }

    }

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

// TYPE 1

  private void randomizeNewScramble1(int[][] scramble, Random rnd, int curr)

    {

    int layer, nextAngle;

    if( curr==0 )

      {

      for(int corner=0; corner<8; corner++) mCornerQuat[corner] = 0;

      mLastRot = rnd.nextInt(4);

      computePermittedAngles();

      }

    switch(mLastRot)

      {

      case LAST_SL: layer = rnd.nextInt(2);

                    nextAngle = getNextAngle(rnd,layer);

                    if( nextAngle==0 )

                      {

                      layer = 1-layer;

                      nextAngle = getNextAngleNotZero(rnd,layer);

                      }

                    scramble[curr][0] = 0;

                    scramble[curr][1] = 2*layer;

                    scramble[curr][2] = nextAngle;

                    mLastRot = layer==0 ? LAST_LO : LAST_UP;

                    updateCornerQuats(scramble[curr]);

                    break;

      case LAST_LO:

      case LAST_UP: layer = mLastRot==LAST_LO ? 1:0;

                    nextAngle = getNextAngle(rnd,layer);

                    if( nextAngle!=0 )

                      {

                      scramble[curr][0] = 0;

                      scramble[curr][1] = 2*layer;

                      scramble[curr][2] = nextAngle;

                      updateCornerQuats(scramble[curr]);

                      mLastRot = LAST_UL;

                      }

                    else

                      {

                      scramble[curr][0] = 1;

                      scramble[curr][1] = rnd.nextInt(2);

                      scramble[curr][2] = 1;

                      mLastRot = LAST_SL;

                      updateCornerQuats(scramble[curr]);

                      computePermittedAngles();

                      }

                    break;

      case LAST_UL: scramble[curr][0] = 1;

                    scramble[curr][1] = rnd.nextInt(2);

                    scramble[curr][2] = 1;

                    mLastRot = LAST_SL;

                    updateCornerQuats(scramble[curr]);

                    computePermittedAngles();

                    break;

      }

    }

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

// TYPE 2

  private void buildMoveForced(int[][] scramble, Random rnd, int curr)

    {

    ScrambleStateBandagedCuboid currState = mStatesHistory.get(curr);

    int indexExcluded = curr>0 ? scramble[curr-1][0] : ScrambleStateBandagedCuboid.AXIS_NONE;

    int numMoves = currState.numMoves(indexExcluded);

    ObjectSignature signature;

    if( numMoves==0 )

      {

      indexExcluded = ScrambleStateBandagedCuboid.AXIS_NONE;

      numMoves = currState.numMoves(indexExcluded);

      }

    if( numMoves==0 )

      {

      scramble[curr][0] = 0;

      scramble[curr][1] = 0;

      scramble[curr][2] = 0;

      signature = currState.getSignature();

      }

    else

      {

      int randMove = rnd.nextInt(numMoves);

      int moveIndex = currState.getNthMove(randMove,indexExcluded);

      signature = currState.getMove(moveIndex);

      currState.fillOutScramble(scramble[curr],moveIndex);

      }

    ScrambleStateBandagedCuboid nextState = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted);

    mStatesHistory.add(nextState);

    }

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

// TYPE 2

  private boolean buildMove2Cons(int[][] scramble, Random rnd, int curr)

    {

    ScrambleStateBandagedCuboid currState = mStatesHistory.get(curr);

    boolean lock= (curr>=2 && scramble[curr-2][0]==scramble[curr-1][0] );

    int axisExcluded = lock ? scramble[curr-1][0] : ScrambleStateBandagedCuboid.AXIS_NONE;

    int layerExcluded= !lock && curr>=1 ? scramble[curr-1][1] : -1;

    int numMoves = currState.numMoves(axisExcluded,layerExcluded);

    while( numMoves==0 )

      {

      if( curr>0 )

        {

        mStatesHistory.remove(curr);

        ScrambleStateBandagedCuboid prevState = mStatesHistory.get(curr-1);

        ObjectSignature signature = currState.getSignature();

        prevState.removeMoves(signature);

        mBlacklisted.add(signature);

        boolean result = buildMove2Cons(scramble,rnd,curr-1);

        if( !result ) return false;

        currState = mStatesHistory.get(curr);

        lock= (curr>=2 && scramble[curr-2][0]==scramble[curr-1][0] );

        axisExcluded = lock ? scramble[curr-1][0] : ScrambleStateBandagedCuboid.AXIS_NONE;

        layerExcluded= lock ? -1 : scramble[curr-1][1];

        numMoves = currState.numMoves(axisExcluded,layerExcluded);

        }

      else return false;

      }

    int randMove = rnd.nextInt(numMoves);

    int moveIndex = currState.getNthMove(randMove,axisExcluded,layerExcluded);

    ObjectSignature signature = currState.getMove(moveIndex);

    currState.fillOutScramble(scramble[curr],moveIndex);

    ScrambleStateBandagedCuboid nextState = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted);

    mStatesHistory.add(nextState);

    return true;

    }

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

// TYPE 2

  private boolean buildMove1Cons(int[][] scramble, Random rnd, int curr)

    {

    ScrambleStateBandagedCuboid currState = mStatesHistory.get(curr);

    int axisExcluded = curr>=1 ? scramble[curr-1][0] : ScrambleStateBandagedCuboid.AXIS_NONE;

    int numMoves = currState.numMoves(axisExcluded);

    while( numMoves==0 )

      {

      if( curr>0 )

        {

        mStatesHistory.remove(curr);

        ScrambleStateBandagedCuboid prevState = mStatesHistory.get(curr-1);

        ObjectSignature signature = currState.getSignature();

        prevState.removeMoves(signature);

        mBlacklisted.add(signature);

        boolean result = buildMove1Cons(scramble,rnd,curr-1);

        if( !result ) return false;

        currState = mStatesHistory.get(curr);

        axisExcluded = scramble[curr-1][0];

        numMoves = currState.numMoves(axisExcluded);

        }

      else

        {

        return false;

        }

      }

    int randMove = rnd.nextInt(numMoves);

    int moveIndex = currState.getNthMove(randMove,axisExcluded);

    ObjectSignature signature = currState.getMove(moveIndex);

    currState.fillOutScramble(scramble[curr],moveIndex);

    ScrambleStateBandagedCuboid nextState = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted);

    mStatesHistory.add(nextState);

    return true;

    }

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

// TYPE 2

  private void initializeType2Scrambling(int[][] scramble, Random rnd, int total, ObjectSignature signature)

    {

    if( mStatesHistory==null ) mStatesHistory = new ArrayList<>();

    else                       mStatesHistory.clear();

    if( mBlacklisted==null ) mBlacklisted = BlacklistedSignatures.getInstance();

    else                     mBlacklisted.clear();

    ScrambleStateBandagedCuboid state = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted);

    mStatesHistory.add(state);

    boolean success = true;

    for(int curr=0; curr<total; curr++)

      {

      boolean result = buildMove1Cons(scramble,rnd,curr);

      if( !result )

        {

        success = false;

        break;

        }

      }

    if( !success )

      {

      success = true;

      mStatesHistory.clear();

      mBlacklisted.clear();

      state = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted);

      mStatesHistory.add(state);

      for(int curr=0; curr<total; curr++)

        {

        boolean result = buildMove2Cons(scramble,rnd,curr);

        if( !result )

          {

          success = false;

          break;

          }

        }

      }

    if( !success )

      {

      mStatesHistory.clear();

      mBlacklisted.clear();

      state = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted);

      mStatesHistory.add(state);

      for(int curr=0; curr<total; curr++)

        {

        buildMoveForced(scramble,rnd,curr);

        }

      }

    }

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

// TYPE 2   (locally-created bandaged cuboids)

  private void randomizeNewScramble2(int[][] scramble, Random rnd, int curr, int total, ObjectSignature signature)

    {

    if( curr==0 ) initializeType2Scrambling(scramble,rnd,total,signature);

    }

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

// PUBLIC API

  public void randomizeNewScramble(int[][] scramble, Random rnd, int curr, int total, ObjectSignature signature)

    {

    switch(mType)

      {

      case 0: randomizeNewScramble0(scramble, rnd, curr); break;

      case 1: randomizeNewScramble1(scramble, rnd, curr); break;

      case 2: randomizeNewScramble2(scramble, rnd, curr, total, signature); break;

      }

    }

  }