# Algorithm Practice

Status
Not open for further replies.

#### Pinzu

Level 15
Im doing some practice assignments for school but I'm not sure how to handle the amount of different states in this one, my program runs out of memory (in neatbeans) before it reaches a solution for cases where n >= 7. I'm using breadth first in my search.

Fig 1: Starting state.
Fig 2: Target state.
Fig 3: Different moves: You can either jump over one or move left and right.

Im thinking my option is to not move pieces that are already in the right place (migrated left to right, but im i'd have to think about how to implement that.

Here is my code:
JASS:
``````package f6;

import java.util.Queue;

public class BlackWhiteBricks {

private enum Color {
BLACK, WHITE, EMPTY;
}

private static boolean isSolved(State target, State current) {
System.out.println(current.toString());
for (int i = 0; i < target.color.length; i++) {
if (target.color[i] != current.color[i]) {
return false;
}
}
return true;
}

private static class State {
Color[] color;
String steps;
int empty;
int count;

private State(int n) {
empty = n/2;
color = new Color[n];
steps = "";
count = 0;
}

private State(Color[] color, String steps, int empty, int count) {
this.count = count;
this.empty = empty;
this.steps = steps;
this.color = new  Color[color.length];
for (int i = 0; i < color.length; i++) {
switch (color[i]) {
case BLACK: this.color[i] = Color.BLACK; break;
case WHITE: this.color[i] = Color.WHITE; break;
default:    this.color[i] = Color.EMPTY; break;
}
}
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder("");
for (Color c : color) {
switch(c) {
case BLACK: sb.append("[B]"); break;
case WHITE: sb.append("[W]"); break;
default: sb.append("[0]"); break;
}
}
sb. append(" | ").append(steps);
return sb.toString();
}

private boolean canJumpLeft() {
return empty < color.length - 2;
}

private void jumpLeft() {
color[empty] = color[empty + 2];
color[empty + 2] = Color.EMPTY;
steps += "[" + (empty + 2) + ">>" + empty + "]";
empty += 2;
count++;
}

boolean canJumpRight() {
return empty > 1;

}

private void jumpRight() {
color[empty] = color[empty - 2];
color[empty - 2] = Color.EMPTY;
steps += "[" + (empty - 2) + ">>" + empty + "]";
empty -= 2;
count++;
}

private boolean canMoveLeft() {
return empty > 0;
}

private void moveLeft() {
color[empty] = color[empty - 1];
color[empty - 1] = Color.EMPTY;
steps += "[" + (empty - 1) + ">>" + empty + "]";
empty -= 1;
count++;
}

private boolean canMoveRight() {
return empty < color.length - 1;
}

private void moveRight() {
color[empty] = color[empty + 1];
color[empty + 1] = Color.EMPTY;
steps += "[" + (empty + 1) + ">>" + empty + "]";
empty += 1;
count++;
}
}

static int counter = 0;

private static void solve(State start, State target) {
State current = start;
while (!isSolved(target, current)) {
if (current.canMoveLeft()) {
State s = new State(current.color, current.steps, current.empty, current.count);
s.moveLeft();
queue.offer(s);
}
if (current.canMoveRight()) {
State s = new State(current.color, current.steps, current.empty, current.count);
s.moveRight();
queue.offer(s);
}
if (current.canJumpLeft()) {
State s = new State(current.color, current.steps, current.empty, current.count);
s.jumpLeft();
queue.offer(s);
}
if (current.canJumpRight()) {
State s = new State(current.color, current.steps, current.empty, current.count);
s.jumpRight();
queue.offer(s);
}
current = queue.poll();
counter++;
//System.out.println("counter: " + counter);
}
System.out.println("SOLVED: " + current.toString());
}

public static void solve(int n) {
if (n < 3 || n%2 == 0)
throw new IllegalArgumentException("" + n);

State start = new State(n);
State target = new State(n);

for (int i = 0; i < n; i++) {
if (i < n/2) {
start.color[i] = Color.BLACK;
target.color[i] = Color.WHITE;
}
else if (i > n/2) {
start.color[i] = Color.WHITE;
target.color[i] = Color.BLACK;
}
else {
start.color[i] = Color.EMPTY;
target.color[i] = Color.EMPTY;
}
}
solve(start, target);

}

}``````

#### Attachments

• Untitled.jpg
24.3 KB · Views: 89
Last edited:

#### Pinzu

Level 15
Solved the issue by getting rid of the creartion of new array objects each cycle and only allowing a brick to move forward.

Status
Not open for further replies.

Replies
0
Views
5K
Replies
2
Views
3K
Replies
0
Views
877
Replies
3
Views
765
Replies
15
Views
2K