TwistyPuzzleLib

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

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

import java.util.ArrayList;

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

// producer of the ScrambleStateGraph - but only for a single Twisty Puzzle, the 'BandagedEvil'.

public class ScrambleStateBandagedEvil

{

  private static final int INVALID_MOVE = -1;

  private static final int CORNER_S = 0;

  private static final int CORNER_X = 1;

  private static final int CORNER_Y = 2;

  private static final int CORNER_Z = 3;

  private static final int CENTER_0 = 0;

  private static final int CENTER_1 = 1;

  private static final int CENTER_2 = 2;

  private static final int CENTER_3 = 3;

  private int mID;

  private final int[] mMoves;

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

  public ScrambleStateBandagedEvil(int id)

    {

    mID = id;

    mMoves = createMoves(mID);

    }

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

  public static void computeGraph()

    {

    ArrayList<ScrambleStateBandagedEvil> graph;

    int id = 0;

    int id1 = setCenter(id  , CENTER_2, 0);

    int id2 = setCenter(id1 , CENTER_2, 1);

    int id3 = setCenter(id2 , CENTER_3, 2);

    int id4 = setCenter(id3 , CENTER_2, 3);

    int id5 = setCorner(id4 , CORNER_X, 0);

    int id6 = setCorner(id5 , CORNER_Y, 1);

    int id7 = setCorner(id6 , CORNER_X, 2);

    int id8 = setCorner(id7 , CORNER_Z, 3);

    int id9 = setCorner(id8 , CORNER_Y, 4);

    int id10= setCorner(id9 , CORNER_Y, 5);

    int id11= setCorner(id10, CORNER_S, 6);

    int id12= setCorner(id11, CORNER_Z, 7);

    ScrambleStateBandagedEvil bsg = new ScrambleStateBandagedEvil(id12);

    graph = new ArrayList<>();

    graph.add(bsg);

    insertChildren(graph,id12);

    pruneGraph(graph);

    remapGraph(graph);

    int num = graph.size();

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

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

      {

      bsg = graph.get(i);

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

      }

    }

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

  private static void insertChildren(ArrayList<ScrambleStateBandagedEvil> list, int id)

    {

    ScrambleStateBandagedEvil bsg = findState(list,id);

    if( bsg==null )

      {

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

      return;

      }

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

      {

      int move = bsg.getMove(i);

      if( move!=INVALID_MOVE )

        {

        ScrambleStateBandagedEvil tmp = findState(list,move);

        if( tmp==null )

          {

          tmp = new ScrambleStateBandagedEvil(move);

          list.add(tmp);

          insertChildren(list,move);

          }

        }

      }

    }

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

  private static void pruneGraph(ArrayList<ScrambleStateBandagedEvil> list)

    {

    int num = list.size(), numAxis;

    boolean pruned = false;

    ScrambleStateBandagedEvil bsg;

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

      {

      bsg = list.get(i);

      numAxis = bsg.numAxis();

      if( numAxis<2 )

        {

        list.remove(i);

        int id = bsg.getID();

        pruned = true;

        remapID(list,id,INVALID_MOVE);

        break;

        }

      }

    if( pruned ) pruneGraph(list);

    }

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

  private static void remapGraph(ArrayList<ScrambleStateBandagedEvil> list)

    {

    int id, num = list.size();

    ScrambleStateBandagedEvil 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<ScrambleStateBandagedEvil> list, int id, int newId)

    {

    ScrambleStateBandagedEvil bsg;

    int size = list.size();

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

      {

      bsg = list.get(i);

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

        {

        if( bsg.getMove(j)==id ) bsg.setMove(j,newId);

        }

      }

    }

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

  private static ScrambleStateBandagedEvil findState(ArrayList<ScrambleStateBandagedEvil> list, int id)

    {

    ScrambleStateBandagedEvil bsg;

    int num = list.size();

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

      {

      bsg= list.get(i);

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

      }

    return null;

    }

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

  private static String formatMoves(ScrambleStateBandagedEvil bsg)

