TwistyPuzzleLib

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

// Copyright 2023 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.tablebases;

import org.distorted.objectlib.R;

import org.distorted.objectlib.helpers.OperatingSystemInterface;

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

public class TBDino4 extends TBDino

{

  private static final int[][] SAME = {{0,3,7},{1,2,5},{4,8,9},{6,10,11}};

  private static final int SOLVED1 =  6237;  // partition 011021302233

  private static final int SOLVED2 = 10837;  // partition 001102133223

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

  public TBDino4()

    {

    super();

    }

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

  public TBDino4(OperatingSystemInterface os)

    {

    super(os, new int[] {R.raw.din4_3_pruning2,R.raw.din4_3_pruning3}, new int[] {R.raw.din4_3_pruning7});

    }

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

// specifically for the tablebase

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

// two solved positions: original and mirrored (left face swapped with right)

  @Override

  int[] getSolvedIndices()

    {

    return new int[] {SOLVED1,SOLVED2};

    }

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

// ditto

  @Override

  boolean isSolved(int index)

    {

    return index==SOLVED1 || index==SOLVED2;

    }

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

// 15408 really (see https://www.jaapsch.net/puzzles/dinocube.htm)

// Here 15400 because we equal positions where colors are simply swapped (those are the same with

// respect to distance to the 2 solved positions) so there are (11 choose 2)*(8 choose 2)*(5 choose 2)

// = 55*28*10 = 15400 possibilities.

// We do not pack those tightly, some positions in the same orbit (by Burnside lemma) have 3 different

// indices.

  int getSize()

    {

    return 15400;

    }

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

  int getMinScramble()

    {

    return 5;

    }

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

  int[] getMidPruningLevels()

    {

    return new int[] {2,3};

    }

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

  int[] getHighPruningLevels()

    {

    return new int[] {7};

    }

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

  int getGodsNumber()

    {

    return 7;

    }

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

  private static int computeIndex(int[] partition, int section, int size)

    {

    int index0=0;

    for(;index0<12; index0++)

      if(partition[index0]==section ) break;

    int index1=index0+1;

    int D1 = 0;

    for(;index1<12; index1++)

      {

      int val = partition[index1];

      if(val >section ) D1++;

      if(val==section ) break;

      }

    int index2=index1+1;

    int D2 = 0;

    for(;index2<12; index2++)

      {

      int val = partition[index2];

      if(val >section ) D2++;

      if(val==section ) break;

      }

    return D1*size - (D1+1)*D1/2 + D2;

    }

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

  public static int indexFromPartition(int[] partition)

    {

    int index0 = computeIndex(partition,0,11);

    int index1 = computeIndex(partition,1,8);

    int index2 = computeIndex(partition,2,5);

    return index0 + 55*(index1 + 28*index2);

    }

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

  private static void fillPart(int[] part, int index, int section, int size)

    {

    int index0=0;

    for(; index0<10; index0++)

      if( part[index0]<0 )

        {

        part[index0] = section;

        break;

        }

    int index1 = index0+1;

    int diff = size-1;

    for(; index1<11; index1++)

      if( part[index1]<0 )

        {

        if( index<diff )

          {

          part[index1] = section;

          break;

          }

        else { index-=diff; diff--; }

        }

    int index2 = index1+1;

    for(; index2<12; index2++)

      {

      if( part[index2]<0 ) index--;

      if( index<0 )

        {

        part[index2] = section;

        break;

        }

      }

    }

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

  private static int[] partitionFromIndex(int index)

    {

    int index0 = (index%55);

    index /= 55;

    int index1 = (index%28);

    int index2 = (index/28);

    int[] part = new int[12];

    for(int i=0; i<12; i++) part[i] = -1;

    fillPart(part,index0,0,11);

    fillPart(part,index1,1,8);

    fillPart(part,index2,2,5);

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

      if( part[i]<0 ) part[i] = 3;

    return part;

    }

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

  private static void fillPerm(int[] perm, int[] part, int section)

    {

    int num=0;

    int[] same = SAME[section];

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

      if( part[i]==section )

        perm[same[num++]] = i;

    }

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

  private static int[] quatsFromPartition(int[] partition)

    {

    int[] perm = new int[12];

    fillPerm(perm,partition,0);

    fillPerm(perm,partition,1);

    fillPerm(perm,partition,2);

    fillPerm(perm,partition,3);

    return TBDino.getQuatsFromPerm(perm);

    }

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

  private static int[] partitionFromQuats(int[] quats)

    {

    int[] perm = new int[12];

    System.arraycopy(quats, 0, perm, 0, 12);

    TBDino.getPermFromQuats(perm);

    int[] part = new int[12];

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

      {

      int[] index = SAME[i];

      part[perm[index[0]]] = part[perm[index[1]]] = part[perm[index[2]]] = (-i-1);

      }

    int newVal=0;

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

      {

      int val = part[i];

      if( val<0 )

        {

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

          if( part[j]==val ) part[j] = newVal;

        newVal++;

        }

      }

    return part;

    }

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

  int[] getQuats(int index)

    {

    int[] partition = partitionFromIndex(index);

    return quatsFromPartition(partition);

    }

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

  int getIndex(int[] quats)

    {

    normalizeQuats(quats);

    int[] partition = partitionFromQuats(quats);

    return indexFromPartition(partition);

    }

}