Project

General

Profile

Download (15 KB) Statistics
| Branch: | Revision:

distorted-objectlib / src / main / java / org / distorted / objectlib / tablebases / TablebasesPruning.java @ cd595931

1 00947987 Leszek Koltunski
///////////////////////////////////////////////////////////////////////////////////////////////////
2
// Copyright 2023 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.tablebases;
11
12 884b702b Leszek Koltunski
import android.content.res.Resources;
13 00947987 Leszek Koltunski
14 884b702b Leszek Koltunski
import java.io.ByteArrayOutputStream;
15
import java.io.IOException;
16
import java.io.InputStream;
17 00947987 Leszek Koltunski
18
///////////////////////////////////////////////////////////////////////////////////////////////////
19
20 f079bf77 Leszek Koltunski
public abstract class TablebasesPruning extends TablebasesAbstract
21 884b702b Leszek Koltunski
{
22 bdcb662f Leszek Koltunski
  private final int mGodsNumber;
23
24 884b702b Leszek Koltunski
  private boolean mInitialized;
25 f079bf77 Leszek Koltunski
  private PruningTable[] mHighTables;
26
  private PruningTable[] mMidTables;
27 bdcb662f Leszek Koltunski
  private int mLowestHigh, mHighestMid, mLowestMid;
28 00947987 Leszek Koltunski
29 15d1f6ad Leszek Koltunski
///////////////////////////////////////////////////////////////////////////////////////////////////
30
31 f079bf77 Leszek Koltunski
  abstract int[] getMidPruningLevels();
32
  abstract int[] getHighPruningLevels();
33
  abstract int getGodsNumber();
34 bdcb662f Leszek Koltunski
  abstract boolean moveCanProceed(int lastA, int lastL, int currA, int currL);
35 15d1f6ad Leszek Koltunski
36 00947987 Leszek Koltunski
///////////////////////////////////////////////////////////////////////////////////////////////////
37
38 f079bf77 Leszek Koltunski
  private PruningTable createPruningTable(Resources res, int id)
39 00947987 Leszek Koltunski
    {
40 884b702b Leszek Koltunski
    InputStream stream = res.openRawResource(id);
41
    ByteArrayOutputStream buffer = new ByteArrayOutputStream();
42 00947987 Leszek Koltunski
43 884b702b Leszek Koltunski
    int nRead;
44
    byte[] tmp = new byte[16384];
45 00947987 Leszek Koltunski
46 884b702b Leszek Koltunski
    try
47 00947987 Leszek Koltunski
      {
48 884b702b Leszek Koltunski
      while ((nRead = stream.read(tmp, 0, tmp.length)) != -1)
49 00947987 Leszek Koltunski
        {
50 884b702b Leszek Koltunski
        buffer.write(tmp, 0, nRead);
51 00947987 Leszek Koltunski
        }
52 884b702b Leszek Koltunski
      stream.close();
53
      byte[] data = buffer.toByteArray();
54
      buffer.close();
55 f079bf77 Leszek Koltunski
      return new PruningTable(data);
56 884b702b Leszek Koltunski
      }
57
    catch(IOException ex)
58 00947987 Leszek Koltunski
      {
59 884b702b Leszek Koltunski
      mInitialized = false;
60 f079bf77 Leszek Koltunski
      return null;
61 00947987 Leszek Koltunski
      }
62 884b702b Leszek Koltunski
    }
63 00947987 Leszek Koltunski
64 884b702b Leszek Koltunski
///////////////////////////////////////////////////////////////////////////////////////////////////
65 00947987 Leszek Koltunski
66 f079bf77 Leszek Koltunski
  public TablebasesPruning()
67 884b702b Leszek Koltunski
    {
68
    super();
69 f079bf77 Leszek Koltunski
    mGodsNumber = getGodsNumber();
70 7363eaa6 Leszek Koltunski
    mInitialized = false;
71 00947987 Leszek Koltunski
    }
72
73
///////////////////////////////////////////////////////////////////////////////////////////////////
74
75 f079bf77 Leszek Koltunski
  public TablebasesPruning(Resources res, int[] midIDs, int[] highIDs)
76 00947987 Leszek Koltunski
    {
77 884b702b Leszek Koltunski
    super();
78
79 f079bf77 Leszek Koltunski
    int mid = midIDs !=null ? midIDs.length  : 0;
80
    int high= highIDs!=null ? highIDs.length : 0;
81
82
    mMidTables = mid >0 ? new PruningTable[mid] : null;
83
    mHighTables= high>0 ? new PruningTable[high]: null;
84
    mGodsNumber = getGodsNumber();
85 884b702b Leszek Koltunski
    mInitialized = true;
86
87 f079bf77 Leszek Koltunski
    for(int i=0; i<mid ; i++) mMidTables[i] = createPruningTable(res,midIDs[i] );
88
    for(int i=0; i<high; i++) mHighTables[i]= createPruningTable(res,highIDs[i]);
89 bdcb662f Leszek Koltunski
90
    computeLowHigh();
91 00947987 Leszek Koltunski
    }
92
93 15d1f6ad Leszek Koltunski
///////////////////////////////////////////////////////////////////////////////////////////////////
94
95
  public byte[][] getPacked()
96
    {
97 7363eaa6 Leszek Koltunski
    if( !mInitialized )
98
      {
99 f079bf77 Leszek Koltunski
      int[] midLevels = getMidPruningLevels();
100
      int numMidLevels= midLevels!=null ? midLevels.length : 0;
101
      int[] highLevels = getHighPruningLevels();
102
      int numHighLevels= highLevels!=null ? highLevels.length : 0;
103 7363eaa6 Leszek Koltunski
      int maxLevel = 0;
104 15d1f6ad Leszek Koltunski
105 f079bf77 Leszek Koltunski
      if( highLevels!=null )
106
        {
107
        for( int l : highLevels )
108
          if( l>maxLevel ) maxLevel = l;
109
        }
110
      else
111
        {
112
        if( midLevels!=null )
113
          for( int l : midLevels )
114
            if( l>maxLevel ) maxLevel = l;
115
        }
116 15d1f6ad Leszek Koltunski
117 7363eaa6 Leszek Koltunski
      createTablebase(maxLevel);
118 f079bf77 Leszek Koltunski
      mMidTables = numMidLevels >0 ? new PruningTable[numMidLevels ] : null;
119
      mHighTables= numHighLevels>0 ? new PruningTable[numHighLevels] : null;
120 15d1f6ad Leszek Koltunski
121 f079bf77 Leszek Koltunski
      for(int i=0; i<numMidLevels; i++)
122
        mMidTables[i] = new PruningTable(mTablebase,midLevels[i]);
123
      for(int i=0; i<numHighLevels; i++)
124
        mHighTables[i] = new PruningTable(mTablebase,highLevels[i]);
125 15d1f6ad Leszek Koltunski
126 bdcb662f Leszek Koltunski
      computeLowHigh();
127
128 7363eaa6 Leszek Koltunski
      mInitialized = true;
129 15d1f6ad Leszek Koltunski
      }
130
131 f079bf77 Leszek Koltunski
    int midNum  = mMidTables !=null ? mMidTables.length  : 0;
132
    int highNum = mHighTables!=null ? mHighTables.length : 0;
133
    byte[][] data = new byte[midNum+highNum][];
134
135
    for(int i=0; i<midNum ; i++) data[i       ] = mMidTables[i].getPacked();
136
    for(int i=0; i<highNum; i++) data[i+midNum] = mHighTables[i].getPacked();
137 7363eaa6 Leszek Koltunski
138 15d1f6ad Leszek Koltunski
    return data;
139
    }
140
141 00947987 Leszek Koltunski
///////////////////////////////////////////////////////////////////////////////////////////////////
142
143 bdcb662f Leszek Koltunski
  private void computeLowHigh()
144
    {
145
    mLowestHigh = mGodsNumber+1;
146
    int numHigh = mHighTables==null ? 0 : mHighTables.length;
147
148
    for( int i=0; i<numHigh; i++ )
149
      {
150
      int level = mHighTables[i].getLevel();
151
      if( i==0 || level<mLowestHigh ) mLowestHigh=level;
152
      }
153
154
    mLowestMid = 0;
155
    mHighestMid= 0;
156
    int numMid = mMidTables==null ? 0 : mMidTables.length;
157
158
    for( int i=0; i<numMid; i++ )
159
      {
160
      int level = mMidTables[i].getLevel();
161
      if( i==0 || level<mLowestMid  ) mLowestMid =level;
162
      if( i==0 || level>mHighestMid ) mHighestMid=level;
163
      }
164
    }
165
166
///////////////////////////////////////////////////////////////////////////////////////////////////
167
168
  public int traverseDownTable(int index, PruningTable[] tables, int tableIndex, int lastA, int lastR, int[] move, int[] tmpQuats)
169
    {
170
    int[] quats = getQuats(index);
171
    int numQuats = quats.length;
172
173
    move[0]=0;
174
    move[1]=0;
175
    move[2]=1;
176
    move[3]=1;
177
178
    for(int ax=0; ax<mNumAxis; ax++)
179
      for(int cubit=0; cubit<mNumCubits; cubit++)
180
        mRotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax);
181
182
    for(int s=0; s<mScalingFactor; s++)
183
      {
184
      int ax    = move[0];
185
      int layer = move[1];
186
      int quat  = move[3];
187
188
      if( mRotatable[ax][layer] && moveCanProceed(lastA,lastR,move[0],move[1]) )
189
        {
190
        int bitLayer = (1<<layer);
191
        System.arraycopy(quats, 0, tmpQuats, 0, numQuats);
192
193
        for(int cubit=0; cubit<mNumCubits; cubit++)
194
          if( mRotRow[cubit][ax]==bitLayer )
195
            {
196
            int currQuat = tmpQuats[cubit];
197
            int newQuat = getMultQuat(quat,currQuat);
198
            tmpQuats[cubit] = newQuat;
199
            }
200
201
        int childIndex = getIndex(tmpQuats);
202
203
        if( tableIndex>0 )
204
          {
205
          if( tables[tableIndex-1].contains(childIndex) ) return childIndex;
206
          }
207
        else if( !tables[0].contains(childIndex) )
208
          {
209
          if( tables.length<=1 || !tables[1].contains(childIndex) ) return childIndex;
210
          }
211
        }
212
213
      getNextAxisLayerAngleQuat(move);
214
      }
215
216
    return -1;
217
    }
