Project

General

Profile

« Previous | Next » 

Revision cf336a4b

Added by Leszek Koltunski 11 months ago

Progress with phased solver. The only thing left to implement is the MitMTable class :)

View differences:

src/main/java/org/distorted/objectlib/algsolvers/MitmTable.java
1 
///////////////////////////////////////////////////////////////////////////////////////////////////
2 
// Copyright 2024 Leszek Koltunski                                                               //
3 
//                                                                                               //
4 
// This file is part of Magic Cube.                                                              //
5 
//                                                                                               //
6 
// Magic Cube is proprietary software licensed under an EULA which you should have received      //
7 
// along with the code. If not, check https://distorted.org/magic/License-Magic-Cube.html        //
8 
///////////////////////////////////////////////////////////////////////////////////////////////////
9 

  		




  
  10
  
    
package org.distorted.objectlib.algsolvers;


  		




  
  11
  
    

  		




  
  12
  
    
import org.distorted.objectlib.helpers.OperatingSystemInterface;


  		




  
  13
  
    

  		




  
  14
  
    
public class MitmTable


  		




  
  15
  
    
{


  		




  
  16
  
    
  private final int mBytesPerEntry;


  		




  
  17
  
    

  		




  
  18
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  
  19
  
    

  		




  
  20
  
    
  MitmTable(int bytesPerEntry)


  		




  
  21
  
    
    {


  		




  
  22
  
    
    mBytesPerEntry = bytesPerEntry;


  		




  
  23
  
    
    }


  		




  
  24
  
    

  		




  
  25
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  
  26
  
    

  		




  
  27
  
    
  int getBytesPerEntry()


  		




  
  28
  
    
    {


  		




  
  29
  
    
    return mBytesPerEntry;


  		




  
  30
  
    
    }


  		




  
  31
  
    

  		




  
  32
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  
  33
  
    

  		




  
  34
  
    
  void clear()


  		




  
  35
  
    
    {


  		




  
  36
  
    

  		




  
  37
  
    
    }


  		




  
  38
  
    

  		




  
  39
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  
  40
  
    

  		




  
  41
  
    
  void build(SolvedObject object)


  		




  
  42
  
    
    {


  		




  
  43
  
    

  		




  
  44
  
    
    }


  		




  
  45
  
    

  		




  
  46
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  
  47
  
    
// having built the MiTM table, try to reach it working backwards from each of the positions


  		




  
  48
  
    
// described by 'endQuats'.


  		




  
  49
  
    

  		




  
  50
  
    
  int[][] tryReaching(SolvedObject object, int[][] endQuats, int len, OperatingSystemInterface osi)


  		




  
  51
  
    
    {


  		




  
  52
  
    

  		




  
  53
  
    
    }


  		




  
  54
  
    
}


  		












  

    
      src/main/java/org/distorted/objectlib/algsolvers/PhaseSolutionFinder.java
    
  





  17
  17
  
    

  		




  18
  18
  
    
