TwistyPuzzleLib

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

// Copyright 2022 Leszek Koltunski                                                               //

//                                                                                               //

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

//                                                                                               //

// Magic Cube is free software: you can redistribute it and/or modify                            //

// it under the terms of the GNU General Public License as published by                          //

// the Free Software Foundation, either version 2 of the License, or                             //

// (at your option) any later version.                                                           //

//                                                                                               //

// Magic Cube is distributed in the hope that it will be useful,                                 //

// but WITHOUT ANY WARRANTY; without even the implied warranty of                                //

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the                                 //

// GNU General Public License for more details.                                                  //

//                                                                                               //

// You should have received a copy of the GNU General Public License                             //

// along with Magic Cube.  If not, see <http://www.gnu.org/licenses/>.                           //

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

package org.distorted.objectlib.scrambling;

import java.util.ArrayList;

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

// Producer of the ScrambleStateGraph for any bandaged 3x3x3.

public class ScrambleStateBandaged3x3

{

  private static final long INVALID_MOVE = -1;

  private static final int NUM_MOVES = 27;

  private static final int AXIS_X = 0;

  private static final int AXIS_Y = 1;

  private static final int AXIS_Z = 2;

  private static final int LAYER_L = 0;

  private static final int LAYER_M = 1;

  private static final int LAYER_R = 2;

  private long mID;

  private int mDistance;

  private final long[] mMoves;

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

  private ScrambleStateBandaged3x3(long id)

    {

    mDistance = -1;

    mID = id;

    mMoves = createMoves(mID);

    }

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

  private long getID()

    {

    return mID;

    }

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

  private void setID(long id)

    {

    mID = id;

    }

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

  private long getMove(int index)

    {

    return (index>=0 && index<NUM_MOVES) ? mMoves[index] : INVALID_MOVE;

    }

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

  private int numAxis()

    {

    int num = 0;

    if( mMoves[ 0]!=INVALID_MOVE || mMoves[ 1]!=INVALID_MOVE || mMoves[ 2]!=INVALID_MOVE ||

        mMoves[ 3]!=INVALID_MOVE || mMoves[ 4]!=INVALID_MOVE || mMoves[ 5]!=INVALID_MOVE ||

        mMoves[ 6]!=INVALID_MOVE || mMoves[ 7]!=INVALID_MOVE || mMoves[ 8]!=INVALID_MOVE   ) num++;

    if( mMoves[ 9]!=INVALID_MOVE || mMoves[10]!=INVALID_MOVE || mMoves[11]!=INVALID_MOVE ||

        mMoves[12]!=INVALID_MOVE || mMoves[13]!=INVALID_MOVE || mMoves[14]!=INVALID_MOVE ||

        mMoves[15]!=INVALID_MOVE || mMoves[16]!=INVALID_MOVE || mMoves[17]!=INVALID_MOVE   ) num++;

    if( mMoves[18]!=INVALID_MOVE || mMoves[19]!=INVALID_MOVE || mMoves[20]!=INVALID_MOVE ||

        mMoves[21]!=INVALID_MOVE || mMoves[22]!=INVALID_MOVE || mMoves[23]!=INVALID_MOVE ||

        mMoves[24]!=INVALID_MOVE || mMoves[25]!=INVALID_MOVE || mMoves[26]!=INVALID_MOVE   ) num++;

    return num;

    }

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

  private void setMove(int index, long newMove)

    {

    if( index>=0 && index<NUM_MOVES ) mMoves[index] = newMove;

    }

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

  private String formatMoves()

    {

    String x = getTable( 0);

    String y = getTable( 9);

    String z = getTable(18);

    return "    new ScrambleState( new int[][] { "+x+", "+y+", "+z+" } ),";

    }

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

  private String getTable(int index)