218
219
///////////////////////////////////////////////////////////////////////////////////////////////////
220
221
  private int traversePruningBlock(int[][] moves, PruningTable[] tables, int tableIndex, int index, int lastA, int lastR)
222 00947987 Leszek Koltunski
    {
223 bdcb662f Leszek Koltunski
    int movesIndex = 1;
224 aa0757b6 Leszek Koltunski
    int[] move, tmpQuats = new int[mNumCubits];
225 bdcb662f Leszek Koltunski
226
    do
227
      {
228 aa0757b6 Leszek Koltunski
      move  = moves[movesIndex++];
229 bdcb662f Leszek Koltunski
      index = traverseDownTable(index,tables,tableIndex,lastA,lastR,move,tmpQuats);
230
      lastA = move[0];
231
      lastR = move[1];
232
      tableIndex--;
233
      }
234
    while( tableIndex>=0 );
235
236
    return index;
237
    }
238
239
///////////////////////////////////////////////////////////////////////////////////////////////////
240
// ret: [0][] --> (new index,new depth,?,?) ; [1...N-1][] --> moves. (or null if index not in High)
241
242
  private int[][] traverseBlock(int index, PruningTable[] tables, int lastA, int lastR)
243
    {
244
    int num = (tables==null) ? 0 : tables.length;
245
    int tableIndex = -1;
246
247
    for( int i=0; i<num; i++ )
248
      if( tables[i].contains(index) )
249
        {
250
        tableIndex = i;
251
        break;
252
        }
253
254 b9633e5f Leszek Koltunski
    if( tableIndex<0 ) return null;
255 bdcb662f Leszek Koltunski
256
    int[][] ret = new int[tableIndex+2][4];
257
    ret[0][1] = tables[0].getLevel()-1;
258
    ret[0][0] = traversePruningBlock(ret,tables,tableIndex,index,lastA, lastR);
259
260
    return ret;
261
    }