public class PhaseSolutionFinder


  		




  19
  19
  
    
{


  		




  20
  
  
    
  private final static double LOG2 = Math.log(2);


  		




  
  20
  
    
  private final static int MAX_MEMORY    = 6*1024*1024; // 6MB max for the MitM table


  		




  
  21
  
    
  private final static double MAX_SEARCH = 3000000.0;   // max 3mln positions back-searched


  		




  21
  22
  
    

  		




  22
  
  
    
  private final static int MAX_MEMORY = 6*1024*1024; // 6MB max for the MitM table


  		




  23
  
  
    
  private final static int MAX_LENGTH = 10;


  		




  
  23
  
    
  private final MitmTable mTable;


  		




  24
  24
  
    
  private final SolvedObject mObject;


  		




  25
  25
  
    
  private final int[][] mQuatMult;


  		




  
  26
  
    
  private int mForwardDepth, mBackwardDepth;


  		




  26
  27
  
    

  		




  27
  28
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  28
  29
  
    

  		




  ......




  37
  38
  
    

  		




  38
  39
  
    
    for(int i=0; i<numQuats; i++)


  		




  39
  40
  
    
      for(int j=0; j<numQuats; j++) mQuatMult[i][j] = mulQuat(i,j);


  		




  
  41
  
    

  		




  
  42
  
    
    int numCubits = mObject.getCubitPositions().length;


  		




  
  43
  
    
    double tmp = Math.log(numQuats) / Math.log(2);


  		




  
  44
  
    
    double numBytes = numCubits*tmp/8;


  		




  
  45
  
    
    int bytesPerEntry = (int)Math.ceil(numBytes);  // this many bytes will be needed to store


  		




  
  46
  
    
                                                   // one position in the MiTM table


  		




  
  47
  
    
    mTable  = new MitmTable(bytesPerEntry);


  		




  40
  48
  
    
    }


  		




  41
  49
  
    

  		




  42
  50
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  ......




  91
  99
  
    

  		




  92
  100
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  93
  101
  
    

  		




  94
  
  
    
  private int computeForwardDepth()


  		




  
  102
  
    
  void prepareForSolution(int[] startingQuats)


  		




  95
  103
  
    
    {


  		




  96
  
  
    
    Static4D[] quats = mObject.getQuats();


  		




  97
  
  
    
    int numQuats = quats.length;


  		




  98
  
  
    
    int numCubits = mObject.getCubitPositions().length;


  		




  
  104
  
    
    mForwardDepth = computeForwardDepth();


  		




  
  105
  
    
    mObject.setUpStartingQuats(startingQuats);


  		




  
  106
  
    
    }


  		




  99
  107
  
    

  		




  100
  
  
    
    double tmp = Math.log(numQuats) / LOG2;


  		




  101
  
  
    
    double numBytes = numCubits*tmp/8;


  		




  102
  
  
    
    int numBytesInt = (int)Math.ceil(numBytes);  // this many bytes will be needed to store


  		




  103
  
  
    
                                                 // one position in the MiTM table


  		




  
  108
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  
  109
  
    

  		




  
  110
  
    
  void prepareForPhase(int[][] endQuats)


  		




  
  111
  
    
    {


  		




  
  112
  
    
    mBackwardDepth = computeBackwardDepth(endQuats);


  		




  
  113
  
    
    }


  		




  
  114
  
    

  		




  
  115
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  104
  116
  
    

  		




  
  117
  
    
  private int computeForwardDepth()


  		




  
  118
  
    
    {


  		




  
  119
  
    
    int bytesPerEntry = mTable.getBytesPerEntry();


  		




  105
  120
  
    
    int branchingFactor = mObject.getBranchingFactor();


  		




  106
  
  
    
    int t = MAX_MEMORY/numBytesInt;


  		




  
  121
  
    
    int t = MAX_MEMORY/bytesPerEntry;


  		




  107
  122
  
    
    double maxDepth = Math.log(t) / Math.log(branchingFactor);


  		




  
  123
  
    
    return (int)maxDepth;


  		




  
  124
  
    
    }


  		




  
  125
  
    

  		




  
  126
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  
  127
  
    
// how deep we can search our tree of moves 'backward' (from any one of the positions described by


  		




  
  128
  
    