    {

    long m0 = getMove(index  );

    long m1 = getMove(index+1);

    long m2 = getMove(index+2);

    long m3 = getMove(index+3);

    long m4 = getMove(index+4);

    long m5 = getMove(index+5);

    long m6 = getMove(index+6);

    long m7 = getMove(index+7);

    long m8 = getMove(index+8);

    String ret = "";

    if( m0!=INVALID_MOVE ) ret += formatRet(ret,0,-1,m0);

    if( m1!=INVALID_MOVE ) ret += formatRet(ret,0, 2,m1);

    if( m2!=INVALID_MOVE ) ret += formatRet(ret,0, 1,m2);

    if( m3!=INVALID_MOVE ) ret += formatRet(ret,1,-1,m3);

    if( m4!=INVALID_MOVE ) ret += formatRet(ret,1, 2,m4);

    if( m5!=INVALID_MOVE ) ret += formatRet(ret,1, 1,m5);

    if( m6!=INVALID_MOVE ) ret += formatRet(ret,2,-1,m6);

    if( m7!=INVALID_MOVE ) ret += formatRet(ret,2, 2,m7);

    if( m8!=INVALID_MOVE ) ret += formatRet(ret,2, 1,m8);

    return formatL("{" + ret + "}");

    }

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

  private int[] getMoves(int index)

    {

    int numValid = 0;

    for(int i=index; i<index+9; i++) if( mMoves[i]!=INVALID_MOVE ) numValid++;

    int[] ret = new int[3*numValid];

    long m0 = getMove(index  );

    long m1 = getMove(index+1);

    long m2 = getMove(index+2);

    long m3 = getMove(index+3);

    long m4 = getMove(index+4);

    long m5 = getMove(index+5);

    long m6 = getMove(index+6);

    long m7 = getMove(index+7);

    long m8 = getMove(index+8);

    int pointer=0;

    if( m0!=INVALID_MOVE ) { ret[pointer]=0; ret[pointer+1]=-1; ret[pointer+2]= (int)m0; pointer+=3; }

    if( m1!=INVALID_MOVE ) { ret[pointer]=0; ret[pointer+1]= 2; ret[pointer+2]= (int)m1; pointer+=3; }

    if( m2!=INVALID_MOVE ) { ret[pointer]=0; ret[pointer+1]= 1; ret[pointer+2]= (int)m2; pointer+=3; }

    if( m3!=INVALID_MOVE ) { ret[pointer]=1; ret[pointer+1]=-1; ret[pointer+2]= (int)m3; pointer+=3; }

    if( m4!=INVALID_MOVE ) { ret[pointer]=1; ret[pointer+1]= 2; ret[pointer+2]= (int)m4; pointer+=3; }

    if( m5!=INVALID_MOVE ) { ret[pointer]=1; ret[pointer+1]= 1; ret[pointer+2]= (int)m5; pointer+=3; }

    if( m6!=INVALID_MOVE ) { ret[pointer]=2; ret[pointer+1]=-1; ret[pointer+2]= (int)m6; pointer+=3; }

    if( m7!=INVALID_MOVE ) { ret[pointer]=2; ret[pointer+1]= 2; ret[pointer+2]= (int)m7; pointer+=3; }

    if( m8!=INVALID_MOVE ) { ret[pointer]=2; ret[pointer+1]= 1; ret[pointer+2]= (int)m8; pointer+=3; }

    return ret;

    }

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

  private ScrambleState produceScrambleState()

    {

    int[] xMoves = getMoves(0);

    int[] yMoves = getMoves(9);

    int[] zMoves = getMoves(18);

    int[][] moves = { xMoves,yMoves,zMoves };

    return new ScrambleState( moves );

    }

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

// STATIC STUFF

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

  public static ScrambleState[] computeGraph(long id)

    {

    ScrambleStateBandaged3x3 bsg = new ScrambleStateBandaged3x3(id);

    ArrayList<ScrambleStateBandaged3x3> graph = new ArrayList<>();

    graph.add(bsg);

long t1 = System.currentTimeMillis();

    insertChildren(graph,id);

long t2 = System.currentTimeMillis();

android.util.Log.e("D", "inserting children: "+(t2-t1));

    pruneGraph(graph,id,false);

long t3 = System.currentTimeMillis();

android.util.Log.e("D", "pruning graph: "+(t3-t2));

    computeDistance(graph,id,0);

long t4 = System.currentTimeMillis();

android.util.Log.e("D", "computing distance: "+(t4-t3));

    removeDisconnectedParts(graph);

long t5 = System.currentTimeMillis();

android.util.Log.e("D", "removing disconnected parts: "+(t5-t4));

    remapGraph(graph);

long t6 = System.currentTimeMillis();

android.util.Log.e("D", "remapping graph: "+(t6-t5));

    int num = graph.size();

    ScrambleState[] ret = new ScrambleState[num];

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

      {

      ScrambleStateBandaged3x3 ssb = graph.get(i);

      ret[i] = ssb.produceScrambleState();

      }

long t7 = System.currentTimeMillis();

android.util.Log.e("D", "producing scramble states: "+(t7-t6)+" graph size: "+graph.size() );

    return ret;

    }

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

