Revision 3feba94e
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; |
|
| 18 | 17 |
|
| 19 | 18 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 20 | 19 |
|
| ... | ... | |
| 24 | 23 |
|
| 25 | 24 |
private PruningTable[] mHighTables; |
| 26 | 25 |
private PruningTable[] mMidTables; |
| 27 |
private int mLowestHigh, mHighestMid, mLowestMid, mMaxDistance;
|
|
| 26 |
private int mLowestHigh, mHighestMid, mLowestMid; |
|
| 28 | 27 |
|
| 29 | 28 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 30 | 29 |
|
| ... | ... | |
| 161 | 160 |
if( i==0 || level<mLowestMid ) mLowestMid =level; |
| 162 | 161 |
if( i==0 || level>mHighestMid ) mHighestMid=level; |
| 163 | 162 |
} |
| 164 |
|
|
| 165 |
int maxHigh = (mLowestHigh-mHighestMid)/2; |
|
| 166 |
int maxMid = mLowestMid/2; |
|
| 167 |
|
|
| 168 |
mMaxDistance = Math.max(maxHigh,maxMid); |
|
| 169 | 163 |
} |
| 170 | 164 |
|
| 171 | 165 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| ... | ... | |
| 192 | 186 |
|
| 193 | 187 |
if( mRotatable[ax][layer] && moveCanProceed(lastA,lastR,move[0],move[1]) ) |
| 194 | 188 |
{
|
| 195 |
int bitLayer = (1<<layer);
|
|
| 189 |
int bitLayer = computeBitLayer(ax,layer);
|
|
| 196 | 190 |
System.arraycopy(quats, 0, tmpQuats, 0, numQuats); |
| 197 | 191 |
|
| 198 | 192 |
for(int cubit=0; cubit<mNumCubits; cubit++) |
| 199 |
if( mRotRow[cubit][ax]==bitLayer )
|
|
| 193 |
if( (mRotRow[cubit][ax] & bitLayer) != 0 )
|
|
| 200 | 194 |
{
|
| 201 | 195 |
int currQuat = tmpQuats[cubit]; |
| 202 | 196 |
int newQuat = getMultQuat(quat,currQuat); |
| ... | ... | |
| 304 | 298 |
|
| 305 | 299 |
if( mRotatable[ax][layer] && moveCanProceed(lastA,lastR,ax,layer) ) |
| 306 | 300 |
{
|
| 307 |
int bitLayer = (1<<layer);
|
|
| 301 |
int bitLayer = computeBitLayer(ax,layer);
|
|
| 308 | 302 |
System.arraycopy(quats, 0, tmp, 0, numQuats); |
| 309 | 303 |
|
| 310 | 304 |
for(int cubit=0; cubit<mNumCubits; cubit++) |
| 311 |
if( rotRow[cubit][ax]==bitLayer )
|
|
| 305 |
if( (rotRow[cubit][ax] & bitLayer) != 0 )
|
|
| 312 | 306 |
{
|
| 313 | 307 |
int currQuat = tmp[cubit]; |
| 314 | 308 |
int newQuat = getMultQuat(quat,currQuat); |
| ... | ... | |
| 391 | 385 |
|
| 392 | 386 |
if( mRotatable[ax][layer] && moveCanProceed(lastA,lastR,move[0],move[1]) ) |
| 393 | 387 |
{
|
| 394 |
int bitLayer = (1<<layer);
|
|
| 388 |
int bitLayer = computeBitLayer(ax,layer);
|
|
| 395 | 389 |
System.arraycopy(quats, 0, tmp, 0, numQuats); |
| 396 | 390 |
|
| 397 | 391 |
for(int cubit=0; cubit<mNumCubits; cubit++) |
| 398 |
if( rotRow[cubit][ax]==bitLayer )
|
|
| 392 |
if( (rotRow[cubit][ax] & bitLayer) != 0 )
|
|
| 399 | 393 |
{
|
| 400 | 394 |
int currQuat = tmp[cubit]; |
| 401 | 395 |
int newQuat = getMultQuat(quat,currQuat); |
| ... | ... | |
| 516 | 510 |
} |
| 517 | 511 |
return concatenateMoves(highMoves,jump1Moves,midMoves,jump2Moves); |
| 518 | 512 |
} |
| 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 |
*/ |
|
| 716 | 513 |
} |
Also available in: Unified diff
CU_323 solver: return to the old way of moving layers with a twist (we do not move the front layer, we move the middle and back layers to imitate this move and keep edge1 always in place)