262
263
///////////////////////////////////////////////////////////////////////////////////////////////////
264
265
  private int midTablesContain(int index)
266
    {
267
    int num = mMidTables.length;
268
269
    for( int i=0; i<num; i++ )
270
      if( mMidTables[i].contains(index) )
271
        return i;
272
273
    return -1;
274
    }
275
276
///////////////////////////////////////////////////////////////////////////////////////////////////
277
278
  private boolean jumpMidZeroRecursive(int index, int jump, int depth, int lastA, int lastR, int[][] solution)
279
    {
280 aa0757b6 Leszek Koltunski
    int[] quats   = getQuats(index);
281
    int numQuats  = quats.length;
282
    int[] move    = solution[depth];
283
    int[] tmp     = new int[mNumCubits];
284
    int[][] rotRow= new int[mNumCubits][mNumAxis];
285 bdcb662f Leszek Koltunski
286
    move[0]=0;
287
    move[1]=0;
288
    move[2]=1;
289
    move[3]=1;
290
291
    for(int ax=0; ax<mNumAxis; ax++)
292
      for(int cubit=0; cubit<mNumCubits; cubit++)
293 aa0757b6 Leszek Koltunski
        rotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax);
294 bdcb662f Leszek Koltunski
295
    for(int s=0; s<mScalingFactor; s++)