  private static void insertChildren(ArrayList<ScrambleStateBandaged3x3> list, long id)

    {

    ScrambleStateBandaged3x3 bsg = findState(list,id);

    if( bsg==null )

      {

      android.util.Log.e("D", "error: "+id+" doesn't exist");

      return;

      }

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

      {

      long move = bsg.getMove(i);

      if( move!=INVALID_MOVE )

        {

        ScrambleStateBandaged3x3 tmp = findState(list,move);

        if( tmp==null )

          {

          tmp = new ScrambleStateBandaged3x3(move);

          list.add(tmp);

          insertChildren(list,move);

          }

        else if( tmp.mID != move )

          {

          bsg.setMove(i,tmp.mID);

          }

        }

      }

    }

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

  private static void pruneGraph(ArrayList<ScrambleStateBandaged3x3> list, long id, boolean startingPrunedAlready)

    {

    int num = list.size();

    if( num>1 ) // do not prune moves of an only node leading to itself. Case in point: bandaged 3x3 locked along 2 of its axis.

      {

      boolean pruned = false;

      ScrambleStateBandaged3x3 bsg;

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

        {

        bsg = list.get(i);

        if( bsg.numAxis()<2 )

          {

          long prunedID = bsg.getID();

          if( id!=prunedID || !startingPrunedAlready )

            {

            startingPrunedAlready = true;

            remapID(list,prunedID,INVALID_MOVE);

            }

          // do not remove the starting point, even if it does have only 1 axis

          if( id!=prunedID )

            {

            list.remove(i);

            pruned = true;

            break;

            }

          }

        }

      if( pruned ) pruneGraph(list,id,startingPrunedAlready);

      }

    }

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

  private static void remapGraph(ArrayList<ScrambleStateBandaged3x3> list)

    {

    long id;

    int num = list.size();

    ScrambleStateBandaged3x3 bsg;

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

      {

      bsg = list.get(i);

      id = bsg.getID();

      bsg.setID(i);

      remapID(list,id,i);

      }

    }

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

  private static void remapID(ArrayList<ScrambleStateBandaged3x3> list, long id, long newId)

    {

    ScrambleStateBandaged3x3 bsg;

    int size = list.size();

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

      {

      bsg = list.get(i);

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

        {

        if( bsg.mMoves[j]==id ) bsg.mMoves[j]=newId;

        }

      }

    }

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

  private static void computeDistance(ArrayList<ScrambleStateBandaged3x3> list, long id, int distance)

    {

    ScrambleStateBandaged3x3 state = findState(list,id);

    if( state==null )

      {

      android.util.Log.e("D", "error: "+id+" doesn't exist");

      return;

      }

    if( state.mDistance<0 )

      {

      state.mDistance = distance;

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

        {

        long move = state.getMove(i);

        if( move!=INVALID_MOVE )

          {

          computeDistance(list,move,distance+1);

          }

        }

      }

    }

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

  private static void removeDisconnectedParts(ArrayList<ScrambleStateBandaged3x3> list)

    {

    int num = list.size();

    ScrambleStateBandaged3x3 bsg;

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

      {

      bsg = list.get(i);

      if( bsg.mDistance<0 )

        {

        list.remove(i);

        i--;

        num--;

        }

      }

    }

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

  private static ScrambleStateBandaged3x3 findState(ArrayList<ScrambleStateBandaged3x3> list, long id)

    {

    ScrambleStateBandaged3x3 bsg;

    int num = list.size();

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

      {

      bsg= list.get(i);

      if( bsg.mID==id ) return bsg;

      }

    return null;

    }

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

  private static String formatRet(String str, int row, int angle, long id)

    {

    String ret = str.length()!=0 ? ",":"";

    ret += row;

    ret += angle<0 ? "," : ", ";

    ret += angle;

         if( id< 10 ) ret += (",  "+id);

    else if( id<100 ) ret += (", " +id);

    else              ret += (","  +id);

    return ret;

    }

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

  private static final int LENGTH = 28;

  private static String formatL(String input)

    {

    int len = input.length();

    String ret = input;

    for(int i=0 ;i<LENGTH-len; i++) ret += " ";

    return ret;

    }

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

