Magic Cube

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

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

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

import java.util.ArrayList;

public class BandagedStateGraph

{

  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 BandagedStateGraph(int id)

    {

    mID = id;

    mMoves = createMoves(mID);

    }

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

  public static void computeGraph()

    {

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

    BandagedStateGraph bsg = new BandagedStateGraph(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<BandagedStateGraph> list, int id)

    {

    BandagedStateGraph 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!=0 )

        {

        BandagedStateGraph tmp = findState(list,move);

        if( tmp==null )

          {

          tmp = new BandagedStateGraph(move);

          list.add(tmp);

          insertChildren(list,move);

          }

        }

      }

    }

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

  private static void pruneGraph(ArrayList<BandagedStateGraph> list)

    {

    int num = list.size(), numAxis;

    boolean pruned = false;

    BandagedStateGraph 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,0);

        break;

        }

      }

    if( pruned ) pruneGraph(list);

    }

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

  private static void remapGraph(ArrayList<BandagedStateGraph> list)

    {

    int id, num = list.size();

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

    {

    BandagedStateGraph 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 BandagedStateGraph findState(ArrayList<BandagedStateGraph> list, int id)

    {

    BandagedStateGraph 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(BandagedStateGraph bsg)

    {

    String x = getTable(bsg,0);

    String y = getTable(bsg,3);

    String z = getTable(bsg,6);

    return "    new BandagedState( "+x+", "+y+", "+z+" ),";

    }

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

  private static String getTable(BandagedStateGraph 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==0 && m1==0 && m2==0 ) return formatL("null");

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

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

      if( m2!=0 ) 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==0 && m1==0 && m2==0 && m3==0 && m4==0 && m5==0 )

        {

        return formatL("null");

        }

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

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

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

      if( m3!=0 ) ret += formatRet(ret,2, 1,m3);

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

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

      }

    return formatL("new int[] {" + 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 = 38;

  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]!=0 || mMoves[ 1]!=0 || mMoves[ 2]!=0 ) num++;

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

    if( mMoves[ 6]!=0 || mMoves[ 7]!=0 || mMoves[ 8]!=0 ) num++;

    if( mMoves[ 9]!=0 || mMoves[10]!=0 || mMoves[11]!=0 ) 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] = 0; ret[ 1] = 0; ret[ 2] = 0; }

    if( moveY ) createYmoves(id,ret);

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

    if( moveZ0) createZ0moves(id,ret);

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

    if( moveZ2) createZ2moves(id,ret);

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

    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;

    }

}