296
      {
297
      int ax    = move[0];
298
      int layer = move[1];
299
      int quat  = move[3];
300
301
      if( mRotatable[ax][layer] && moveCanProceed(lastA,lastR,ax,layer) )
302
        {
303
        int bitLayer = (1<<layer);
304
        System.arraycopy(quats, 0, tmp, 0, numQuats);
305
306
        for(int cubit=0; cubit<mNumCubits; cubit++)
307 aa0757b6 Leszek Koltunski
          if( rotRow[cubit][ax]==bitLayer )
308 bdcb662f Leszek Koltunski
            {
309
            int currQuat = tmp[cubit];
310
            int newQuat = getMultQuat(quat,currQuat);
311
            tmp[cubit] = newQuat;
312
            }
313
314
        int childIndex = getIndex(tmp);
315
316
        if( childIndex==0 )
317
          {
318
          solution[0][0] = childIndex;
319
          solution[0][1] = 0;
320
          return true;
321
          }
322
323
        int containingTable = midTablesContain(childIndex);
324
325
        if( containingTable>=0 )
326
          {
327
          solution[0][0] = childIndex;
328
          solution[0][1] = mMidTables[containingTable].getLevel();
329
          return true;
330
          }
331
332
        if( jump>1 && jumpMidZeroRecursive(childIndex, jump-1, depth+1, ax, layer, solution) )
333
          {
334
          return true;
335
          }
336
        }
337
338
      getNextAxisLayerAngleQuat(move);
339
      }
340
341
    return false;
342
    }
