1
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
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
|
import android.content.res.Resources;
|
13
|
|
14
|
import java.io.ByteArrayOutputStream;
|
15
|
import java.io.IOException;
|
16
|
import java.io.InputStream;
|
17
|
|
18
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
19
|
|
20
|
public abstract class TablebasesPruning extends TablebasesAbstract
|
21
|
{
|
22
|
private final int mGodsNumber;
|
23
|
|
24
|
private boolean mInitialized;
|
25
|
private PruningTable[] mHighTables;
|
26
|
private PruningTable[] mMidTables;
|
27
|
private int mLowestHigh, mHighestMid, mLowestMid;
|
28
|
|
29
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
30
|
|
31
|
abstract int[] getMidPruningLevels();
|
32
|
abstract int[] getHighPruningLevels();
|
33
|
abstract int getGodsNumber();
|
34
|
abstract boolean moveCanProceed(int lastA, int lastL, int currA, int currL);
|
35
|
|
36
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
37
|
|
38
|
private PruningTable createPruningTable(Resources res, int id)
|
39
|
{
|
40
|
InputStream stream = res.openRawResource(id);
|
41
|
ByteArrayOutputStream buffer = new ByteArrayOutputStream();
|
42
|
|
43
|
int nRead;
|
44
|
byte[] tmp = new byte[16384];
|
45
|
|
46
|
try
|
47
|
{
|
48
|
while ((nRead = stream.read(tmp, 0, tmp.length)) != -1)
|
49
|
{
|
50
|
buffer.write(tmp, 0, nRead);
|
51
|
}
|
52
|
stream.close();
|
53
|
byte[] data = buffer.toByteArray();
|
54
|
buffer.close();
|
55
|
return new PruningTable(data);
|
56
|
}
|
57
|
catch(IOException ex)
|
58
|
{
|
59
|
mInitialized = false;
|
60
|
return null;
|
61
|
}
|
62
|
}
|
63
|
|
64
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
65
|
|
66
|
public TablebasesPruning()
|
67
|
{
|
68
|
super();
|
69
|
mGodsNumber = getGodsNumber();
|
70
|
mInitialized = false;
|
71
|
}
|
72
|
|
73
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
74
|
|
75
|
public TablebasesPruning(Resources res, int[] midIDs, int[] highIDs)
|
76
|
{
|
77
|
super();
|
78
|
|
79
|
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
|
mInitialized = true;
|
86
|
|
87
|
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
|
|
90
|
computeLowHigh();
|
91
|
}
|
92
|
|
93
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
94
|
|
95
|
public byte[][] getPacked()
|
96
|
{
|
97
|
if( !mInitialized )
|
98
|
{
|
99
|
int[] midLevels = getMidPruningLevels();
|
100
|
int numMidLevels= midLevels!=null ? midLevels.length : 0;
|
101
|
int[] highLevels = getHighPruningLevels();
|
102
|
int numHighLevels= highLevels!=null ? highLevels.length : 0;
|
103
|
int maxLevel = 0;
|
104
|
|
105
|
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
|
|
117
|
createTablebase(maxLevel);
|
118
|
mMidTables = numMidLevels >0 ? new PruningTable[numMidLevels ] : null;
|
119
|
mHighTables= numHighLevels>0 ? new PruningTable[numHighLevels] : null;
|
120
|
|
121
|
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
|
|
126
|
computeLowHigh();
|
127
|
|
128
|
mInitialized = true;
|
129
|
}
|
130
|
|
131
|
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
|
|
138
|
return data;
|
139
|
}
|
140
|
|
141
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
142
|
|
143
|
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
|
{
|
223
|
int movesIndex = 1;
|
224
|
int[] move, tmpQuats = new int[mNumCubits];
|
225
|
|
226
|
do
|
227
|
{
|
228
|
move = moves[movesIndex++];
|
229
|
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
|
if( tableIndex<0 ) return null;
|
255
|
|
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
|
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
|
|
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
|
rotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax);
|
294
|
|
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
|
if( rotRow[cubit][ax]==bitLayer )
|
308
|
{
|
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
|
android.util.Log.e("D", "1 jumped to mid: index="+childIndex);
|
319
|
|
320
|
solution[0][0] = childIndex;
|
321
|
solution[0][1] = 0;
|
322
|
return true;
|
323
|
}
|
324
|
|
325
|
int containingTable = midTablesContain(childIndex);
|
326
|
|
327
|
if( containingTable>=0 )
|
328
|
{
|
329
|
android.util.Log.e("D", "2 jumped to mid: index="+childIndex);
|
330
|
|
331
|
solution[0][0] = childIndex;
|
332
|
solution[0][1] = mMidTables[containingTable].getLevel();
|
333
|
return true;
|
334
|
}
|
335
|
|
336
|
if( jump>1 && jumpMidZeroRecursive(childIndex, jump-1, depth+1, ax, layer, solution) )
|
337
|
{
|
338
|
return true;
|
339
|
}
|
340
|
}
|
341
|
|
342
|
getNextAxisLayerAngleQuat(move);
|
343
|
}
|
344
|
|
345
|
return false;
|
346
|
}
|
347
|
|
348
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
349
|
// ret: [0][] --> (num moves,old depth,?,?) ; [1...N-1][] --> moves.
|
350
|
|
351
|
private int[][] jumpToMidOrZero(int index, int maxJump, int lastA, int lastR)
|
352
|
{
|
353
|
if( midTablesContain(index)>=0 ) return null;
|
354
|
|
355
|
int[][] solution = new int[maxJump+1][4];
|
356
|
|
357
|
for(int i=1; i<=maxJump; i++)
|
358
|
if( jumpMidZeroRecursive(index,i,1,lastA,lastR,solution) )
|
359
|
{
|
360
|
solution[0][0] = i;
|
361
|
return solution;
|
362
|
}
|
363
|
|
364
|
return null;
|
365
|
}
|
366
|
|
367
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
368
|
|
369
|
private boolean jumpZeroRecursive(int index, int jump, int depth, int lastA, int lastR, int[][] solution)
|
370
|
{
|
371
|
int[] quats = getQuats(index);
|
372
|
int numQuats = quats.length;
|
373
|
int[] move = solution[depth];
|
374
|
int[] tmp = new int[mNumCubits];
|
375
|
int[][]rotRow= new int[mNumCubits][mNumAxis];
|
376
|
|
377
|
move[0]=0;
|
378
|
move[1]=0;
|
379
|
move[2]=1;
|
380
|
move[3]=1;
|
381
|
|
382
|
if( jump==3 ) android.util.Log.e("D", "trying index="+index+" depth="+depth+" lastA="+lastA+" lastR="+lastR);
|
383
|
|
384
|
for(int ax=0; ax<mNumAxis; ax++)
|
385
|
for(int cubit=0; cubit<mNumCubits; cubit++)
|
386
|
rotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax);
|
387
|
/*
|
388
|
if( index==1719861 )
|
389
|
{
|
390
|
StringBuilder sb4 = new StringBuilder();
|
391
|
for(int a=0; a<mNumAxis; a++)
|
392
|
{
|
393
|
for(int c=0; c<mNumCubits; c++)
|
394
|
{
|
395
|
sb4.append(mRotRow[c][a]);
|
396
|
sb4.append(' ');
|
397
|
}
|
398
|
sb4.append("\n");
|
399
|
|
400
|
}
|
401
|
android.util.Log.e("D", "1 rotRows= \n"+sb4 );
|
402
|
}
|
403
|
*/
|
404
|
for(int s=0; s<mScalingFactor; s++)
|
405
|
{
|
406
|
int ax = move[0];
|
407
|
int layer = move[1];
|
408
|
int quat = move[3];
|
409
|
|
410
|
if( mRotatable[ax][layer] && moveCanProceed(lastA,lastR,move[0],move[1]) )
|
411
|
{
|
412
|
int bitLayer = (1<<layer);
|
413
|
System.arraycopy(quats, 0, tmp, 0, numQuats);
|
414
|
|
415
|
for(int cubit=0; cubit<mNumCubits; cubit++)
|
416
|
if( rotRow[cubit][ax]==bitLayer )
|
417
|
{
|
418
|
int currQuat = tmp[cubit];
|
419
|
int newQuat = getMultQuat(quat,currQuat);
|
420
|
tmp[cubit] = newQuat;
|
421
|
}
|
422
|
/*
|
423
|
if( depth==1 && ax==1 && layer==1 && move[2]==3 )
|
424
|
{
|
425
|
StringBuilder sb2 = new StringBuilder();
|
426
|
for(int i=0; i<8; i++) { sb2.append(' '); sb2.append(quats[i]); }
|
427
|
android.util.Log.e("D", " quats= "+sb2 );
|
428
|
|
429
|
StringBuilder sb3 = new StringBuilder();
|
430
|
for(int i=0; i<8; i++) { sb3.append(' '); sb3.append(tmp[i]); }
|
431
|
android.util.Log.e("D", " tmpQuats= "+sb3 );
|
432
|
|
433
|
|
434
|
|
435
|
android.util.Log.e("D", " index= "+index );
|
436
|
}
|
437
|
|
438
|
|
439
|
if( index==1719861 )
|
440
|
{
|
441
|
StringBuilder sb4 = new StringBuilder();
|
442
|
for(int a=0; a<mNumAxis; a++)
|
443
|
{
|
444
|
for(int c=0; c<mNumCubits; c++)
|
445
|
{
|
446
|
sb4.append(mRotRow[c][a]);
|
447
|
sb4.append(' ');
|
448
|
}
|
449
|
sb4.append("\n");
|
450
|
|
451
|
}
|
452
|
android.util.Log.e("D", "2 rotRows= \n"+sb4 );
|
453
|
}
|
454
|
*/
|
455
|
|
456
|
int childIndex = getIndex(tmp);
|
457
|
if( childIndex==0 ) return true;
|
458
|
if( jump>1 && jumpZeroRecursive(childIndex, jump-1, depth+1, ax, layer, solution) ) return true;
|
459
|
}
|
460
|
|
461
|
getNextAxisLayerAngleQuat(move);
|
462
|
}
|
463
|
|
464
|
return false;
|
465
|
}
|
466
|
|
467
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
468
|
// ret: [0][] --> (numMoves,old depth,?,?) ; [1...N-1][] --> moves.
|
469
|
|
470
|
private int[][] jumpToZero(int index, int maxJump, int lastA, int lastR)
|
471
|
{
|
472
|
int[][] solution = new int[maxJump+1][4];
|
473
|
|
474
|
for(int i=1; i<=maxJump; i++)
|
475
|
if( jumpZeroRecursive(index,i,1,lastA,lastR,solution) )
|
476
|
{
|
477
|
solution[0][0] = i;
|
478
|
return solution;
|
479
|
}
|
480
|
|
481
|
return null;
|
482
|
}
|
483
|
|
484
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
485
|
|
486
|
private int[][] concatenateMoves(int[][] high, int[][] jump1, int[][] mid, int[][] jump2)
|
487
|
{
|
488
|
int len1 = high ==null ? 0 : high.length-1;
|
489
|
int len2 = jump1==null ? 0 : jump1[0][0];
|
490
|
int len3 = mid ==null ? 0 : mid.length-1;
|
491
|
int len4 = jump2==null ? 0 : jump2[0][0];
|
492
|
|
493
|
int[][] moves = new int[len1+len2+len3+len4][];
|
494
|
int index = 0;
|
495
|
|
496
|
for(int i=0; i<len1; i++) moves[index++] = high[i+1];
|
497
|
for(int i=0; i<len2; i++) moves[index++] = jump1[i+1];
|
498
|
for(int i=0; i<len3; i++) moves[index++] = mid[i+1];
|
499
|
for(int i=0; i<len4; i++) moves[index++] = jump2[i+1];
|
500
|
|
501
|
convertMoves(moves);
|
502
|
|
503
|
return moves;
|
504
|
}
|
505
|
|
506
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
507
|
|
508
|
public int[][] solution(int index, int[] extra)
|
509
|
{
|
510
|
if( index==0 ) return null;
|
511
|
int lastA=-1, lastR=0;
|
512
|
int[][] highMoves = traverseBlock(index,mHighTables,lastA,lastR);
|
513
|
|
514
|
if( highMoves!=null )
|
515
|
{
|
516
|
index = highMoves[0][0];
|
517
|
int len = highMoves.length;
|
518
|
lastA = highMoves[len-1][0];
|
519
|
lastR = highMoves[len-1][1];
|
520
|
}
|
521
|
|
522
|
int maxJump = Math.max(mLowestHigh-1-mHighestMid,mLowestMid/2);
|
523
|
int[][] jump1Moves = jumpToMidOrZero(index,maxJump,lastA,lastR);
|
524
|
|
525
|
if( jump1Moves!=null )
|
526
|
{
|
527
|
if( jump1Moves[0][0]==0 )
|
528
|
{
|
529
|
return concatenateMoves(null,null,null,jump1Moves);
|
530
|
}
|
531
|
if( jump1Moves[0][1]==mLowestMid )
|
532
|
{
|
533
|
int[][] jump2Moves = jumpToZero(index,mLowestMid-1,-1,0);
|
534
|
if( jump2Moves==null ) throw new RuntimeException("1 error jumping to 0");
|
535
|
return concatenateMoves(null,null,null,jump2Moves);
|
536
|
}
|
537
|
|
538
|
index = jump1Moves[0][0];
|
539
|
int len = jump1Moves.length;
|
540
|
lastA = jump1Moves[len-1][0];
|
541
|
lastR = jump1Moves[len-1][1];
|
542
|
}
|
543
|
|
544
|
int[][] midMoves = traverseBlock(index,mMidTables,lastA,lastR);
|
545
|
if( midMoves!=null )
|
546
|
{
|
547
|
index = midMoves[0][0];
|
548
|
int len = midMoves.length;
|
549
|
lastA = midMoves[len-1][0];
|
550
|
lastR = midMoves[len-1][1];
|
551
|
}
|
552
|
else throw new RuntimeException("error traversing mid Tables");
|
553
|
|
554
|
android.util.Log.e("D", "index now="+index+" depth now "+midMoves[0][1]+" ax="+midMoves[1][0]+" row="+midMoves[1][1]+" angle="+midMoves[1][2]);
|
555
|
|
556
|
int[][] jump2Moves = jumpToZero(index,mLowestMid-1,lastA,lastR);
|
557
|
if( jump2Moves==null ) throw new RuntimeException("2 error jumping to 0");
|
558
|
return concatenateMoves(highMoves,jump1Moves,midMoves,jump2Moves);
|
559
|
}
|
560
|
}
|