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;

import java.util.Random;

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

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

public class ScrambleStateSquare1

{

  private static final int INVALID_MOVE = -1;

  private static final int NUM_MOVES = 23;

  private int mDist;

  private boolean mFresh;

  private long mID;

  private final long[] mMoves;

  private final int[][] mPermittedAngles;

  private final int[] mCornerQuat, mTmp;

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

  static final int[][] QUAT_MULT = 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,}

    };

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

  private static final int[][] BAD_CORNER_QUATS = new int[][]

    {

      { 2, 8,17,23},

      { 5,11,14,20},

    };

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

  public ScrambleStateSquare1(long id, int dist)

    {

    mCornerQuat = new int[8];

    mTmp        = new int[8];

    mPermittedAngles = new int[2][12];

    mDist = dist;

    mFresh = true;

    mID = id;

    mMoves = createMoves(mID);

    }

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

  private void setNotFresh()

    {

    mFresh = false;

    }

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

  private boolean isFresh()

    {

    return mFresh;

    }

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

  public static void computeGraph()

    {

    ArrayList<ScrambleStateSquare1> graph;

    ScrambleStateSquare1 bsg = new ScrambleStateSquare1(0,0);

    graph = new ArrayList<>();

    graph.add(bsg);

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

    insertChildren(graph,0);

//android.util.Log.e("D", "PRUNING "+graph.size());

//    pruneGraph(graph);

android.util.Log.e("D", "REMAPPING "+graph.size());

    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<ScrambleStateSquare1> list, long id)

    {

    ScrambleStateSquare1 bsg = findState(list,id);

    if( bsg==null )

      {

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

      return;

      }

    int dist = bsg.mDist;

    if( dist>6 ) return;

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

      {

      long moveID = bsg.getMoveID(i);

      if( moveID!=INVALID_MOVE )

        {

        ScrambleStateSquare1 tmp = findState(list,moveID);

        if( tmp==null )

          {

          tmp = new ScrambleStateSquare1(moveID,dist+1);

          list.add(tmp);

          }

        }

      }

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

      {

      long moveID = bsg.getMoveID(i);

      if( moveID!=INVALID_MOVE )

        {

        ScrambleStateSquare1 tmp = findState(list,moveID);

        if( tmp.isFresh() )

          {

          tmp.setNotFresh();

          insertChildren(list,moveID);

          }

        }

      }

    }

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

  private static void pruneGraph(ArrayList<ScrambleStateSquare1> list)

    {

    int num = list.size(), numAxis;

    boolean pruned = false;

    ScrambleStateSquare1 bsg;

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

      {

      bsg = list.get(i);

      numAxis = bsg.numAxis();

      if( numAxis<2 )

        {

        list.remove(i);

        long id = bsg.getID();

        pruned = true;

        remapID(list,id,INVALID_MOVE);

        break;

        }

      }

    if( pruned ) pruneGraph(list);

    }

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

  private static void remapGraph(ArrayList<ScrambleStateSquare1> list)

    {

    long id;

    int num = list.size();

    ScrambleStateSquare1 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<ScrambleStateSquare1> list, long id, long newId)

    {

    ScrambleStateSquare1 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.getMoveID(j)==id ) bsg.setMoveID(j,newId);

        }

      }

    }

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

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

    {

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

    {

    String x = getTable(bsg,0);

    String y = getTable(bsg,11);

    String z = getTable(bsg,12);

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

    long id = bsg.getID();

    return id+" "+x+" , "+y+" , "+z;

    }

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

  private static String getTable(ScrambleStateSquare1 sc, int index)

    {

    String ret = "";

    long m;

    int half = (NUM_MOVES)/2;

    if( index==11 )

      {

      m = sc.getMoveID(index);

      if( m==INVALID_MOVE ) return formatL("{}");

      ret += formatRet(ret,0,1,m);

      }

    else

      {

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

        {

        m = sc.getMoveID(index+i);

        int row = index==0 ? 0:2;

        int angle = i+1;

        if( m!=INVALID_MOVE ) ret += formatRet(ret,row,angle,m);

        }

      }

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

    }

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

  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 long getID()

    {

    return mID;

    }

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

  private void setID(long id)

    {

    mID = id;

    }

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

  private long getMoveID(int index)

    {

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

    }

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

  private void setMoveID(int index, long newID)

    {

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

    }

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

  private int numAxis()

    {

    int num = 0;

    int half = (NUM_MOVES)/2;

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

      {

      if( mMoves[i]!=INVALID_MOVE )

        {

        num++;

        break;

        }

      }

    for(int i=half; i<NUM_MOVES-1; i++)

      {

      if( mMoves[i]!=INVALID_MOVE )

        {

        num++;

        break;

        }

      }

    if( mMoves[NUM_MOVES-1]!=INVALID_MOVE ) num++;

    return num;

    }

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

  private long[] createMoves(long id)

    {

    long[] ret = new long[NUM_MOVES];

    fillCornerQuat(id);

    computePermittedAngles();

    generateUMoves(ret, 0);

    generateSMoves(ret,11);

    generateLMoves(ret,12);

    return ret;

    }

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

  private void generateUMoves(long[] table, int index)

    {

    for(int angle=1; angle<12; angle++)

      {

      table[index+angle-1] = mPermittedAngles[1][angle]==1 ? updateCornerQuats(0,2,angle) : INVALID_MOVE;

      }

    }

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

  private void generateLMoves(long[] table, int index)

    {

    for(int angle=1; angle<12; angle++)

      {

      table[index+angle-1] = mPermittedAngles[0][angle]==1 ? updateCornerQuats(0,0,angle) : INVALID_MOVE;

      }

    }

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

  private void generateSMoves(long[] table, int index)

    {

    table[index] = updateCornerQuats(1,1,1);

    }

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

  private void fillCornerQuat(long id)

    {

    int NUM_QUATS = 24;

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

      {

      mCornerQuat[i] = (int)(id%NUM_QUATS);

      id/=NUM_QUATS;

      }

    }

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

  private static long returnID(int[] cornerQuat)

    {

    int NUM_QUATS = 24;

    long mult=1,ret=0;

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

      {

      ret += mult*cornerQuat[i];

      mult*=NUM_QUATS;

      }

    return ret;

    }

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

  private boolean cornerIsUp(int index)

    {

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

    }

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

  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;

    }

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

  private int makeQuat(int axis,int index)

    {

    if( axis==1 ) return 13;

    if( index<0 ) index+=12;

    return index;

    }

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

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

      }

    }

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

  private long updateCornerQuats(int axis, int layer, int index)

    {

    int quat = makeQuat(axis,index);

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

      {

      if( cornerBelongs(corner,axis,layer) )

        {

        int curr = mCornerQuat[corner];

        mTmp[corner] = QUAT_MULT[quat][curr];

        }

      else

        {

        mTmp[corner] = mCornerQuat[corner];

        }

      }

    return returnID(mTmp);

    }

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

  private boolean quatIsBad(int quatIndex, int corner)

    {

    int index = (corner%2);

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

             quatIndex==BAD_CORNER_QUATS[index][1] ||

             quatIndex==BAD_CORNER_QUATS[index][2] ||

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

    }

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

  private int isPermittedDo(int angle)

    {

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

      {

      if( !cornerIsUp(corner) )

        {

        int currQuat = mCornerQuat[corner];

        int finalQuat= QUAT_MULT[angle][currQuat];

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

        }

      }

    return 1;

    }

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

  private int isPermittedUp(int angle)

    {

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

      {

      if( cornerIsUp(corner) )

        {

        int currQuat = mCornerQuat[corner];

        int finalQuat= QUAT_MULT[angle][currQuat];

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

        }

      }

    return 1;

    }

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

  private void computePermittedAngles()

    {

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

      {

      mPermittedAngles[0][angle] = isPermittedDo(angle);

      mPermittedAngles[1][angle] = isPermittedUp(angle);

      }

    }

}