Revision ca2ba7a1
Added by Leszek Koltunski about 1 year ago
| src/main/java/org/distorted/objectlib/tablebases/TablebasesPruning.java | ||
|---|---|---|
| 14 | 14 |
import java.io.ByteArrayOutputStream; |
| 15 | 15 |
import java.io.IOException; |
| 16 | 16 |
import java.io.InputStream; |
| 17 |
import java.util.ArrayList; |
|
| 17 | 18 |
|
| 18 | 19 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 19 | 20 |
|
| ... | ... | |
| 23 | 24 |
|
| 24 | 25 |
private PruningTable[] mHighTables; |
| 25 | 26 |
private PruningTable[] mMidTables; |
| 26 |
private int mLowestHigh, mHighestMid, mLowestMid; |
|
| 27 |
private int mLowestHigh, mHighestMid, mLowestMid, mMaxDistance;
|
|
| 27 | 28 |
|
| 28 | 29 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 29 | 30 |
|
| ... | ... | |
| 160 | 161 |
if( i==0 || level<mLowestMid ) mLowestMid =level; |
| 161 | 162 |
if( i==0 || level>mHighestMid ) mHighestMid=level; |
| 162 | 163 |
} |
| 164 |
|
|
| 165 |
int maxHigh = (mLowestHigh-mHighestMid)/2; |
|
| 166 |
int maxMid = mLowestMid/2; |
|
| 167 |
|
|
| 168 |
mMaxDistance = Math.max(maxHigh,maxMid); |
|
| 163 | 169 |
} |
| 164 | 170 |
|
| 165 | 171 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| ... | ... | |
| 274 | 280 |
|
| 275 | 281 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 276 | 282 |
|
| 277 |
private boolean jumpMidSolvedRecursive(int index, int jump, int depth, int lastA, int lastR, int[][] solution)
|
|
| 283 |
private boolean jumpMidSolvedRecursive(int[] quats, int jump, int depth, int lastA, int lastR, int[][] solution)
|
|
| 278 | 284 |
{
|
| 279 |
int[] quats = getQuats(index); |
|
| 280 | 285 |
int numQuats = quats.length; |
| 281 | 286 |
int[] move = solution[depth]; |
| 282 | 287 |
int[] tmp = new int[mNumCubits]; |
| ... | ... | |
| 328 | 333 |
return true; |
| 329 | 334 |
} |
| 330 | 335 |
|
| 331 |
if( jump>1 && jumpMidSolvedRecursive(childIndex, jump-1, depth+1, ax, layer, solution) )
|
|
| 336 |
if( jump>1 && jumpMidSolvedRecursive(tmp, jump-1, depth+1, ax, layer, solution) )
|
|
| 332 | 337 |
{
|
| 333 | 338 |
return true; |
| 334 | 339 |
} |
| ... | ... | |
| 348 | 353 |
if( midTablesContain(index)>=0 ) return null; |
| 349 | 354 |
|
| 350 | 355 |
int[][] solution = new int[maxJump+1][4]; |
| 356 |
int[] quats = getQuats(index); |
|
| 351 | 357 |
|
| 352 | 358 |
for(int i=1; i<=maxJump; i++) |
| 353 |
if( jumpMidSolvedRecursive(index,i,1,lastA,lastR,solution) )
|
|
| 359 |
if( jumpMidSolvedRecursive(quats,i,1,lastA,lastR,solution) )
|
|
| 354 | 360 |
{
|
| 355 | 361 |
solution[0][2] = i; |
| 356 | 362 |
return solution; |
| ... | ... | |
| 361 | 367 |
|
| 362 | 368 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 363 | 369 |
|
| 364 |
private boolean jumpToSolvedRecursive(int index, int jump, int depth, int lastA, int lastR, int[][] solution)
|
|
| 370 |
private boolean jumpToSolvedRecursive(int[] quats, int jump, int depth, int lastA, int lastR, int[][] solution)
|
|
| 365 | 371 |
{
|
| 366 |
int[] quats = getQuats(index); |
|
| 367 | 372 |
int numQuats = quats.length; |
| 368 | 373 |
int[] move = solution[depth]; |
| 369 | 374 |
int[] tmp = new int[mNumCubits]; |
| ... | ... | |
| 399 | 404 |
|
| 400 | 405 |
int childIndex = getIndex(tmp); |
| 401 | 406 |
if( isSolved(childIndex) ) return true; |
| 402 |
if( jump>1 && jumpToSolvedRecursive(childIndex, jump-1, depth+1, ax, layer, solution) ) return true;
|
|
| 407 |
if( jump>1 && jumpToSolvedRecursive(tmp, jump-1, depth+1, ax, layer, solution) ) return true;
|
|
| 403 | 408 |
} |
| 404 | 409 |
|
| 405 | 410 |
getNextAxisLayerAngleQuat(move); |
| ... | ... | |
| 414 | 419 |
private int[][] jumpToSolved(int index, int maxJump, int lastA, int lastR) |
| 415 | 420 |
{
|
| 416 | 421 |
int[][] solution = new int[maxJump+1][4]; |
| 422 |
int[] quats = getQuats(index); |
|
| 417 | 423 |
|
| 418 | 424 |
for(int i=1; i<=maxJump; i++) |
| 419 |
if( jumpToSolvedRecursive(index,i,1,lastA,lastR,solution) )
|
|
| 425 |
if( jumpToSolvedRecursive(quats,i,1,lastA,lastR,solution) )
|
|
| 420 | 426 |
{
|
| 421 | 427 |
solution[0][0] = i; |
| 422 | 428 |
return solution; |
| ... | ... | |
| 510 | 516 |
} |
| 511 | 517 |
return concatenateMoves(highMoves,jump1Moves,midMoves,jump2Moves); |
| 512 | 518 |
} |
| 519 |
/* |
|
| 520 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 521 |
|
|
| 522 |
private int getDistanceSingle(int[] quats) |
|
| 523 |
{
|
|
| 524 |
int index = getIndex(quats); |
|
| 525 |
|
|
| 526 |
if( isSolved(index) ) return 0; |
|
| 527 |
|
|
| 528 |
int numMid = mMidTables.length; |
|
| 529 |
for(int i=0; i<numMid; i++) |
|
| 530 |
if( mMidTables[i].contains(index) ) return mLowestMid+i; |
|
| 531 |
|
|
| 532 |
if( mHighTables!=null ) |
|
| 533 |
{
|
|
| 534 |
int numHigh = mHighTables.length; |
|
| 535 |
for(int i=0; i<numHigh; i++) |
|
| 536 |
if( mHighTables[i].contains(index) ) |
|
| 537 |
{
|
|
| 538 |
//android.util.Log.e("D", "high tables contain "+index);
|
|
| 539 |
return mLowestHigh+i; |
|
| 540 |
} |
|
| 541 |
|
|
| 542 |
//android.util.Log.e("D", "high tables do not contain "+index);
|
|
| 543 |
} |
|
| 544 |
|
|
| 545 |
return -1; |
|
| 546 |
} |
|
| 547 |
|
|
| 548 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 549 |
|
|
| 550 |
private int getDistance(int[] quats, int depth) |
|
| 551 |
{
|
|
| 552 |
if( depth==0 ) return getDistanceSingle(quats); |
|
| 553 |
|
|
| 554 |
final int MAX = 1000; |
|
| 555 |
int[] data = new int[4]; |
|
| 556 |
int numQuats = quats.length; |
|
| 557 |
int[] tmpQuats = new int[numQuats]; |
|
| 558 |
int[][] rotRow = new int[mNumCubits][mNumAxis]; |
|
| 559 |
int ret = MAX; |
|
| 560 |
|
|
| 561 |
data[0]=0; |
|
| 562 |
data[1]=0; |
|
| 563 |
data[2]=1; |
|
| 564 |
data[3]=1; |
|
| 565 |
|
|
| 566 |
for(int ax=0; ax<mNumAxis; ax++) |
|
| 567 |
for(int cubit=0; cubit<mNumCubits; cubit++) |
|
| 568 |
rotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax); |
|
| 569 |
|
|
| 570 |
for(int s=0; s<mScalingFactor; s++) |
|
| 571 |
{
|
|
| 572 |
int ax = data[0]; |
|
| 573 |
int layer = data[1]; |
|
| 574 |
int quat = data[3]; |
|
| 575 |
|
|
| 576 |
if( mRotatable[ax][layer] ) |
|
| 577 |
{
|
|
| 578 |
int bitLayer = (1<<layer); |
|
| 579 |
System.arraycopy(quats, 0, tmpQuats, 0, numQuats); |
|
| 580 |
|
|
| 581 |
for(int cubit=0; cubit<mNumCubits; cubit++) |
|
| 582 |
if( rotRow[cubit][ax]==bitLayer ) |
|
| 583 |
{
|
|
| 584 |
int currQuat = tmpQuats[cubit]; |
|
| 585 |
int newQuat = getMultQuat(quat,currQuat); |
|
| 586 |
tmpQuats[cubit] = newQuat; |
|
| 587 |
} |
|
| 588 |
|
|
| 589 |
//android.util.Log.e("D", "getDistance: trying ax="+ax+" layer="+layer+" angle="+data[2]+" quat="+quat);
|
|
| 590 |
//TablebaseHelpers.displayTable(tmpQuats, "tmpQuats"); |
|
| 591 |
|
|
| 592 |
int dist = getDistance(tmpQuats,depth-1); |
|
| 593 |
|
|
| 594 |
//android.util.Log.e("D", "dist="+dist);
|
|
| 595 |
|
|
| 596 |
if( dist>=0 && dist<ret ) ret=dist; |
|
| 597 |
} |
|
| 598 |
|
|
| 599 |
getNextAxisLayerAngleQuat(data); |
|
| 600 |
} |
|
| 601 |
|
|
| 602 |
return ret<MAX ? ret : -1; |
|
| 603 |
} |
|
| 604 |
|
|
| 605 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 606 |
|
|
| 607 |
private int getDepth(int[] quats, OperatingSystemInterface osi) |
|
| 608 |
{
|
|
| 609 |
for(int d=0; d<=mMaxDistance; d++) |
|
| 610 |
{
|
|
| 611 |
//TablebaseHelpers.displayTable(quats, "quats, d="+d); |
|
| 612 |
|
|
| 613 |
int res = getDistance(quats,d); |
|
| 614 |
|
|
| 615 |
//osi.reportError("getDistance res="+res+" d="+d);
|
|
| 616 |
|
|
| 617 |
if( res>=0 ) |
|
| 618 |
{
|
|
| 619 |
if( res==0 ) return d; |
|
| 620 |
if( res==mLowestMid ) return mLowestMid-d; |
|
| 621 |
if( res>mLowestMid && res<mHighestMid ) |
|
| 622 |
{
|
|
| 623 |
if( d>0 ) |
|
| 624 |
{
|
|
| 625 |
osi.reportError("1 IMPOSSIBLE!!");
|
|
| 626 |
return -1; |
|
| 627 |
} |
|
| 628 |
else return res; |
|
| 629 |
} |
|
| 630 |
if( res==mHighestMid ) return mHighestMid+d; |
|
| 631 |
if( res==mLowestHigh ) return mLowestHigh-d; |
|
| 632 |
if( res >mLowestHigh ) |
|
| 633 |
{
|
|
| 634 |
if( d>0 ) |
|
| 635 |
{
|
|
| 636 |
osi.reportError("2 IMPOSSIBLE!!");
|
|
| 637 |
return -1; |
|
| 638 |
} |
|
| 639 |
else return res; |
|
| 640 |
} |
|
| 641 |
} |
|
| 642 |
} |
|
| 643 |
|
|
| 644 |
int index=getIndex(quats); |
|
| 645 |
osi.reportError("3 IMPOSSIBLE "+index);
|
|
| 646 |
return -1; |
|
| 647 |
} |
|
| 648 |
|
|
| 649 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 650 |
|
|
| 651 |
public int[][] solutionNew(int index, int[] extra, OperatingSystemInterface osi) |
|
| 652 |
{
|
|
| 653 |
int[] data = new int[4]; |
|
| 654 |
ArrayList<int[]> moves = new ArrayList<>(); |
|
| 655 |
int[] quats = getQuats(index); |
|
| 656 |
int depth = getDepth(quats,osi); |
|
| 657 |
int numQuats = quats.length; |
|
| 658 |
int[] tmpQuats = new int[numQuats]; |
|
| 659 |
|
|
| 660 |
while( depth>0 ) |
|
| 661 |
{
|
|
| 662 |
boolean found = false; |
|
| 663 |
|
|
| 664 |
data[0]=0; |
|
| 665 |
data[1]=0; |
|
| 666 |
data[2]=1; |
|
| 667 |
data[3]=1; |
|
| 668 |
|
|
| 669 |
for(int ax=0; ax<mNumAxis; ax++) |
|
| 670 |
for(int cubit=0; cubit<mNumCubits; cubit++) |
|
| 671 |
mRotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax); |
|
| 672 |
|
|
| 673 |
for(int s=0; s<mScalingFactor && !found; s++) |
|
| 674 |
{
|
|
| 675 |
int ax = data[0]; |
|
| 676 |
int layer = data[1]; |
|
| 677 |
int angle = data[2]; |
|
| 678 |
int quat = data[3]; |
|
| 679 |
|
|
| 680 |
if( mRotatable[ax][layer] ) |
|
| 681 |
{
|
|
| 682 |
int bitLayer = (1<<layer); |
|
| 683 |
System.arraycopy(quats, 0, tmpQuats, 0, numQuats); |
|
| 684 |
|
|
| 685 |
for(int cubit=0; cubit<mNumCubits; cubit++) |
|
| 686 |
if( mRotRow[cubit][ax]==bitLayer ) |
|
| 687 |
{
|
|
| 688 |
int currQuat = tmpQuats[cubit]; |
|
| 689 |
int newQuat = getMultQuat(quat,currQuat); |
|
| 690 |
tmpQuats[cubit] = newQuat; |
|
| 691 |
} |
|
| 692 |
|
|
| 693 |
int newDepth = getDepth(tmpQuats,osi); |
|
| 694 |
|
|
| 695 |
if( newDepth==depth-1 ) |
|
| 696 |
{
|
|
| 697 |
int[] tmpMove = newMove(ax,layer,angle); |
|
| 698 |
moves.add(tmpMove); |
|
| 699 |
quats = new int[numQuats]; |
|
| 700 |
System.arraycopy(tmpQuats, 0, quats, 0, numQuats); |
|
| 701 |
depth = newDepth; |
|
| 702 |
found = true; |
|
| 703 |
} |
|
| 704 |
} |
|
| 705 |
|
|
| 706 |
getNextAxisLayerAngleQuat(data); |
|
| 707 |
} |
|
| 708 |
} |
|
| 709 |
|
|
| 710 |
int[][] ret = convertMovesFromArray(moves); |
|
| 711 |
|
|
| 712 |
return extraInfo(ret,extra); |
|
| 713 |
} |
|
| 714 |
|
|
| 715 |
*/ |
|
| 513 | 716 |
} |
Also available in: Unified diff
CU_323 solver: progress and slight speedup for the 'old' solver.