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 java.util.Random;

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

public class TablebaseHelpers

{

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

  public static void displayTable(int[] table, String marker)

    {

    StringBuilder sb = new StringBuilder();

    for( int t : table )

      {

      sb.append(' ');

      sb.append(t);

      }

    android.util.Log.e("D", marker+" : "+sb);

    }

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

  private static String print(int[][] move)

    {

    StringBuilder sb = new StringBuilder();

    if( move==null )

      {

      return ("move NULL!!");

      }

    for (int[] ints : move)

      {

      sb.append(' ');

      sb.append('(');

      sb.append(ints[0]);

      sb.append(' ');

      sb.append(ints[1]);

      sb.append(' ');

      sb.append(ints[2]);

      sb.append(')');

      }

    return sb.toString();

    }

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

  public static void test(TablebasesAbstract tb)

    {

    int size = tb.getSize();

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

      {

      boolean success = tb.test(i);

      if( (!success && i>0) || (success && i==0) )

        {

        android.util.Log.e("D", "--------> FAILED: "+i);

        break;

        }

      if( (i%1000)==0 )   android.util.Log.e("D", "trying "+i);

      }

    }

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

  private final static int MAX_PERM=12;  // biggest N for which N! is still less than 2^32

  private final static int[] avail = new int[MAX_PERM];

  private final static int[] pos   = new int[MAX_PERM];

  private final static int[] fact  = new int[MAX_PERM];

  static

    {

    fact[0] = 1;

    for(int i=1; i<MAX_PERM; i++) fact[i] = fact[i-1]*i;

    }

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

  public static void getPermutationFromNum(int[] buffer,int permSize, int permNum)

    {

    avail[0] = pos[0] = 0;

    for(int i=1; i<permSize; i++) avail[i] = pos[i] = permSize-i;

    for(int i=0; i<permSize-1; i++)

      {

      int m = fact[permSize-1-i];

      int k = permNum/m;

      permNum %= m;

      buffer[i] = avail[k];

      int y = avail[permSize-1-i];

      pos[y] = k;

      avail[k] = y;

      }

    buffer[permSize-1] = avail[0];

    }

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

// Enumeration of permutations in linear time.

// 1) notice that 'avail' and 'pos' are always inverses: avail[m]=n iff pos[n]=m

// 2) notice that that implies that after the i-th execution of the loop, avail[0 ... n-1-i]

//    contains the n-i elements of the permutation we haven't scanned yet

//    ( that is because this is true initially, and during each loop, we remove avail[k] from

//      this list - but k = pos[buffer[i]] implies buffer[i] = avail[k] so we are really removing

//      buffer[i] - i.e. exactly the permutation element we have just scanned! )

// 3) each 'k' is a digit of the permutation in a strange ( n-1,n-2,...,2 ) notation where the most

//    significant digit can be one of the {0...,n-1}, the next most significant - one of the {0,...,n-2},

//    etc.

// 4) the ret = ret*(permSize-i) + k is a transform from this ( n-1,n-2,...,2 ) notation to an index.

//

// 'avail' is initially set to {0,n-1,n-2,...,2,1} because that implies that an 'empty' permutation

//  gets mapped to index=0.

  public static int computePermutationNum(int[] buffer)

    {

    int permSize = buffer.length;

    avail[0] = pos[0] = 0;

    for(int i=1; i<permSize; i++) avail[i] = pos[i] = permSize-i;

    int ret = 0;

    for(int i=0; i<permSize-1; i++)

      {

      int k = pos[buffer[i]];

      ret = ret*(permSize-i) + k;

      int y = avail[permSize-1-i];

      pos[y] = k;

      avail[k] = y;

      }

    return ret;

    }

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

  public static int computeEvenPermutationNum(int[] buffer)

    {

    int index = computePermutationNum(buffer);

    return index/2;

    }

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

  public static void getEvenPermutationFromNum(int[] buffer, int permNum)

    {

    getPermutationFromNum(buffer, buffer.length, 2*permNum);

    boolean even = permutationIsEven(buffer);

    if( !even ) getPermutationFromNum(buffer, buffer.length, 2*permNum+1 );

    }

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

  private static int swaps(int val, int[] buffer, int len)

    {

    int ret = 0;

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

      {

           if( buffer[i] >val ) ret++;

      else if( buffer[i]==val ) return ret;

      }

    return -1;

    }

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

  public static boolean permutationIsEven(int[] buffer)

    {

    int len = buffer.length;

    int numOfSwaps = 0;

    for(int i=0; i<len-1; i++) numOfSwaps += swaps(i,buffer,len);

    return (numOfSwaps%2==0);

    }

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

  public static void invertPermutation(int[] perm, int[] output)

    {

    int len = perm.length;

    for(int i=0; i<len; i++) output[i] = -1;

    for(int i=0; i<len; i++) output[perm[i]] = i;

    }

}