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 |
}
|
CU_323 solver: progress and slight speedup for the 'old' solver.