Revision e342c3f7
Added by Leszek Koltunski almost 2 years ago
| src/main/java/org/distorted/objectlib/helpers/ObjectSignature.java | ||
|---|---|---|
| 25 | 25 |
|
| 26 | 26 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 27 | 27 |
|
| 28 |
public class ObjectSignature |
|
| 28 |
public class ObjectSignature implements Comparable<ObjectSignature>
|
|
| 29 | 29 |
{
|
| 30 | 30 |
private long mSignature1, mSignature2, mSignature3; |
| 31 | 31 |
private int[] mLayer; |
| ... | ... | |
| 163 | 163 |
mSignature3 = sig; |
| 164 | 164 |
} |
| 165 | 165 |
|
| 166 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 167 |
|
|
| 168 |
public int compareTo(ObjectSignature sig) |
|
| 169 |
{
|
|
| 170 |
if( mSignature1>sig.mSignature1 ) return +1; |
|
| 171 |
else if( mSignature1<sig.mSignature1 ) return -1; |
|
| 172 |
else |
|
| 173 |
{
|
|
| 174 |
if( mSignature2>sig.mSignature2 ) return +1; |
|
| 175 |
else if( mSignature2<sig.mSignature2 ) return -1; |
|
| 176 |
else |
|
| 177 |
{
|
|
| 178 |
if( mSignature3>sig.mSignature3 ) return +1; |
|
| 179 |
else if( mSignature3<sig.mSignature3 ) return -1; |
|
| 180 |
else return 0; |
|
| 181 |
} |
|
| 182 |
} |
|
| 183 |
} |
|
| 184 |
|
|
| 166 | 185 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 167 | 186 |
|
| 168 | 187 |
public boolean isEqual(ObjectSignature sig) |
| src/main/java/org/distorted/objectlib/scrambling/BlacklistedSignatures.java | ||
|---|---|---|
| 1 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 2 |
// Copyright 2022 Leszek Koltunski // |
|
| 3 |
// // |
|
| 4 |
// This file is part of Magic Cube. // |
|
| 5 |
// // |
|
| 6 |
// Magic Cube is free software: you can redistribute it and/or modify // |
|
| 7 |
// it under the terms of the GNU General Public License as published by // |
|
| 8 |
// the Free Software Foundation, either version 2 of the License, or // |
|
| 9 |
// (at your option) any later version. // |
|
| 10 |
// // |
|
| 11 |
// Magic Cube is distributed in the hope that it will be useful, // |
|
| 12 |
// but WITHOUT ANY WARRANTY; without even the implied warranty of // |
|
| 13 |
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // |
|
| 14 |
// GNU General Public License for more details. // |
|
| 15 |
// // |
|
| 16 |
// You should have received a copy of the GNU General Public License // |
|
| 17 |
// along with Magic Cube. If not, see <http://www.gnu.org/licenses/>. // |
|
| 18 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 19 |
|
|
| 20 |
package org.distorted.objectlib.scrambling; |
|
| 21 |
|
|
| 22 |
import java.util.TreeSet; |
|
| 23 |
|
|
| 24 |
import org.distorted.objectlib.helpers.ObjectSignature; |
|
| 25 |
|
|
| 26 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 27 |
|
|
| 28 |
public class BlacklistedSignatures |
|
| 29 |
{
|
|
| 30 |
private static BlacklistedSignatures mThis; |
|
| 31 |
private final TreeSet<ObjectSignature> mBlacklisted; |
|
| 32 |
|
|
| 33 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 34 |
|
|
| 35 |
private BlacklistedSignatures() |
|
| 36 |
{
|
|
| 37 |
mBlacklisted = new TreeSet<>(); |
|
| 38 |
} |
|
| 39 |
|
|
| 40 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 41 |
|
|
| 42 |
public static BlacklistedSignatures getInstance() |
|
| 43 |
{
|
|
| 44 |
if( mThis==null ) mThis = new BlacklistedSignatures(); |
|
| 45 |
return mThis; |
|
| 46 |
} |
|
| 47 |
|
|
| 48 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 49 |
|
|
| 50 |
public void clear() |
|
| 51 |
{
|
|
| 52 |
mBlacklisted.clear(); |
|
| 53 |
} |
|
| 54 |
|
|
| 55 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 56 |
|
|
| 57 |
public void add(ObjectSignature signature) |
|
| 58 |
{
|
|
| 59 |
mBlacklisted.add(signature); |
|
| 60 |
} |
|
| 61 |
|
|
| 62 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
| 63 |
|
|
| 64 |
public boolean contains(ObjectSignature signature) |
|
| 65 |
{
|
|
| 66 |
return mBlacklisted.contains(signature); |
|
| 67 |
} |
|
| 68 |
} |
|
| src/main/java/org/distorted/objectlib/scrambling/ObjectScrambler.java | ||
|---|---|---|
| 54 | 54 |
private int[][] mQuatMult; |
| 55 | 55 |
|
| 56 | 56 |
// type=2 , i.e. locally created bandaged cuboids |
| 57 |
private ArrayList<ScrambleStateBandagedCuboid> mBandagedStates; |
|
| 57 |
private ArrayList<ScrambleStateBandagedCuboid> mStatesHistory; |
|
| 58 |
private BlacklistedSignatures mBlacklisted; |
|
| 58 | 59 |
|
| 59 | 60 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 60 | 61 |
|
| ... | ... | |
| 411 | 412 |
|
| 412 | 413 |
private void buildMoveForced(int[][] scramble, Random rnd, int curr) |
| 413 | 414 |
{
|
| 414 |
ScrambleStateBandagedCuboid currState = mBandagedStates.get(curr);
|
|
| 415 |
ScrambleStateBandagedCuboid currState = mStatesHistory.get(curr);
|
|
| 415 | 416 |
int indexExcluded = curr>0 ? scramble[curr-1][0] : ScrambleStateBandagedCuboid.AXIS_NONE; |
| 416 | 417 |
int numMoves = currState.numMoves(indexExcluded); |
| 417 | 418 |
ObjectSignature signature; |
| ... | ... | |
| 437 | 438 |
currState.fillOutScramble(scramble[curr],moveIndex); |
| 438 | 439 |
} |
| 439 | 440 |
|
| 440 |
ScrambleStateBandagedCuboid nextState = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature); |
|
| 441 |
mBandagedStates.add(nextState);
|
|
| 441 |
ScrambleStateBandagedCuboid nextState = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted);
|
|
| 442 |
mStatesHistory.add(nextState);
|
|
| 442 | 443 |
} |
| 443 | 444 |
|
| 444 | 445 |
|
| ... | ... | |
| 447 | 448 |
|
| 448 | 449 |
private boolean buildMove2Cons(int[][] scramble, Random rnd, int curr) |
| 449 | 450 |
{
|
| 450 |
ScrambleStateBandagedCuboid currState = mBandagedStates.get(curr);
|
|
| 451 |
ScrambleStateBandagedCuboid currState = mStatesHistory.get(curr);
|
|
| 451 | 452 |
boolean lock= (curr>=2 && scramble[curr-2][0]==scramble[curr-1][0] ); |
| 452 | 453 |
int axisExcluded = lock ? scramble[curr-1][0] : ScrambleStateBandagedCuboid.AXIS_NONE; |
| 453 | 454 |
int layerExcluded= !lock && curr>=1 ? scramble[curr-1][1] : -1; |
| ... | ... | |
| 457 | 458 |
{
|
| 458 | 459 |
if( curr>0 ) |
| 459 | 460 |
{
|
| 460 |
mBandagedStates.remove(curr);
|
|
| 461 |
ScrambleStateBandagedCuboid prevState = mBandagedStates.get(curr-1);
|
|
| 461 |
mStatesHistory.remove(curr);
|
|
| 462 |
ScrambleStateBandagedCuboid prevState = mStatesHistory.get(curr-1);
|
|
| 462 | 463 |
ObjectSignature signature = currState.getSignature(); |
| 463 | 464 |
prevState.removeMoves(signature); |
| 465 |
mBlacklisted.add(signature); |
|
| 464 | 466 |
boolean result = buildMove2Cons(scramble,rnd,curr-1); |
| 465 | 467 |
if( !result ) return false; |
| 466 |
currState = mBandagedStates.get(curr);
|
|
| 468 |
currState = mStatesHistory.get(curr);
|
|
| 467 | 469 |
lock= (curr>=2 && scramble[curr-2][0]==scramble[curr-1][0] ); |
| 468 | 470 |
axisExcluded = lock ? scramble[curr-1][0] : ScrambleStateBandagedCuboid.AXIS_NONE; |
| 469 | 471 |
layerExcluded= lock ? -1 : scramble[curr-1][1]; |
| ... | ... | |
| 477 | 479 |
ObjectSignature signature = currState.getMove(moveIndex); |
| 478 | 480 |
currState.fillOutScramble(scramble[curr],moveIndex); |
| 479 | 481 |
|
| 480 |
ScrambleStateBandagedCuboid nextState = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature); |
|
| 481 |
mBandagedStates.add(nextState);
|
|
| 482 |
ScrambleStateBandagedCuboid nextState = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted);
|
|
| 483 |
mStatesHistory.add(nextState);
|
|
| 482 | 484 |
|
| 483 | 485 |
return true; |
| 484 | 486 |
} |
| ... | ... | |
| 488 | 490 |
|
| 489 | 491 |
private boolean buildMove1Cons(int[][] scramble, Random rnd, int curr) |
| 490 | 492 |
{
|
| 491 |
ScrambleStateBandagedCuboid currState = mBandagedStates.get(curr);
|
|
| 493 |
ScrambleStateBandagedCuboid currState = mStatesHistory.get(curr);
|
|
| 492 | 494 |
int axisExcluded = curr>=1 ? scramble[curr-1][0] : ScrambleStateBandagedCuboid.AXIS_NONE; |
| 493 | 495 |
int numMoves = currState.numMoves(axisExcluded); |
| 494 | 496 |
|
| ... | ... | |
| 496 | 498 |
{
|
| 497 | 499 |
if( curr>0 ) |
| 498 | 500 |
{
|
| 499 |
mBandagedStates.remove(curr);
|
|
| 500 |
ScrambleStateBandagedCuboid prevState = mBandagedStates.get(curr-1);
|
|
| 501 |
mStatesHistory.remove(curr);
|
|
| 502 |
ScrambleStateBandagedCuboid prevState = mStatesHistory.get(curr-1);
|
|
| 501 | 503 |
ObjectSignature signature = currState.getSignature(); |
| 502 | 504 |
prevState.removeMoves(signature); |
| 505 |
mBlacklisted.add(signature); |
|
| 503 | 506 |
boolean result = buildMove1Cons(scramble,rnd,curr-1); |
| 504 | 507 |
if( !result ) return false; |
| 505 |
currState = mBandagedStates.get(curr);
|
|
| 508 |
currState = mStatesHistory.get(curr);
|
|
| 506 | 509 |
axisExcluded = scramble[curr-1][0]; |
| 507 | 510 |
numMoves = currState.numMoves(axisExcluded); |
| 508 | 511 |
} |
| ... | ... | |
| 517 | 520 |
ObjectSignature signature = currState.getMove(moveIndex); |
| 518 | 521 |
currState.fillOutScramble(scramble[curr],moveIndex); |
| 519 | 522 |
|
| 520 |
ScrambleStateBandagedCuboid nextState = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature); |
|
| 521 |
mBandagedStates.add(nextState);
|
|
| 523 |
ScrambleStateBandagedCuboid nextState = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted);
|
|
| 524 |
mStatesHistory.add(nextState);
|
|
| 522 | 525 |
|
| 523 | 526 |
return true; |
| 524 | 527 |
} |
| ... | ... | |
| 528 | 531 |
|
| 529 | 532 |
private void initializeType2Scrambling(int[][] scramble, Random rnd, int total, ObjectSignature signature) |
| 530 | 533 |
{
|
| 531 |
if( mBandagedStates==null ) mBandagedStates = new ArrayList<>();
|
|
| 532 |
else mBandagedStates.clear();
|
|
| 534 |
if( mStatesHistory==null ) mStatesHistory = new ArrayList<>();
|
|
| 535 |
else mStatesHistory.clear();
|
|
| 533 | 536 |
|
| 534 |
ScrambleStateBandagedCuboid state = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature); |
|
| 535 |
mBandagedStates.add(state); |
|
| 537 |
if( mBlacklisted==null ) mBlacklisted = BlacklistedSignatures.getInstance(); |
|
| 538 |
else mBlacklisted.clear(); |
|
| 539 |
|
|
| 540 |
ScrambleStateBandagedCuboid state = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted); |
|
| 541 |
mStatesHistory.add(state); |
|
| 536 | 542 |
boolean success = true; |
| 537 | 543 |
|
| 538 | 544 |
for(int curr=0; curr<total; curr++) |
| ... | ... | |
| 548 | 554 |
if( !success ) |
| 549 | 555 |
{
|
| 550 | 556 |
success = true; |
| 551 |
mBandagedStates.clear(); |
|
| 552 |
state = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature); |
|
| 553 |
mBandagedStates.add(state); |
|
| 557 |
mStatesHistory.clear(); |
|
| 558 |
state = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted); |
|
| 559 |
mStatesHistory.add(state); |
|
| 560 |
mBlacklisted.clear(); |
|
| 554 | 561 |
|
| 555 | 562 |
for(int curr=0; curr<total; curr++) |
| 556 | 563 |
{
|
| ... | ... | |
| 565 | 572 |
|
| 566 | 573 |
if( !success ) |
| 567 | 574 |
{
|
| 568 |
mBandagedStates.clear();
|
|
| 569 |
state = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature); |
|
| 570 |
mBandagedStates.add(state);
|
|
| 575 |
mStatesHistory.clear();
|
|
| 576 |
state = new ScrambleStateBandagedCuboid(mNumLayers[0], mNumLayers[1], mNumLayers[2], signature, mBlacklisted);
|
|
| 577 |
mStatesHistory.add(state);
|
|
| 571 | 578 |
|
| 572 | 579 |
for(int curr=0; curr<total; curr++) |
| 573 | 580 |
{
|
| src/main/java/org/distorted/objectlib/scrambling/ScrambleStateBandagedCuboid.java | ||
|---|---|---|
| 19 | 19 |
|
| 20 | 20 |
package org.distorted.objectlib.scrambling; |
| 21 | 21 |
|
| 22 |
import org.distorted.objectlib.helpers.ObjectSignature; |
|
| 23 |
|
|
| 22 | 24 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 23 | 25 |
// Info about a scramble state of any bandaged cuboid. |
| 24 | 26 |
|
| 25 |
import org.distorted.objectlib.helpers.ObjectSignature; |
|
| 26 |
|
|
| 27 | 27 |
public class ScrambleStateBandagedCuboid |
| 28 | 28 |
{
|
| 29 | 29 |
public static int MAX_SUPPORTED_SIZE = 5; |
| ... | ... | |
| 42 | 42 |
|
| 43 | 43 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 44 | 44 |
|
| 45 |
public ScrambleStateBandagedCuboid(int x, int y, int z, ObjectSignature signature) |
|
| 45 |
public ScrambleStateBandagedCuboid(int x, int y, int z, ObjectSignature signature, BlacklistedSignatures blacklisted)
|
|
| 46 | 46 |
{
|
| 47 | 47 |
mLayer = new int[3]; |
| 48 | 48 |
mTurns = new int[3]; |
| ... | ... | |
| 73 | 73 |
mStartZ = xMoves + yMoves; |
| 74 | 74 |
|
| 75 | 75 |
mSignature = signature; |
| 76 |
mMoves = createMoves(); |
|
| 76 |
mMoves = createMoves(blacklisted);
|
|
| 77 | 77 |
} |
| 78 | 78 |
|
| 79 | 79 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| ... | ... | |
| 280 | 280 |
|
| 281 | 281 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
| 282 | 282 |
|
| 283 |
private ObjectSignature[] createMoves() |
|
| 283 |
private ObjectSignature[] createMoves(BlacklistedSignatures blacklisted)
|
|
| 284 | 284 |
{
|
| 285 | 285 |
ObjectSignature[] ret = new ObjectSignature[mNumMoves]; |
| 286 | 286 |
int index = 0; |
| ... | ... | |
| 296 | 296 |
for(int turn=1; turn<=mTurns[axis]; turn++) |
| 297 | 297 |
{
|
| 298 | 298 |
boolean allLayersLocked = true; |
| 299 |
int begIndex = index; |
|
| 299 | 300 |
|
| 300 | 301 |
for(int layer=0; layer<mLayer[axis]; layer++) |
| 301 | 302 |
{
|
| ... | ... | |
| 313 | 314 |
index++; |
| 314 | 315 |
} |
| 315 | 316 |
|
| 317 |
for(int i=begIndex; i<index; i++) |
|
| 318 |
{
|
|
| 319 |
if( ret[i]!=null && blacklisted.contains(ret[i]) ) ret[i]=null; |
|
| 320 |
} |
|
| 321 |
|
|
| 316 | 322 |
if( allLayersLocked ) ret[index-1] = null; |
| 317 | 323 |
} |
| 318 | 324 |
|
Also available in: Unified diff
Introduce BlacklistedSignatures singleton: during type2 scrambling (locally-produced bandaged cuboids) remember the signatures that we've previously proven to be leading to a dead-end.