  private static long[] createMoves(long id)

    {

    long[] ret = new long[NUM_MOVES];

    int index = 0;

    for(int axis=0; axis<3; axis++)

      for(int layer=0; layer<3; layer++)

        {

        long x1 = turn(id,axis,layer);

        if( x1!=INVALID_MOVE )

          {

          long x2 = turn(x1,axis,layer);

          long x3 = turn(x2,axis,layer);

          ret[index  ] = x1;

          ret[index+1] = x2;

          ret[index+2] = x3;

          }

        else

          {

          ret[index  ] = INVALID_MOVE;

          ret[index+1] = INVALID_MOVE;

          ret[index+2] = INVALID_MOVE;

          }

        index+=3;

        }

    return ret;

    }

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

// Definition of the id: it's an 'Andreas signature' of a bandaged cube.

// https://twistypuzzles.com/forum/viewtopic.php?t=24452&sid=f3b4ac0c611c4713e4d7840f1aabbb0b&start=350

  private static long turn(long id, int axis, int layer)

    {

    switch(axis)

      {

      case AXIS_X: switch(layer)

                     {

                     case LAYER_L: if( getBit(id, 1)==1 || getBit(id, 6)==1 || getBit(id,11)==1 ||

                                       getBit(id,22)==1 || getBit(id,27)==1 || getBit(id,32)==1 ||

                                       getBit(id,43)==1 || getBit(id,48)==1 || getBit(id,53)==1  ) return INVALID_MOVE;

                                   long x1 = cycle(id,9,14,46,41);

                                   long x2 = cycle(x1,4,35,51,20);

                                   return    cycle(x2,17,25,38,30);

                     case LAYER_M: if( getBit(id, 1)==1 || getBit(id, 6)==1 || getBit(id,11)==1 ||

                                       getBit(id,22)==1 || getBit(id,27)==1 || getBit(id,32)==1 ||

                                       getBit(id,43)==1 || getBit(id,48)==1 || getBit(id,53)==1 ||

                                       getBit(id, 0)==1 || getBit(id, 5)==1 || getBit(id,10)==1 ||

                                       getBit(id,21)==1 || getBit(id,26)==1 || getBit(id,31)==1 ||

                                       getBit(id,42)==1 || getBit(id,47)==1 || getBit(id,52)==1  ) return INVALID_MOVE;

                                   long x4 = cycle(id,8,13,45,40);

                                   long x5 = cycle(x4,3,34,50,19);

                                   return    cycle(x5,16,24,37,29);

                     case LAYER_R: if( getBit(id, 0)==1 || getBit(id, 5)==1 || getBit(id,10)==1 ||

                                       getBit(id,21)==1 || getBit(id,26)==1 || getBit(id,31)==1 ||

                                       getBit(id,42)==1 || getBit(id,47)==1 || getBit(id,52)==1  ) return INVALID_MOVE;

                                   long x7 = cycle(id,7,12,44,39);

                                   long x8 = cycle(x7,2,33,49,18);

                                   return    cycle(x8,15,23,36,28);

                     }

      case AXIS_Y: switch(layer)

                     {

                     case LAYER_L: if( getBit(id,12)==1 || getBit(id,13)==1 || getBit(id,14)==1 ||

                                       getBit(id,15)==1 || getBit(id,16)==1 || getBit(id,17)==1 ||

                                       getBit(id,18)==1 || getBit(id,19)==1 || getBit(id,20)==1  ) return INVALID_MOVE;

                                   long y1 = cycle(id,1,9,10,2);

                                   long y2 = cycle(y1,0,4,11,7);

                                   return    cycle(y2,3,6,8,5);

                     case LAYER_M: if( getBit(id,12)==1 || getBit(id,13)==1 || getBit(id,14)==1 ||

                                       getBit(id,15)==1 || getBit(id,16)==1 || getBit(id,17)==1 ||

                                       getBit(id,18)==1 || getBit(id,19)==1 || getBit(id,20)==1 ||

                                       getBit(id,33)==1 || getBit(id,34)==1 || getBit(id,35)==1 ||

                                       getBit(id,36)==1 || getBit(id,37)==1 || getBit(id,38)==1 ||

                                       getBit(id,39)==1 || getBit(id,40)==1 || getBit(id,41)==1  ) return INVALID_MOVE;

                                   long y4 = cycle(id,21,25,32,28);

                                   long y5 = cycle(y4,22,30,31,23);

                                   return    cycle(y5,24,27,29,26);

                     case LAYER_R: if( getBit(id,33)==1 || getBit(id,34)==1 || getBit(id,35)==1 ||

                                       getBit(id,36)==1 || getBit(id,37)==1 || getBit(id,38)==1 ||

                                       getBit(id,39)==1 || getBit(id,40)==1 || getBit(id,41)==1  ) return INVALID_MOVE;

                                   long y7 = cycle(id,42,46,53,49);

                                   long y8 = cycle(y7,43,51,52,44);

                                   return    cycle(y8,45,48,50,47);

                     }

      case AXIS_Z: switch(layer)

                     {

                     case LAYER_L: if( getBit(id, 7)==1 || getBit(id, 8)==1 || getBit(id, 9)==1 ||

                                       getBit(id,28)==1 || getBit(id,29)==1 || getBit(id,30)==1 ||

                                       getBit(id,49)==1 || getBit(id,50)==1 || getBit(id,51)==1  ) return INVALID_MOVE;

                                   long z1 = cycle(id,10,20,53,39);

                                   long z2 = cycle(z1,11,41,52,18);

                                   return    cycle(z2,19,32,40,31);

                     case LAYER_M: if( getBit(id, 7)==1 || getBit(id, 8)==1 || getBit(id, 9)==1 ||

                                       getBit(id,28)==1 || getBit(id,29)==1 || getBit(id,30)==1 ||

                                       getBit(id,49)==1 || getBit(id,50)==1 || getBit(id,51)==1 ||

                                       getBit(id, 2)==1 || getBit(id, 3)==1 || getBit(id, 4)==1 ||

                                       getBit(id,23)==1 || getBit(id,24)==1 || getBit(id,25)==1 ||

                                       getBit(id,44)==1 || getBit(id,45)==1 || getBit(id,46)==1  ) return INVALID_MOVE;

                                   long z4 = cycle(id,5,17,48,36);

                                   long z5 = cycle(z4,6,38,47,15);

                                   return    cycle(z5,16,27,37,26);

                     case LAYER_R: if( getBit(id, 2)==1 || getBit(id, 3)==1 || getBit(id, 4)==1 ||

                                       getBit(id,23)==1 || getBit(id,24)==1 || getBit(id,25)==1 ||

                                       getBit(id,44)==1 || getBit(id,45)==1 || getBit(id,46)==1  ) return INVALID_MOVE;

                                   long z7 = cycle(id,0,14,43,33);

                                   long z8 = cycle(z7,1,35,42,12);

                                   return    cycle(z8,13,22,34,21);

                     }

      }

    return 0;

    }

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

// bit b1 in place of b2 etc.

