Revision 5b9f1cec
Added by Leszek Koltunski over 2 years ago
| src/main/java/org/distorted/objectlib/tablebases/TBDino6.java | ||
|---|---|---|
| 14 | 14 |
import android.content.res.Resources; |
| 15 | 15 |
|
| 16 | 16 |
import org.distorted.library.type.Static3D; |
| 17 |
import org.distorted.objectlib.R; |
|
| 17 | 18 |
|
| 18 | 19 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 19 | 20 |
|
| 20 |
public class TBDino6 extends TablebasesAbstract
|
|
| 21 |
public class TBDino6 extends TablebasesPruning
|
|
| 21 | 22 |
{
|
| 23 |
private static final int INDEX_INVERTED = 13379863; // quats (0,10,0,10, 11,11,11,11, 0,10,0,10) |
|
| 24 |
|
|
| 22 | 25 |
private static final int[][] QUATS = |
| 23 | 26 |
{
|
| 24 | 27 |
{0,2,10,8, 1,4,6,7, 11,5,9,3},
|
| ... | ... | |
| 35 | 38 |
{4,11,7,9, 8,3,2,5, 6,10,1,0}
|
| 36 | 39 |
}; |
| 37 | 40 |
|
| 41 |
private int[][] mAngles; |
|
| 42 |
|
|
| 38 | 43 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 39 | 44 |
|
| 40 | 45 |
public TBDino6() |
| ... | ... | |
| 46 | 51 |
|
| 47 | 52 |
public TBDino6(Resources res) |
| 48 | 53 |
{
|
| 49 |
super(res,org.distorted.objectlib.R.raw.dino_3_tablebase);
|
|
| 54 |
super(res,new int[] {R.raw.dino_3_pruning3,R.raw.dino_3_pruning4},new int[] {R.raw.dino_3_pruning10});
|
|
| 50 | 55 |
} |
| 51 | 56 |
|
| 52 | 57 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 53 | 58 |
|
| 54 | 59 |
int[][] getBasicAngles() |
| 55 | 60 |
{
|
| 56 |
int[] tmp = {3,3,3};
|
|
| 57 |
return new int[][] { tmp,tmp,tmp,tmp };
|
|
| 61 |
if( mAngles==null ) |
|
| 62 |
{
|
|
| 63 |
int[] tmp = {3,3,3};
|
|
| 64 |
mAngles = new int[][] { tmp,tmp,tmp,tmp };
|
|
| 65 |
} |
|
| 66 |
|
|
| 67 |
return mAngles; |
|
| 58 | 68 |
} |
| 59 | 69 |
|
| 60 | 70 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| ... | ... | |
| 110 | 120 |
|
| 111 | 121 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 112 | 122 |
// specifically for the tablebase |
| 123 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 124 |
// two solved positions: original and mirrored (left face swapped with right) |
|
| 125 |
|
|
| 126 |
@Override |
|
| 127 |
int[] getSolvedIndices() |
|
| 128 |
{
|
|
| 129 |
return new int[] {0,INDEX_INVERTED};
|
|
| 130 |
} |
|
| 131 |
|
|
| 132 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 133 |
// ditto |
|
| 134 |
|
|
| 135 |
@Override |
|
| 136 |
boolean isSolved(int index) |
|
| 137 |
{
|
|
| 138 |
return index==0 || index==INDEX_INVERTED; |
|
| 139 |
} |
|
| 140 |
|
|
| 141 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 142 |
// we can never really move the top-front edge, because if we do so, we would also rotate the |
|
| 143 |
// rotation axis themselves! (see getIndex() where the cubit quats are normalized so that quat[0] |
|
| 144 |
// - i.e. the front-top edge - is always 0). |
|
| 145 |
// That's why map the moves (0,2,X) to (0,0&1,-X) and (3,0,X) to (3,1&2,-X) |
|
| 146 |
|
|
| 147 |
@Override |
|
| 148 |
int[] newMove(int axis, int layer, int angle) |
|
| 149 |
{
|
|
| 150 |
if( axis==0 && layer==2 ) return new int[] { axis, (1<<0)+(1<<1), angle==1 ? 1:-1};
|
|
| 151 |
if( axis==3 && layer==0 ) return new int[] { axis, (1<<1)+(1<<2), angle==1 ? 1:-1};
|
|
| 152 |
|
|
| 153 |
int maxAngle = mAngles[axis][layer]; |
|
| 154 |
angle = maxAngle-angle; |
|
| 155 |
if( angle> 0.5f*maxAngle ) angle -= maxAngle; |
|
| 156 |
return new int[] { axis, (1<<layer), angle };
|
|
| 157 |
} |
|
| 158 |
|
|
| 113 | 159 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 114 | 160 |
|
| 115 | 161 |
int getSize() |
| ... | ... | |
| 121 | 167 |
|
| 122 | 168 |
int getMinScramble() |
| 123 | 169 |
{
|
| 124 |
return 9; |
|
| 170 |
return 8; |
|
| 171 |
} |
|
| 172 |
|
|
| 173 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 174 |
|
|
| 175 |
int[] getMidPruningLevels() |
|
| 176 |
{
|
|
| 177 |
return new int[] {3,4};
|
|
| 178 |
} |
|
| 179 |
|
|
| 180 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 181 |
|
|
| 182 |
int[] getHighPruningLevels() |
|
| 183 |
{
|
|
| 184 |
return new int[] {10};
|
|
| 185 |
} |
|
| 186 |
|
|
| 187 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 188 |
|
|
| 189 |
int getGodsNumber() |
|
| 190 |
{
|
|
| 191 |
return 10; |
|
| 192 |
} |
|
| 193 |
|
|
| 194 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 195 |
|
|
| 196 |
boolean moveCanProceed(int lastA, int lastR, int currA, int currR) |
|
| 197 |
{
|
|
| 198 |
return (lastA!=currA) || (lastR!=currR); |
|
| 125 | 199 |
} |
| 126 | 200 |
|
| 127 | 201 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| ... | ... | |
| 157 | 231 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 158 | 232 |
// in-place! |
| 159 | 233 |
|
| 160 |
private int[] getQuatsFromPerm(int[] perm)
|
|
| 234 |
public static int[] getQuatsFromPerm(int[] perm)
|
|
| 161 | 235 |
{
|
| 162 | 236 |
for(int i=0; i<12; i++) |
| 163 | 237 |
{
|
| src/main/java/org/distorted/objectlib/tablebases/TablebasesAbstract.java | ||
|---|---|---|
| 303 | 303 |
public void createTablebase(int maxLevel) |
| 304 | 304 |
{
|
| 305 | 305 |
mTablebase = new Tablebase(mSize); |
| 306 |
mTablebase.insertUnpacked(0,(byte)0); |
|
| 306 |
int[] solved = getSolvedIndices(); |
|
| 307 |
int numSolved = solved.length; |
|
| 308 |
for(int s : solved ) mTablebase.insertUnpacked(s,(byte)0); |
|
| 307 | 309 |
|
| 308 |
int numInserted, totalInserted=1;
|
|
| 310 |
int numInserted, totalInserted=numSolved;
|
|
| 309 | 311 |
byte insertingLevel = 0; |
| 310 | 312 |
|
| 311 | 313 |
android.util.Log.e("D", "creating tablebase of size "+mSize);
|
| ... | ... | |
| 329 | 331 |
android.util.Log.e("D", "total Inserted: "+totalInserted);
|
| 330 | 332 |
} |
| 331 | 333 |
|
| 334 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 335 |
|
|
| 336 |
int[] getSolvedIndices() |
|
| 337 |
{
|
|
| 338 |
return new int[] {0};
|
|
| 339 |
} |
|
| 340 |
|
|
| 341 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 342 |
|
|
| 343 |
boolean isSolved(int index) |
|
| 344 |
{
|
|
| 345 |
return index==0; |
|
| 346 |
} |
|
| 347 |
|
|
| 332 | 348 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 333 | 349 |
|
| 334 | 350 |
public void pack() |
| ... | ... | |
| 359 | 375 |
{
|
| 360 | 376 |
for(int[] move : moves ) |
| 361 | 377 |
{
|
| 362 |
int axis = move[0]; |
|
| 363 |
int layer= move[1]; |
|
| 364 |
int angle= move[2]; |
|
| 365 |
|
|
| 366 |
int maxAngle = mAngles[axis][layer]; |
|
| 367 |
angle = maxAngle-angle; |
|
| 368 |
if( angle> 0.5f*maxAngle ) angle -= maxAngle; |
|
| 378 |
int[] newMove = newMove(move[0],move[1],move[2]); |
|
| 369 | 379 |
|
| 370 |
move[1] = (1<<layer); |
|
| 371 |
move[2] = angle; |
|
| 380 |
move[0] = newMove[0]; |
|
| 381 |
move[1] = newMove[1]; |
|
| 382 |
move[2] = newMove[2]; |
|
| 372 | 383 |
} |
| 373 | 384 |
} |
| 374 | 385 |
|
| 375 | 386 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 376 | 387 |
|
| 377 |
private void addMove(ArrayList<int[]> moves, int axis, int layer, int angle)
|
|
| 388 |
int[] newMove(int axis, int layer, int angle)
|
|
| 378 | 389 |
{
|
| 379 | 390 |
int maxAngle = mAngles[axis][layer]; |
| 380 | 391 |
angle = maxAngle-angle; |
| 381 | 392 |
if( angle> 0.5f*maxAngle ) angle -= maxAngle; |
| 382 | 393 |
|
| 383 |
int[] move = new int[] { axis, (1<<layer), angle };
|
|
| 384 |
moves.add(move); |
|
| 394 |
return new int[] { axis, (1<<layer), angle };
|
|
| 385 | 395 |
} |
| 386 | 396 |
|
| 387 | 397 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| ... | ... | |
| 439 | 449 |
int numQuats = quats.length; |
| 440 | 450 |
int[] tmpQuats = new int[numQuats]; |
| 441 | 451 |
|
| 442 |
while(index!=0)
|
|
| 452 |
while( !isSolved(index) )
|
|
| 443 | 453 |
{
|
| 444 | 454 |
boolean found = false; |
| 445 | 455 |
|
| ... | ... | |
| 477 | 487 |
|
| 478 | 488 |
if( ((newLevel-level+1)%3) == 0 ) |
| 479 | 489 |
{
|
| 480 |
addMove(moves,ax,layer,angle); |
|
| 490 |
int[] tmpMove = newMove(ax,layer,angle); |
|
| 491 |
moves.add(tmpMove); |
|
| 481 | 492 |
index = childIndex; |
| 482 | 493 |
level = (level==0 ? 2 : (byte)(level-1)); |
| 483 | 494 |
found = true; |
| ... | ... | |
| 534 | 545 |
} |
| 535 | 546 |
} |
| 536 | 547 |
|
| 548 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 549 |
// TESTING |
|
| 537 | 550 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 538 | 551 |
|
| 539 | 552 |
public boolean test(int index) |
| ... | ... | |
| 588 | 601 |
|
| 589 | 602 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 590 | 603 |
|
| 591 |
public void testPruning(int level) |
|
| 604 |
public void testPruning(int level) |
|
| 605 |
{
|
|
| 606 |
for( int supp : PruningTable.SUPPORTED ) |
|
| 592 | 607 |
{
|
| 593 |
for( int supp : PruningTable.SUPPORTED ) |
|
| 594 |
{
|
|
| 595 |
PruningTable table = new PruningTable(mTablebase, level, supp); |
|
| 596 |
int size = mTablebase.getSize(); |
|
| 608 |
PruningTable table = new PruningTable(mTablebase, level, supp); |
|
| 609 |
int size = mTablebase.getSize(); |
|
| 597 | 610 |
|
| 598 |
StringBuilder sb = new StringBuilder();
|
|
| 599 |
int num = 0;
|
|
| 611 |
StringBuilder sb = new StringBuilder(); |
|
| 612 |
int num = 0; |
|
| 600 | 613 |
|
| 601 |
for(int i=0; i<size; i++) |
|
| 614 |
for(int i=0; i<size; i++) |
|
| 615 |
{
|
|
| 616 |
if (table.contains(i)) |
|
| 602 | 617 |
{
|
| 603 |
if (table.contains(i)) |
|
| 604 |
{
|
|
| 605 |
if ((num % 10) == 0) sb.append("\n");
|
|
| 606 |
num++; |
|
| 607 |
sb.append(i); |
|
| 608 |
sb.append(' ');
|
|
| 609 |
} |
|
| 618 |
if ((num % 10) == 0) sb.append("\n");
|
|
| 619 |
num++; |
|
| 620 |
sb.append(i); |
|
| 621 |
sb.append(' ');
|
|
| 610 | 622 |
} |
| 611 |
|
|
| 612 |
android.util.Log.e("D", "numbers: " + sb);
|
|
| 613 | 623 |
} |
| 624 |
|
|
| 625 |
android.util.Log.e("D", "numbers: " + sb);
|
|
| 626 |
} |
|
| 627 |
} |
|
| 628 |
|
|
| 629 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 630 |
|
|
| 631 |
private void printQuats(int[] quats) |
|
| 632 |
{
|
|
| 633 |
StringBuilder sb = new StringBuilder(); |
|
| 634 |
for(int q : quats ) |
|
| 635 |
{
|
|
| 636 |
sb.append(' ');
|
|
| 637 |
sb.append(q); |
|
| 614 | 638 |
} |
| 639 |
android.util.Log.e("D", "quats: "+sb);
|
|
| 640 |
} |
|
| 641 |
|
|
| 642 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 643 |
|
|
| 644 |
public void test() |
|
| 645 |
{
|
|
| 646 |
int[] p0 = {0,5,6,10, 2,3,11,9, 1,4,7,8};
|
|
| 647 |
int[] q0 = TBDino6.getQuatsFromPerm(p0); |
|
| 648 |
int index0 = getIndex(q0); |
|
| 649 |
android.util.Log.e("D", "index0: "+index0);
|
|
| 650 |
|
|
| 651 |
int[] p1 = {0,3,11,6, 7,8,10,2, 1,4,9,5};
|
|
| 652 |
int[] q1 = TBDino6.getQuatsFromPerm(p1); |
|
| 653 |
int index1 = getIndex(q1); |
|
| 654 |
android.util.Log.e("D", "index1: "+index1);
|
|
| 655 |
|
|
| 656 |
int[] p2 = {0,3,2,1, 7,6,5,4, 8,11,10,9};
|
|
| 657 |
int[] q2 = TBDino6.getQuatsFromPerm(p2); |
|
| 658 |
int index2 = getIndex(q2); |
|
| 659 |
android.util.Log.e("D", "index2: "+index2);
|
|
| 660 |
} |
|
| 615 | 661 |
|
| 616 | 662 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 617 | 663 |
|
| 618 |
private void printQuats(int[] quats) |
|
| 664 |
private void printPerm(int index) |
|
| 665 |
{
|
|
| 666 |
int[] perm11 = new int[11]; |
|
| 667 |
TablebaseHelpers.getEvenPermutationFromNum(perm11,index); |
|
| 668 |
int[] perm = new int[12]; |
|
| 669 |
for(int i=1; i<12; i++) perm[i] = perm11[i-1]+1; |
|
| 670 |
|
|
| 671 |
StringBuilder sb = new StringBuilder(); |
|
| 672 |
sb.append(index); |
|
| 673 |
sb.append(" : ");
|
|
| 674 |
|
|
| 675 |
for(int i=0; i<12; i++) |
|
| 619 | 676 |
{
|
| 620 |
StringBuilder sb = new StringBuilder(); |
|
| 621 |
for(int q : quats ) |
|
| 622 |
{
|
|
| 623 |
sb.append(' ');
|
|
| 624 |
sb.append(q); |
|
| 625 |
} |
|
| 626 |
android.util.Log.e("D", "quats: "+sb);
|
|
| 677 |
sb.append(' ');
|
|
| 678 |
sb.append(perm[i]); |
|
| 627 | 679 |
} |
| 680 |
android.util.Log.e("D", "PERM: "+sb);
|
|
| 681 |
} |
|
| 628 | 682 |
|
| 629 | 683 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 630 | 684 |
|
| 631 |
public void test() |
|
| 685 |
private void printQuat(int index) |
|
| 686 |
{
|
|
| 687 |
int[] perm11 = new int[11]; |
|
| 688 |
TablebaseHelpers.getEvenPermutationFromNum(perm11,index); |
|
| 689 |
int[] perm = new int[12]; |
|
| 690 |
for(int i=1; i<12; i++) perm[i] = perm11[i-1]+1; |
|
| 691 |
int[] quats = TBDino6.getQuatsFromPerm(perm); |
|
| 692 |
|
|
| 693 |
StringBuilder sb = new StringBuilder(); |
|
| 694 |
sb.append(index); |
|
| 695 |
sb.append(" : ");
|
|
| 696 |
|
|
| 697 |
for(int i=0; i<12; i++) |
|
| 632 | 698 |
{
|
| 633 |
int[] q1 = {1,1,1,0,1,0,0,0, 1,0,1,0,1,0 };
|
|
| 634 |
int index1 = getIndex(q1); |
|
| 635 |
android.util.Log.e("D", "index1: "+index1);
|
|
| 636 |
|
|
| 637 |
int[] q2 = getQuats(index1); |
|
| 638 |
printQuats(q2); |
|
| 639 |
/* |
|
| 640 |
int[] q2 = {0,0,3,0,4,0,0,0, 0,0,0,0,0,0 };
|
|
| 641 |
int index2 = getIndex(q2); |
|
| 642 |
android.util.Log.e("D", "index2: "+index2);
|
|
| 643 |
|
|
| 644 |
*/ |
|
| 699 |
sb.append(' ');
|
|
| 700 |
sb.append(quats[i]); |
|
| 645 | 701 |
} |
| 702 |
android.util.Log.e("D", "QUATS: "+sb);
|
|
| 703 |
} |
|
| 646 | 704 |
} |
| src/main/java/org/distorted/objectlib/tablebases/TablebasesPruning.java | ||
|---|---|---|
| 312 | 312 |
|
| 313 | 313 |
int childIndex = getIndex(tmp); |
| 314 | 314 |
|
| 315 |
if( childIndex==0 )
|
|
| 315 |
if( isSolved(childIndex) )
|
|
| 316 | 316 |
{
|
| 317 | 317 |
solution[0][0] = childIndex; |
| 318 | 318 |
solution[0][1] = 0; |
Also available in: Unified diff
Dino6 solver: pruning version done.