// 'endQuats')


  		




  
  129
  
    

  		




  
  130
  
    
  private int computeBackwardDepth(int[][] endQuats)


  		




  
  131
  
    
    {


  		




  
  132
  
    
    int multiplier = 1;


  		




  
  133
  
    

  		




  
  134
  
    
    for( int[] quats : endQuats )


  		




  
  135
  
    
      if( quats!=null ) multiplier *= quats.length;


  		




  
  136
  
    

  		




  
  137
  
    
    int branchingFactor = mObject.getBranchingFactor();


  		




  
  138
  
    
    double maxDepth = Math.log(MAX_SEARCH/multiplier) / Math.log(branchingFactor);


  		




  108
  139
  
    

  		




  109
  140
  
    
    return (int)maxDepth;


  		




  110
  141
  
    
    }


  		




  ......




  123
  154
  
    

  		




  124
  155
  
    
  private int[][] solution(int[][] endQuats, int maxlen, OperatingSystemInterface osi)


  		




  125
  156
  
    
    {


  		




  126
  
  
    
    int forward_depth = computeForwardDepth();


  		




  
  157
  
    
    float tmp = ((float)(mForwardDepth*maxlen))/(mForwardDepth+mBackwardDepth);


  		




  
  158
  
    
    int tmpForward = (int)Math.ceil(tmp);


  		




  
  159
  
    
    int tmpBackward= mForwardDepth+mBackwardDepth - tmpForward;


  		




  127
  160
  
    

  		




  128
  
  
    
    // TODO


  		




  129
  
  
    
    return null;


  		




  
  161
  
    
    mTable.clear();


  		




  
  162
  
    
    mTable.build(mObject);


  		




  
  163
  
    
    return mTable.tryReaching(mObject,endQuats,tmpBackward,osi);


  		




  130
  164
  
    
    }


  		




  131
  165
  
    

  		




  132
  166
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  ......




  134
  168
  
    

  		




  135
  169
  
    
  private int[][] findSol(int[][] endQuats, int maxlen, OperatingSystemInterface osi)


  		




  136
  170
  
    
    {


  		




  137
  
  
    
    int[][] solution = solution(endQuats,maxlen,osi);


  		




  
  171
  
    
    int[][] s = solution(endQuats,maxlen,osi);


  		




  138
  172
  
    

  		




  139
  
  
    
    if( solution!=null )


  		




  
  173
  
    
    if( s!=null )


  		




  140
  174
  
    
      {


  		




  141
  
  
    
      for(int[] m : solution) mObject.rotateAllCubits(m[0],m[1],m[2]);


  		




  
  175
  
    
      for(int[] m : s) mObject.rotateAllCubits(m[0],m[1],m[2]);


  		




  142
  176
  
    
      }


  		




  143
  177
  
    

  		




  144
  
  
    
    return solution;


  		




  145
  
  
    
    }


  		




  146
  
  
    

  		




  147
  
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  148
  
  
    

  		




  149
  
  
    
  void setUpObjectStartingQuats(int[] quats)


  		




  150
  
  
    
    {


  		




  151
  
  
    
    mObject.setUpStartingQuats(quats);


  		




  
  178
  
    
    return s;


  		




  152
  179
  
    
    }


  		




  153
  180
  
    

  		




  154
  181
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  ......




  170
  197
  
    

  		




  171
  198
  
    
  int[][] findSolution(int[][] endQuats, OperatingSystemInterface osi)


  		




  172
  199
  
    
    {


  		




  173
  
  
    
    return findSol(endQuats,MAX_LENGTH,osi);


  		




  
  200
  
    
    return findSol(endQuats,mForwardDepth+mBackwardDepth,osi);


  		




  174
  201
  
    
    }


  		




  175
  202
  
    

  		




  176
  203
  
    
///////////////////////////////////////////////////////////////////////////////////////////////////


  		




  ......




  226
  253
  
    
  private boolean solveAnySubphase(int[][] endQuats, boolean[] solved, int sub, int numSubphases, int[][] tmp,


  		




  227
  254
  
    
                                   int[][][] solution, int[] whichSubphase, OperatingSystemInterface osi)


  		




  228
  255
  
    
    {


  		




  
  256
  
    
    int maxDepth = mForwardDepth + mBackwardDepth;


  		




  229
  257
  
    
    int numQuats = endQuats.length;


  		




  230
  258
  
    
    System.arraycopy(endQuats, 0, tmp, 0, numQuats);


  		




  231
  259
  
    

  		




  232
  
  
    
    for(int l=1; l<=MAX_LENGTH; l++)


  		




  
  260
  
    
    for(int l=0; l<=maxDepth; l++)


  		




  233
  261
  
    
      for(int p=0; p<numSubphases; p++)


  		




  234
  262
  
    
        if( !solved[p] )


  		




  235
  263
  
    
          {


  		












  

    
      src/main/java/org/distorted/objectlib/algsolvers/PhasedSolver.java
    
  





  188
  188
  
    
      endQuats[c] = figureOutEndQuatIndices(mode,quats[c],phase,c);


  		




  189
  189
  
    
      }


  		




  190
  190
  
    

  		




  
  191
  
    
    mFinder.prepareForPhase(endQuats);


  		




  
  192
  
    

  		




  191
  193
  
    
    if( numSubphases>1 )


  		




  192
  194
  
    
      {


  		




  193
  195
  
    
      return mFinder.findSolutionSubphases(endQuats, p, numSubphases, osi);


  		




  ......




  204
  206
  
    
  public int[][][] solution(int[] quats, OperatingSystemInterface osi)


  		




  205
  207
  
    
    {


  		




  206
  208
  
    
    int[][][] solution_moves = new int[mNumPhases][][];


  		




  207
  
  
    
    mFinder.setUpObjectStartingQuats(quats);


  		




  
  209
  
    
    mFinder.prepareForSolution(quats);


  		




  208
  210
  
    

  		




  209
  211
  
    
    for(int i=0; i<mNumPhases; i++)


  		




  210
  212
  
    
      {


  		












Also available in:  Unified diff