  private static long cycle(long id, int b1, int b2, int b3, int b4)

    {

    long bit1 = getBit(id,b1);

    long bit2 = getBit(id,b2);

    long bit3 = getBit(id,b3);

    long bit4 = getBit(id,b4);

    long i1 = setBit(id,b2,bit1);

    long i2 = setBit(i1,b3,bit2);

    long i3 = setBit(i2,b4,bit3);

    return    setBit(i3,b1,bit4);

    }

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

  private static long getBit(long id, int bit)

    {

    return (id>>bit)&0x1;

    }

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

  private static long setBit(long id, int bit, long value)

    {

    long old = getBit(id,bit);

    if( old!=value )

      {

      long diff = (1L<<bit);

      id += (value==0 ? -diff : diff);

      }

    return id;

    }

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

  private void printMoves()

    {

    String moves = "";

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

      {

      moves += (" " + mMoves[i]);

      }

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

    }

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

  private static String printBits(long id)

    {

    String ret = "[";

    boolean first = true;

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

      {

      if( ( (id>>i)&0x1)==1 )

        {

        String num = (i<10 ? " "+i : ""+i);

        if( first ) { ret += num; first=false; }

        else          ret += (","+num);

        }

      }

    return ret + "]";

    }

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

  private static void printGraph(ArrayList<ScrambleStateBandaged3x3> graph)

    {

    int num = graph.size();

    android.util.Log.e("D", "\n"+num+" states\n");

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

      {

      ScrambleStateBandaged3x3 bsg = graph.get(i);

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

      }

    }

}