343
344
///////////////////////////////////////////////////////////////////////////////////////////////////
345 cd595931 Leszek Koltunski
// ret: [0][] --> (new index,new depth,num moves,?) ; [1...N-1][] --> moves.
346 bdcb662f Leszek Koltunski
347
  private int[][] jumpToMidOrZero(int index, int maxJump, int lastA, int lastR)
348
    {
349 aa0757b6 Leszek Koltunski
    if( midTablesContain(index)>=0 ) return null;
350
351 bdcb662f Leszek Koltunski
    int[][] solution = new int[maxJump+1][4];
352
353 b9633e5f Leszek Koltunski
    for(int i=1; i<=maxJump; i++)
354 bdcb662f Leszek Koltunski
      if( jumpMidZeroRecursive(index,i,1,lastA,lastR,solution) )
355 aa0757b6 Leszek Koltunski
        {
356 cd595931 Leszek Koltunski
        solution[0][2] = i;
357 bdcb662f Leszek Koltunski
        return solution;
358 aa0757b6 Leszek Koltunski
        }
359 bdcb662f Leszek Koltunski
360
    return null;
361
    }
362
363
///////////////////////////////////////////////////////////////////////////////////////////////////
364
365
  private boolean jumpZeroRecursive(int index, int jump, int depth, int lastA, int lastR, int[][] solution)
366
    {
367
    int[] quats  = getQuats(index);
368
    int numQuats = quats.length;
369
    int[] move   = solution[depth];
370
    int[] tmp    = new int[mNumCubits];
371 aa0757b6 Leszek Koltunski
    int[][]rotRow= new int[mNumCubits][mNumAxis];
372 bdcb662f Leszek Koltunski
373
    move[0]=0;
374
    move[1]=0;
375
    move[2]=1;
376
    move[3]=1;
377
378
    for(int ax=0; ax<mNumAxis; ax++)
379
      for(int cubit=0; cubit<mNumCubits; cubit++)
380 aa0757b6 Leszek Koltunski
        rotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax);
381 bdcb662f Leszek Koltunski
382
    for(int s=0; s<mScalingFactor; s++)
383
      {
384
      int ax    = move[0];
385
      int layer = move[1];
386
      int quat  = move[3];
387
388
      if( mRotatable[ax][layer] && moveCanProceed(lastA,lastR,move[0],move[1]) )
389
        {
390
        int bitLayer = (1<<layer);
391
        System.arraycopy(quats, 0, tmp, 0, numQuats);
392
393
        for(int cubit=0; cubit<mNumCubits; cubit++)
394 aa0757b6 Leszek Koltunski
          if( rotRow[cubit][ax]==bitLayer )
395 bdcb662f Leszek Koltunski
            {
396
            int currQuat = tmp[cubit];
397
            int newQuat = getMultQuat(quat,currQuat);
398
            tmp[cubit] = newQuat;
399
            }
400
401
        int childIndex = getIndex(tmp);
402 aa0757b6 Leszek Koltunski
        if( childIndex==0 ) return true;
403
        if( jump>1 && jumpZeroRecursive(childIndex, jump-1, depth+1, ax, layer, solution) ) return true;
404 bdcb662f Leszek Koltunski
        }
405
406
      getNextAxisLayerAngleQuat(move);
407
      }
408
409
    return false;
410
    }
411
412
///////////////////////////////////////////////////////////////////////////////////////////////////
413 aa0757b6 Leszek Koltunski
// ret: [0][] --> (numMoves,old depth,?,?) ; [1...N-1][] --> moves.
414 bdcb662f Leszek Koltunski
415
  private int[][] jumpToZero(int index, int maxJump, int lastA, int lastR)
416
    {
417
    int[][] solution = new int[maxJump+1][4];
418
419 b9633e5f Leszek Koltunski
    for(int i=1; i<=maxJump; i++)
420 bdcb662f Leszek Koltunski
      if( jumpZeroRecursive(index,i,1,lastA,lastR,solution) )
421 aa0757b6 Leszek Koltunski
        {
422
        solution[0][0] = i;
423 bdcb662f Leszek Koltunski
        return solution;
424 aa0757b6 Leszek Koltunski
        }
425 bdcb662f Leszek Koltunski
426 00947987 Leszek Koltunski
    return null;
427
    }