    {

    String x = getTable(bsg,0);

    String y = getTable(bsg,3);

    String z = getTable(bsg,6);

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

    }

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

  private static String getTable(ScrambleStateBandagedEvil sc, int index)

    {

    String ret = "";

    if( index==0 || index==3 )

      {

      int m0 = sc.getMove(index  );

      int m1 = sc.getMove(index+1);

      int m2 = sc.getMove(index+2);

      if( m0==INVALID_MOVE && m1==INVALID_MOVE && m2==INVALID_MOVE ) return formatL("{}");

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

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

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

      }

    else

      {

      int m0 = sc.getMove(index  );

      int m1 = sc.getMove(index+1);

      int m2 = sc.getMove(index+2);

      int m3 = sc.getMove(index+3);

      int m4 = sc.getMove(index+4);

      int m5 = sc.getMove(index+5);

      if( m0==INVALID_MOVE && m1==INVALID_MOVE && m2==INVALID_MOVE &&

          m3==INVALID_MOVE && m4==INVALID_MOVE && m5==INVALID_MOVE  )

        {

        return formatL("{}");

        }

      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,2, 1,m3);

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

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

      }

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

    }

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

  private static String formatRet(String str, int row, int angle, int 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 int getID()

    {

    return mID;

    }

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

  private void setID(int id)

    {

    mID = id;

    }

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

  private int getMove(int index)

    {

    return (index>=0 && index<12) ? mMoves[index] : -1;

    }

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

  private int numAxis()

    {

    int num = 0;

    if( mMoves[ 0]!=INVALID_MOVE || mMoves[ 1]!=INVALID_MOVE || mMoves[ 2]!=INVALID_MOVE ) num++;

    if( mMoves[ 3]!=INVALID_MOVE || mMoves[ 4]!=INVALID_MOVE || mMoves[ 5]!=INVALID_MOVE ) num++;

    if( 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 ) num++;

    return num;

    }

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

  private void setMove(int index, int newMove)

    {

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

    }

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

  private static String debug(int id)

    {

    int ce0 = getCenter(id,0);

    int ce1 = getCenter(id,1);

    int ce2 = getCenter(id,2);

    int ce3 = getCenter(id,3);

    int co0 = getCorner(id,0);

    int co1 = getCorner(id,1);

    int co2 = getCorner(id,2);

    int co3 = getCorner(id,3);

    int co4 = getCorner(id,4);

    int co5 = getCorner(id,5);

    int co6 = getCorner(id,6);

    int co7 = getCorner(id,7);

    String center = centerString(ce0) + centerString(ce1) + centerString(ce2) + centerString(ce3);

    String corner = cornerString(co0) + cornerString(co1) + cornerString(co2) + cornerString(co3) +

                    cornerString(co4) + cornerString(co5) + cornerString(co6) + cornerString(co7);

    return center + " -" + corner;

    }

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

  private static String centerString(int center)

    {

    return " "+center;

    }

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

  private static String cornerString(int corner)

    {

    switch(corner)

      {

      case CORNER_S: return " S";

      case CORNER_X: return " X";

      case CORNER_Y: return " Y";

      case CORNER_Z: return " Z";

      }

    return "?";

    }

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

  private static int[] createMoves(int id)

    {

    int[] ret = new int[12];

    boolean moveX  = xPossible(id);

    boolean moveY  = yPossible(id);

    boolean moveZ0 = z0Possible(id);

    boolean moveZ2 = z2Possible(id);

    if( moveX ) createXmoves(id,ret);

    else        { ret[ 0] = INVALID_MOVE; ret[ 1] = INVALID_MOVE; ret[ 2] = INVALID_MOVE; }

    if( moveY ) createYmoves(id,ret);

    else        { ret[ 3] = INVALID_MOVE; ret[ 4] = INVALID_MOVE; ret[ 5] = INVALID_MOVE; }

    if( moveZ0) createZ0moves(id,ret);

    else        { ret[ 6] = INVALID_MOVE; ret[ 7] = INVALID_MOVE; ret[ 8] = INVALID_MOVE; }

    if( moveZ2) createZ2moves(id,ret);

    else        { ret[ 9] = INVALID_MOVE; ret[10] = INVALID_MOVE; ret[11] = INVALID_MOVE; }

    return ret;

    }

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

  private static boolean xPossible(int id)

    {

    if( getCorner(id,4)==CORNER_X ) return false;

    if( getCorner(id,5)==CORNER_X ) return false;

    if( getCorner(id,6)==CORNER_X ) return false;

    if( getCorner(id,7)==CORNER_X ) return false;

    if( getCenter(id,1)==CENTER_1 ) return false;

    if( getCenter(id,2)==CENTER_1 ) return false;

    if( getCenter(id,3)==CENTER_1 ) return false;

    return true;

    }

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

  private static boolean yPossible(int id)

    {

    if( getCorner(id,2)==CORNER_Y ) return false;

    if( getCorner(id,3)==CORNER_Y ) return false;

    if( getCorner(id,6)==CORNER_Y ) return false;

    if( getCorner(id,7)==CORNER_Y ) return false;

    if( getCenter(id,0)==CENTER_0 ) return false;

    if( getCenter(id,2)==CENTER_0 ) return false;

    if( getCenter(id,3)==CENTER_0 ) return false;

    return true;

    }

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

  private static boolean z0Possible(int id)

    {

    if( getCorner(id,0)==CORNER_Z ) return false;

    if( getCorner(id,2)==CORNER_Z ) return false;

    if( getCorner(id,4)==CORNER_Z ) return false;

    if( getCorner(id,6)==CORNER_Z ) return false;

    if( getCenter(id,0)==CENTER_1 ) return false;

    if( getCenter(id,1)==CENTER_0 ) return false;

    return true;

    }

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

  private static boolean z2Possible(int id)

    {

    if( getCorner(id,1)==CORNER_Z ) return false;

    if( getCorner(id,3)==CORNER_Z ) return false;

    if( getCorner(id,5)==CORNER_Z ) return false;

    if( getCorner(id,7)==CORNER_Z ) return false;

    if( getCenter(id,0)==CENTER_3 ) return false;

    if( getCenter(id,1)==CENTER_2 ) return false;

    return true;

    }

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

  private static int getCorner(int id, int index)

    {

    return (id>>(14-2*index))&3;

    }

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

  private static int getCenter(int id, int index)

    {

    return (id>>(22-2*index))&3;

    }

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

  private static int setCorner(int id, int corner, int index)

    {

    return id + ((corner-getCorner(id,index))<<(14-2*index));

    }

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

  private static int setCenter(int id, int center, int index)

    {

    return id + ((center-getCenter(id,index))<<(22-2*index));

    }

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

  private static void createXmoves(int id, int[] moves)

    {

    int id1 = rotateX(id);

    moves[0] = id1;

    int id2 = rotateX(id1);

    moves[1] = id2;

    int id3 = rotateX(id2);

    moves[2] = id3;

    }

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

  private static void createYmoves(int id, int[] moves)

    {

    int id1 = rotateY(id);

    moves[3] = id1;

    int id2 = rotateY(id1);

    moves[4] = id2;

    int id3 = rotateY(id2);

    moves[5] = id3;

    }

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

  private static void createZ0moves(int id, int[] moves)

    {

    int id1 = rotateZ0(id);

    moves[6] = id1;

    int id2 = rotateZ0(id1);

    moves[7] = id2;

    int id3 = rotateZ0(id2);

    moves[8] = id3;

    }

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

  private static void createZ2moves(int id, int[] moves)

    {

    int id1 = rotateZ2(id);

    moves[ 9] = id1;

    int id2 = rotateZ2(id1);

    moves[10] = id2;

    int id3 = rotateZ2(id2);

    moves[11] = id3;

    }

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

  private static int rotateX(int id)

    {

    int newCorner4 = rotCornerX(getCorner(id,5));

    int newCorner5 = rotCornerX(getCorner(id,7));

    int newCorner6 = rotCornerX(getCorner(id,4));

    int newCorner7 = rotCornerX(getCorner(id,6));

    int newCenter  = rotCenter (getCenter(id,0));

    int id1 = setCorner(id ,newCorner4,4);

    int id2 = setCorner(id1,newCorner5,5);

    int id3 = setCorner(id2,newCorner6,6);

    int id4 = setCorner(id3,newCorner7,7);

    int id5 = setCenter(id4,newCenter ,0);

    return id5;

    }

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

  private static int rotateY(int id)

    {

    int newCorner2 = rotCornerY(getCorner(id,6));

    int newCorner3 = rotCornerY(getCorner(id,2));

    int newCorner6 = rotCornerY(getCorner(id,7));

    int newCorner7 = rotCornerY(getCorner(id,3));

    int newCenter  = rotCenter (getCenter(id,1));

    int id1 = setCorner(id ,newCorner2,2);

    int id2 = setCorner(id1,newCorner3,3);

    int id3 = setCorner(id2,newCorner6,6);

    int id4 = setCorner(id3,newCorner7,7);

    int id5 = setCenter(id4,newCenter ,1);

    return id5;

    }

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

  private static int rotateZ0(int id)

    {

    int newCorner0 = rotCornerZ(getCorner(id,2));

    int newCorner2 = rotCornerZ(getCorner(id,6));

    int newCorner4 = rotCornerZ(getCorner(id,0));

    int newCorner6 = rotCornerZ(getCorner(id,4));

    int newCenter  = rotCenter (getCenter(id,2));

    int id1 = setCorner(id ,newCorner0,0);

    int id2 = setCorner(id1,newCorner2,2);

    int id3 = setCorner(id2,newCorner4,4);

    int id4 = setCorner(id3,newCorner6,6);

    int id5 = setCenter(id4,newCenter ,2);

    return id5;

    }

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

  private static int rotateZ2(int id)

    {

    int newCorner1 = rotCornerZ(getCorner(id,3));

    int newCorner3 = rotCornerZ(getCorner(id,7));

    int newCorner5 = rotCornerZ(getCorner(id,1));

    int newCorner7 = rotCornerZ(getCorner(id,5));

    int newCenter  = rotCenter (getCenter(id,3));

    int id1 = setCorner(id ,newCorner1,1);

    int id2 = setCorner(id1,newCorner3,3);

    int id3 = setCorner(id2,newCorner5,5);

    int id4 = setCorner(id3,newCorner7,7);

    int id5 = setCenter(id4,newCenter ,3);

    return id5;

    }

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

  private static int rotCornerX(int corner)

    {

    switch(corner)

      {

      case CORNER_S: return CORNER_S;

      case CORNER_X: android.util.Log.e("DIST", "rotateX: ERROR");

                     return CORNER_S;

      case CORNER_Y: return CORNER_Z;

      case CORNER_Z: return CORNER_Y;

      }

    return CORNER_S;

    }

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

  private static int rotCornerY(int corner)

    {

    switch(corner)

      {

      case CORNER_S: return CORNER_S;

      case CORNER_X: return CORNER_Z;

      case CORNER_Y: android.util.Log.e("DIST", "rotateY: ERROR");

                     return CORNER_S;

      case CORNER_Z: return CORNER_X;

      }

    return CORNER_S;

    }

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

  private static int rotCornerZ(int corner)

    {

    switch(corner)

      {

      case CORNER_S: return CORNER_S;

      case CORNER_X: return CORNER_Y;

      case CORNER_Y: return CORNER_X;

      case CORNER_Z: android.util.Log.e("DIST", "rotateZ: ERROR");

                     return CORNER_S;

      }

    return CORNER_S;

    }

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

  private static int rotCenter(int center)

    {

    switch(center)

      {

      case CENTER_0: return CENTER_3;

      case CENTER_1: return CENTER_0;

      case CENTER_2: return CENTER_1;

      case CENTER_3: return CENTER_2;

      }

    return CENTER_0;

    }

}