Revision f9980f6a
Added by Leszek Koltunski over 1 year ago
| src/main/java/org/distorted/objectlib/tablebases/TablebaseHelpers.java | ||
|---|---|---|
| 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 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 13 |
|
|
| 14 |
public class TablebaseHelpers |
|
| 15 |
{
|
|
| 16 |
private static int swaps(int val, int[] buffer, int len) |
|
| 17 |
{
|
|
| 18 |
int ret = 0; |
|
| 19 |
|
|
| 20 |
for(int i=0; i<len; i++) |
|
| 21 |
{
|
|
| 22 |
if( buffer[i] >val ) ret++; |
|
| 23 |
else if( buffer[i]==val ) return ret; |
|
| 24 |
} |
|
| 25 |
|
|
| 26 |
return -1; |
|
| 27 |
} |
|
| 28 |
|
|
| 29 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 30 |
|
|
| 31 |
public static boolean permutationIsEven(int[] buffer) |
|
| 32 |
{
|
|
| 33 |
int len = buffer.length; |
|
| 34 |
int numOfSwaps = 0; |
|
| 35 |
for(int i=0; i<len; i++) numOfSwaps += swaps(i,buffer,len); |
|
| 36 |
return (numOfSwaps%2==0); |
|
| 37 |
} |
|
| 38 |
|
|
| 39 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 40 |
|
|
| 41 |
public static int computeEvenPermutationNum(int[] permutation) |
|
| 42 |
{
|
|
| 43 |
int len = permutation.length-2; |
|
| 44 |
int ret = 0; |
|
| 45 |
int mul = 4; |
|
| 46 |
|
|
| 47 |
for(int i=0; i<len; i++) |
|
| 48 |
{
|
|
| 49 |
int n = swaps(len-1-i,permutation,len+2); |
|
| 50 |
|
|
| 51 |
ret += n; |
|
| 52 |
|
|
| 53 |
if( i<len-1 ) |
|
| 54 |
{
|
|
| 55 |
ret *= mul; |
|
| 56 |
mul++; |
|
| 57 |
} |
|
| 58 |
} |
|
| 59 |
|
|
| 60 |
return ret; |
|
| 61 |
} |
|
| 62 |
|
|
| 63 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 64 |
|
|
| 65 |
public static void getEvenPermutationFromNum(int[] buffer,int permSize, int permNum) |
|
| 66 |
{
|
|
| 67 |
int index = permSize; |
|
| 68 |
int len = permSize-2; |
|
| 69 |
int totalSwaps = 0; |
|
| 70 |
|
|
| 71 |
for(int i=0; i<permSize; i++) buffer[i]=-1; |
|
| 72 |
|
|
| 73 |
for(int i=0; i<len; i++) |
|
| 74 |
{
|
|
| 75 |
int swaps = (permNum%index); |
|
| 76 |
permNum /= index; |
|
| 77 |
index--; |
|
| 78 |
totalSwaps += swaps; |
|
| 79 |
|
|
| 80 |
for(int j=0; j<permSize; j++) |
|
| 81 |
{
|
|
| 82 |
if( buffer[j]==-1 ) |
|
| 83 |
{
|
|
| 84 |
if( swaps==0 ) |
|
| 85 |
{
|
|
| 86 |
buffer[j] = i; |
|
| 87 |
break; |
|
| 88 |
} |
|
| 89 |
swaps--; |
|
| 90 |
} |
|
| 91 |
} |
|
| 92 |
} |
|
| 93 |
|
|
| 94 |
int lower, upper; |
|
| 95 |
|
|
| 96 |
if( (totalSwaps%2)==0 ) |
|
| 97 |
{
|
|
| 98 |
lower = permSize-2; |
|
| 99 |
upper = permSize-1; |
|
| 100 |
} |
|
| 101 |
else |
|
| 102 |
{
|
|
| 103 |
lower = permSize-1; |
|
| 104 |
upper = permSize-2; |
|
| 105 |
} |
|
| 106 |
|
|
| 107 |
boolean first=true; |
|
| 108 |
|
|
| 109 |
for(int i=0; i<permSize; i++) |
|
| 110 |
if( buffer[i]==-1 ) |
|
| 111 |
{
|
|
| 112 |
if( first ) |
|
| 113 |
{
|
|
| 114 |
buffer[i] = lower; |
|
| 115 |
first=false; |
|
| 116 |
} |
|
| 117 |
else |
|
| 118 |
{
|
|
| 119 |
buffer[i] = upper; |
|
| 120 |
break; |
|
| 121 |
} |
|
| 122 |
} |
|
| 123 |
|
|
| 124 |
} |
|
| 125 |
} |
|
| src/main/java/org/distorted/objectlib/tablebases/TablebasesAbstract.java | ||
|---|---|---|
| 98 | 98 |
{
|
| 99 | 99 |
this(); |
| 100 | 100 |
|
| 101 |
mInitialized = true; |
|
| 101 | 102 |
InputStream stream = res.openRawResource(resource); |
| 102 | 103 |
ByteArrayOutputStream buffer = new ByteArrayOutputStream(); |
| 103 | 104 |
|
| ... | ... | |
| 275 | 276 |
mTablebase = new Tablebase(mSize); |
| 276 | 277 |
mTablebase.insertUnpacked(0,(byte)0); |
| 277 | 278 |
|
| 278 |
int numInserted; |
|
| 279 |
int numInserted, totalInserted=1;
|
|
| 279 | 280 |
byte insertingLevel = 0; |
| 280 | 281 |
|
| 281 | 282 |
android.util.Log.e("D", "creating tablebase of size "+mSize);
|
| ... | ... | |
| 291 | 292 |
} |
| 292 | 293 |
|
| 293 | 294 |
insertingLevel++; |
| 294 |
|
|
| 295 |
totalInserted += numInserted; |
|
| 295 | 296 |
android.util.Log.e("D", "inserted "+numInserted+" positions at level "+insertingLevel);
|
| 296 | 297 |
} |
| 297 | 298 |
while( numInserted>0 ); |
| 298 | 299 |
|
| 300 |
android.util.Log.e("D", "total Inserted: "+totalInserted);
|
|
| 299 | 301 |
android.util.Log.e("D", "packing...");
|
| 300 | 302 |
mTablebase.pack(); |
| 301 | 303 |
android.util.Log.e("D", "all done");
|
| ... | ... | |
| 430 | 432 |
|
| 431 | 433 |
if( !found ) |
| 432 | 434 |
{
|
| 433 |
// error, no move found which would move us closer to a solution
|
|
| 435 |
android.util.Log.e("D", "solution error: no move found!");
|
|
| 434 | 436 |
return null; |
| 435 | 437 |
} |
| 436 | 438 |
} |
| ... | ... | |
| 503 | 505 |
|
| 504 | 506 |
if( !found ) |
| 505 | 507 |
{
|
| 506 |
// error, no move found which would move us closer to a solution
|
|
| 508 |
android.util.Log.e("D", "scramble error: no move found!");
|
|
| 507 | 509 |
return null; |
| 508 | 510 |
} |
| 509 | 511 |
} |
| src/main/java/org/distorted/objectlib/tablebases/TablebasesIvyCube.java | ||
|---|---|---|
| 18 | 18 |
|
| 19 | 19 |
public class TablebasesIvyCube extends TablebasesAbstract |
| 20 | 20 |
{
|
| 21 |
private static final int[] mTmp = new int[6]; |
|
| 22 |
|
|
| 23 |
private static final int[][] MAP = { {0,4,2,2,5,3,4,5,3,0,1,1},
|
|
| 24 |
{1,5,3,3,4,2,5,4,2,1,0,0},
|
|
| 25 |
{2,0,4,5,0,5,1,1,4,3,3,2},
|
|
| 26 |
{3,1,5,4,1,4,0,0,5,2,2,3},
|
|
| 27 |
{4,2,0,1,3,0,3,2,1,5,4,5},
|
|
| 28 |
{5,3,1,0,2,1,2,3,0,4,5,4} };
|
|
| 29 |
|
|
| 21 | 30 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 22 | 31 |
|
| 23 | 32 |
public TablebasesIvyCube() |
| ... | ... | |
| 29 | 38 |
|
| 30 | 39 |
public TablebasesIvyCube(Resources res) |
| 31 | 40 |
{
|
| 32 |
super(res,org.distorted.objectlib.R.raw.pduo_2_tablebase);
|
|
| 41 |
super(res,org.distorted.objectlib.R.raw.ivy_2_tablebase);
|
|
| 33 | 42 |
} |
| 34 | 43 |
|
| 35 | 44 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| ... | ... | |
| 60 | 69 |
{-DIST_CORNER, DIST_CORNER,-DIST_CORNER },
|
| 61 | 70 |
{-DIST_CORNER,-DIST_CORNER, DIST_CORNER },
|
| 62 | 71 |
{ DIST_CORNER,-DIST_CORNER,-DIST_CORNER },
|
| 63 |
{ 0, 0, DIST_CENTER },
|
|
| 64 |
{ 0, 0,-DIST_CENTER },
|
|
| 65 |
{ 0, DIST_CENTER, 0 },
|
|
| 66 |
{ 0,-DIST_CENTER, 0 },
|
|
| 67 | 72 |
{ DIST_CENTER, 0, 0 },
|
| 68 | 73 |
{-DIST_CENTER, 0, 0 },
|
| 74 |
{ 0, DIST_CENTER, 0 },
|
|
| 75 |
{ 0,-DIST_CENTER, 0 },
|
|
| 76 |
{ 0, 0, DIST_CENTER },
|
|
| 77 |
{ 0, 0,-DIST_CENTER },
|
|
| 69 | 78 |
}; |
| 70 | 79 |
} |
| 71 | 80 |
|
| ... | ... | |
| 81 | 90 |
|
| 82 | 91 |
boolean[][] getRotatable() |
| 83 | 92 |
{
|
| 84 |
boolean[] tmp = new boolean[] {false,true};
|
|
| 85 |
return new boolean[][] { tmp,tmp,tmp,tmp };
|
|
| 93 |
boolean[] tmp1 = new boolean[] {false,true};
|
|
| 94 |
boolean[] tmp2 = new boolean[] {true,false};
|
|
| 95 |
|
|
| 96 |
return new boolean[][] { tmp1,tmp2,tmp2,tmp1 };
|
|
| 86 | 97 |
} |
| 87 | 98 |
|
| 88 | 99 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| ... | ... | |
| 97 | 108 |
|
| 98 | 109 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 99 | 110 |
|
| 100 |
int[] getQuats(int index) |
|
| 111 |
private int findFirst(int[] table, int value) |
|
| 112 |
{
|
|
| 113 |
int len = table.length; |
|
| 114 |
|
|
| 115 |
for(int i=0; i<len; i++) |
|
| 116 |
if( table[i]==value ) return i; |
|
| 117 |
|
|
| 118 |
return -1; |
|
| 119 |
} |
|
| 120 |
|
|
| 121 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 122 |
|
|
| 123 |
public int[] getQuats(int index) |
|
| 101 | 124 |
{
|
| 102 |
return new int[] {0,0,0,0, 0,0,0,0,0,0};
|
|
| 125 |
int perm_num = index%360; |
|
| 126 |
index /= 360; |
|
| 127 |
int twist0 = index%3; |
|
| 128 |
index /= 3; |
|
| 129 |
int twist1 = index%3; |
|
| 130 |
index /= 3; |
|
| 131 |
int twist2 = index%3; |
|
| 132 |
index /= 3; |
|
| 133 |
int twist3 = index%3; |
|
| 134 |
|
|
| 135 |
int[] ret = new int[10]; |
|
| 136 |
|
|
| 137 |
ret[0] = twist0==0 ? 0 : (twist0==1 ? 2:1); |
|
| 138 |
ret[1] = twist1==0 ? 0 : (twist1==1 ? 5:6); |
|
| 139 |
ret[2] = twist2==0 ? 0 : (twist2==1 ? 3:4); |
|
| 140 |
ret[3] = twist3==0 ? 0 : (twist3==1 ? 8:7); |
|
| 141 |
|
|
| 142 |
TablebaseHelpers.getEvenPermutationFromNum(mTmp,6,perm_num); |
|
| 143 |
|
|
| 144 |
for(int i=0; i<6; i++) |
|
| 145 |
{
|
|
| 146 |
int cubitThatMoves = mTmp[i]; |
|
| 147 |
ret[cubitThatMoves+4] = findFirst(MAP[cubitThatMoves],i); |
|
| 148 |
} |
|
| 149 |
|
|
| 150 |
return ret; |
|
| 103 | 151 |
} |
| 104 | 152 |
|
| 105 | 153 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 106 | 154 |
|
| 107 |
int getIndex(int[] quats) |
|
| 155 |
public int getIndex(int[] quats)
|
|
| 108 | 156 |
{
|
| 109 |
return 0; |
|
| 157 |
int twist0 = quats[0]==0 ? 0 : (quats[0]==1 ? 2:1); |
|
| 158 |
int twist1 = quats[1]==0 ? 0 : (quats[1]==6 ? 2:1); |
|
| 159 |
int twist2 = quats[2]==0 ? 0 : (quats[2]==4 ? 2:1); |
|
| 160 |
int twist3 = quats[3]==0 ? 0 : (quats[3]==7 ? 2:1); |
|
| 161 |
|
|
| 162 |
int c4 = MAP[0][quats[4]]; |
|
| 163 |
int c5 = MAP[1][quats[5]]; |
|
| 164 |
int c6 = MAP[2][quats[6]]; |
|
| 165 |
int c7 = MAP[3][quats[7]]; |
|
| 166 |
int c8 = MAP[4][quats[8]]; |
|
| 167 |
int c9 = MAP[5][quats[9]]; |
|
| 168 |
|
|
| 169 |
mTmp[c4]=0; |
|
| 170 |
mTmp[c5]=1; |
|
| 171 |
mTmp[c6]=2; |
|
| 172 |
mTmp[c7]=3; |
|
| 173 |
mTmp[c8]=4; |
|
| 174 |
mTmp[c9]=5; |
|
| 175 |
|
|
| 176 |
int perm_num = TablebaseHelpers.computeEvenPermutationNum(mTmp); |
|
| 177 |
|
|
| 178 |
return perm_num + 360*(twist0+ 3*(twist1+ 3*(twist2+ 3*twist3))); |
|
| 110 | 179 |
} |
| 111 | 180 |
} |
| 112 | 181 |
|
Also available in: Unified diff
Ivy solver finished