428 bdcb662f Leszek Koltunski
429
///////////////////////////////////////////////////////////////////////////////////////////////////
430
431
  private int[][] concatenateMoves(int[][] high, int[][] jump1, int[][] mid, int[][] jump2)
432
    {
433
    int len1 = high ==null ? 0 : high.length-1;
434 cd595931 Leszek Koltunski
    int len2 = jump1==null ? 0 : jump1[0][2];
435 bdcb662f Leszek Koltunski
    int len3 = mid  ==null ? 0 : mid.length-1;
436 aa0757b6 Leszek Koltunski
    int len4 = jump2==null ? 0 : jump2[0][0];
437 bdcb662f Leszek Koltunski
438
    int[][] moves = new int[len1+len2+len3+len4][];
439
    int index = 0;
440
441
    for(int i=0; i<len1; i++) moves[index++] =  high[i+1];
442
    for(int i=0; i<len2; i++) moves[index++] = jump1[i+1];
443
    for(int i=0; i<len3; i++) moves[index++] =   mid[i+1];
444
    for(int i=0; i<len4; i++) moves[index++] = jump2[i+1];
445
446
    convertMoves(moves);
447
448
    return moves;
449
    }
450
451
///////////////////////////////////////////////////////////////////////////////////////////////////
452
453
  public int[][] solution(int index, int[] extra)
454
    {
455
    if( index==0 ) return null;
456
    int lastA=-1, lastR=0;
457
    int[][] highMoves = traverseBlock(index,mHighTables,lastA,lastR);
458
459
    if( highMoves!=null )
460
      {
461
      index = highMoves[0][0];
462
      int len = highMoves.length;
463
      lastA = highMoves[len-1][0];
464
      lastR = highMoves[len-1][1];
465
      }
466
467
    int maxJump = Math.max(mLowestHigh-1-mHighestMid,mLowestMid/2);
468
    int[][] jump1Moves = jumpToMidOrZero(index,maxJump,lastA,lastR);
469
470
    if( jump1Moves!=null )
471
      {
472
      if( jump1Moves[0][0]==0 )
473
        {
474 cd595931 Leszek Koltunski
        return concatenateMoves(null,jump1Moves,null,null);
475 bdcb662f Leszek Koltunski
        }
476
      if( jump1Moves[0][1]==mLowestMid )
477
        {
478
        int[][] jump2Moves = jumpToZero(index,mLowestMid-1,-1,0);
479
        if( jump2Moves==null ) throw new RuntimeException("1 error jumping to 0");
480
        return concatenateMoves(null,null,null,jump2Moves);
481
        }
482
483
      index = jump1Moves[0][0];
484 cd595931 Leszek Koltunski
      int len = jump1Moves[0][2];
485
      lastA = jump1Moves[len][0];
486
      lastR = jump1Moves[len][1];
487 bdcb662f Leszek Koltunski
      }
488
489
    int[][] midMoves = traverseBlock(index,mMidTables,lastA,lastR);
490
    if( midMoves!=null )
491
      {
492
      index = midMoves[0][0];
493
      int len = midMoves.length;
494
      lastA = midMoves[len-1][0];
495
      lastR = midMoves[len-1][1];
496
      }
497
    else throw new RuntimeException("error traversing mid Tables");
498
499
    int[][] jump2Moves = jumpToZero(index,mLowestMid-1,lastA,lastR);
500
    if( jump2Moves==null ) throw new RuntimeException("2 error jumping to 0");
501
    return concatenateMoves(highMoves,jump1Moves,midMoves,jump2Moves);
502
    }
503 00947987 Leszek Koltunski
}