### Prefer interfaces to implementations ###
> public static ArrayList<State> findNeighbours(State currentState) {
Consider
public static List<State> findNeighbours(State currentState) {
This way you can change from `ArrayList` to another implementation at just one place: the initialization.
### Remember what you know ###
> for (int i = 0; i < state.length; i++) {
if (state[i] == 0) {
Note that each state knows where the empty spot is when you create it. So why iterate to find the empty spot? Just store it. Then you can get just say
int i = state.getEmptyIndex();
That saves looping at the cost of a little more memory.
### Pick your data type ###
You use a `byte[]` to store the state. That's easy to access, but it's hard to copy and store. Consider using a `long` instead. Each square takes four bits to hold. Determining the neighbors is a little more complicated, but not terribly so. And best of all, you can say things like
if (!seen.contains(next)) {
neighbours.add(next);
}
Where `seen` can be a `HashSet<State>`.
### Third time refactor ###
There's a rule of thumb. If you're doing something once, just write it out for that purpose. If you do it a second time, copy and paste and then modify to fit. If you do it a third time, refactor so that you're just calling one method three times with different data. This isn't an absolute rule. Sometimes it makes sense to put the code in a method the first or second time. But it almost always makes sense by the third time.
You have the same basic code written four times.
> if (i % 4 != 0) {
byte[] left = new byte[16];
System.arraycopy(state, 0, left, 0, left.length);
byte temp = left[i];
left[i] = left[i - 1];
left[i - 1] = temp;
State s = new State(currentState.getMoves() + 1, left);
neighbours.add(s);
>
}
You can call a method for this.
int column = i % WIDTH;
if (column > 0) {
move(-1, currentState, neighbours);
}
And define `move` as
private void move(int direction, State current, List<State> neighbours) {
State next = current.move(direction);
if (!SET.contains(next)) {
neighbours.add(next);
}
}
And define that `move` as
public State move(int direction) {
int index = getEmptyIndex();
long next = swapBits(composition, index, index + direction, BIT_WIDTH);
return new State(getMoves() + 1, next, index + direction);
}
And we can get `swapBits` from [here](http://www.geeksforgeeks.org/swap-bits-in-a-given-number/):
public long swapBits(long n, int from, int to, int width) {
from *= width;
to *= width;
long xor = ((n >> from) ^ (n >> to)) & ((1U << width) - 1);
return n ^ ((xor << from) | (xor << to));
}
You don't provide enough context for testing, so I haven't tried to run this. There may need to be tweaking.
This looks more complicated but it should actually use less memory.
if (column < WIDTH - 1) {
move(1, currentState, neighbours);
}
if (i >= WIDTH) {
move(-WIDTH, currentState, neighbours);
}
if (i < SIZE - WIDTH) {
move(WIDTH, currentState, neighbours);
}
The remaining three possible moves.
Note that I also saved `i % 4` as `column` so as not to repeat that. I also find that easier to read.
I added constants for `WIDTH`, which would be `4`, `SIZE` as `16`, and `BIT_WIDTH` as `4`. Other possible triplets include `3`, `9`, and `4`.
### Performance ###
The hope was that a more aggressive check of the `seen` tracker would help here. Other than that, this shouldn't make much difference.
> @Override
public boolean contains(Object obj) {
State v = (State) obj;
for (State mad : this) {
if (Arrays.equals(mad.getState(), v.getState())) {
>
return true;
}
}
return false;
}
So every time you call `SET.contains` or `SET.add` (which calls `contains`), you do an `Arrays.equals` on each and every member of the `SET`. You took an \$\mathcal{O}(1)\$ operation and turned it into a \$\mathcal{O}(n)\$. Why? You could have just made this a `List` with the same performance. Instead of overriding `HashSet.contains`, consider what happens if you override `State.hashCode`.
> current = QUEUE.remove();
SET.add(current);
You also call `SET.add` ever time you remove something from the queue. And you remove every valid state from the queue. I.e. \$\mathcal{O}(n)\$ times. So now we're up to \$\mathcal{O}(n^2)\$. You only add to the queue once without adding to the set. So just move the `SET.add` to where you put the initial state in the queue.
> if (!SET.contains(n)) {
SET.add(n);
if (!QUEUE.contains(n)) {
QUEUE.add(n);
}
}
You can trim this down.
if (!SET.contains(n)) {
SET.add(n);
QUEUE.add(n);
}
You don't need to check if it's in the `QUEUE`. You only add things to the `QUEUE` after you put them in the `SET`. So this will never be true and is a linear time operation.
Also, as I said earlier, I'd prefer to do that check earlier.
### Example ###
public static final int WIDTH = 4;
public static final int SIZE = 16;
private static Set<State> SET = new HashSet<>();
private static Queue<State> QUEUE = new LinkedList<>();
public static void main(String[] args) {
long initial = 0x1FFF56FF9AFFDFF0L;
State s = new State(0, initial, 0);
SET.add(s);
QUEUE.add(s);
int numInserted = 0;
while (!QUEUE.isEmpty()) {
numInserted++;
if (numInserted % 1024576 == 0) {
System.out.println(numInserted + " " + QUEUE.peek().getMoves());
}
findNeighbours(QUEUE.remove());
}
System.out.println("Recorded inserted :" + SET.size());
}
public static void findNeighbours(State current) {
int i = current.getEmptyIndex();
int column = i % WIDTH;
if (column > 0) {
move(-1, current);
}
if (column < WIDTH - 1) {
move(1, current);
}
if (i >= WIDTH) {
move(-WIDTH, current);
}
if (i < SIZE - WIDTH) {
move(WIDTH, current);
}
}
private static void move(int direction, State current) {
State next = current.move(direction);
if (!SET.contains(next)) {
SET.add(next);
QUEUE.add(next);
}
}
public static class State {
public static final int BIT_WIDTH = 4;
int moves;
Long composition;
int emptyIndex;
public State(int moves, long composition, int emptyIndex) {
this.moves = moves;
this.composition = composition;
this.emptyIndex = emptyIndex;
}
public int getMoves() {
return moves;
}
public void setMoves(int moves) {
this.moves = moves;
}
public long getState() {
return composition;
}
public int getEmptyIndex() {
return emptyIndex;
}
public State move(int direction) {
int index = getEmptyIndex();
long next = swapBits(composition, index, index + direction, BIT_WIDTH);
return new State(getMoves() + 1, next, index + direction);
}
public long swapBits(long n, int from, int to, int width) {
from *= width;
to *= width;
long xor = ((n >> from) ^ (n >> to)) & ((1 << width) - 1);
return n ^ ((xor << from) | (xor << to));
}
@Override
public int hashCode() {
return composition.hashCode();
}
@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof State)) {
return false;
}
State s = (State)o;
return composition.equals(s.getState());
}
}
I ripped out the database parts, since I don't have access to the database. It was still slow, so I don't think that was the problem.
Because this overrides `hashCode`, we can just use the regular `hashSet`. `Long.hashCode` seems to work well enough.
This version does a million records in less time than the original took to do 20 thousand. And it doesn't take longer with each added element.
I tested it with output for the simple, one and two square states. I just printed out the number found for the states with more squares.
Note that your example has seven squares and 57,657,600 states, not 5 million.
In this example, I used F (15) instead of -1 to represent unknown squares. That of course stops working if 15 is one of your squares.