I think I've managed to locate the minimum amount of moves to arrange a string (ABCDE in any order) alphabetically.
There are some conditions that must be followed:
b), or:s)However, I'm also trying to print out the moves I've used to get to the shortest path.
For example, if I put in BECAD i would get Minimum step used: 7 but I would also like to print bsssbsb.
Right now my StringBuilder keeps appending all possible moves. Any help would be appreciated.
public static void main(String[] args) {
String s = "BECAD";
int step = 0;
System.out.println("Minimum step used: " + robot(s, step));
}
public static int robot(String s, int step) {
StringBuilder sb1 = new StringBuilder();
Queue<State> leftQ = new LinkedList<>();
Queue<State> rightQ = new LinkedList<>();
State nodeLeft = new State(s, step, 0, sb1);
State nodeRight = new State(s, step, 0, sb1);
//while we havent reached ABCDE continue until one of them reaches
while(!(nodeLeft.s.equals("ABCDE")) && !(nodeRight.s.equals("ABCDE"))) {
// first loop we will always enter the first condition.
if(nodeLeft.previousMove == 0 || nodeRight.previousMove == 0) {
leftQ.offer(new State(nodeLeft.s.substring(1, 2) + nodeLeft.s.substring(0, 1) + nodeLeft.s.substring(2, 5), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 1, nodeLeft.allMoves.append("b")));
rightQ.offer(new State(nodeLeft.s.substring(4, 5) + nodeLeft.s.substring(0, 4), nodeRight.currentSteps + 1, nodeRight.previousMove + 2, nodeRight.allMoves.append("s")));
// there are two queues, left and right. first we swap the 1st element with the 2nd element and push it to the leftQ. The other one be will shift the string one step left and push it to the rightQ.
} else if(nodeLeft.previousMove == 1 || nodeRight.previousMove == 1) {
leftQ.offer(new State(nodeLeft.s.substring(4, 5) + nodeLeft.s.substring(0, 4), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 2, nodeLeft.allMoves.append("s")));
rightQ.offer(new State(nodeRight.s.substring(4, 5) + nodeRight.s.substring(0, 4), nodeRight.currentSteps + 1, nodeRight.previousMove = 2, nodeRight.allMoves.append("s")));
} else if(nodeLeft.previousMove == 2 || nodeRight.previousMove == 2) {
leftQ.offer(new State(nodeLeft.s.substring(1, 2) + nodeLeft.s.substring(0, 1) + nodeLeft.s.substring(2, 5), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 1, nodeLeft.allMoves.append("b")));
leftQ.offer(new State(nodeLeft.s.substring(4, 5) + nodeLeft.s.substring(0, 4), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 2, nodeLeft.allMoves.append("s")));
rightQ.offer(new State(nodeRight.s.substring(1, 2) + nodeRight.s.substring(0, 1) + nodeRight.s.substring(2, 5), nodeRight.currentSteps + 1, nodeRight.previousMove = 1, nodeRight.allMoves.append("b")));
rightQ.offer(new State(nodeRight.s.substring(4, 5) + nodeRight.s.substring(0, 4), nodeRight.currentSteps + 1, nodeRight.previousMove = 2, nodeRight.allMoves.append("s")));
// to avoid endless loop i check the previous move. If i swapped previously i must shift one step left.
}
nodeLeft = leftQ.poll();
nodeRight = rightQ.poll();
// i continue to poll from both the queues to see which one reaches ABCDE first.
// Since i am building something like a binary tree on the width
// eventually one of the nodes will reach first. Then i set the other to a max value since it never finished it search.
}
if(!(nodeLeft.s.equals("ABCDE"))) {
nodeLeft.currentSteps = Integer.MAX_VALUE;
}
if(!(nodeRight.s.equals("ABCDE"))) {
nodeRight.currentSteps = Integer.MAX_VALUE;
}
return Math.min(nodeLeft.currentSteps, nodeRight.currentSteps);
// here i return the minimum amount of steps taken to achieve my goal
}
public class State {
public String s;
public int currentSteps;
public int previousMove;
public StringBuilder allMoves;
public State(String s, int currentSteps, int previousMove, StringBuilder allMoves) {
this.s = s;
this.currentSteps = currentSteps;
this.previousMove = previousMove;
this.allMoves = allMoves;
}
}
There are two main issues with your code that are causing you grief.
Firstly, you're passing the same string builder to both the left and right nodes. Which means that any append operation that happens on the left node also happens on the right.
StringBuilder sb1 = new StringBuilder();
Queue<State> leftQ = new LinkedList<>();
Queue<State> rightQ = new LinkedList<>();
State nodeLeft = new State(s, step, 0, sb1);
State nodeRight = new State(s, step, 0, sb1);
This is an easy fix, you just need to make two StringBuilders e.g.
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
State nodeLeft = new State(s, step, 0, sb1);
State nodeRight = new State(s, step, 0, sb2);
The second issue is that for each node you're actually appending to the same Stringbuilder twice in your second else if block
leftQ.offer(new State(nodeLeft.s.substring(1, 2) + nodeLeft.s.substring(0, 1) + nodeLeft.s.substring(2, 5), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 1, nodeLeft.allMoves.append("b")));
leftQ.offer(new State(nodeLeft.s.substring(4, 5) + nodeLeft.s.substring(0, 4), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 2, nodeLeft.allMoves.append("s")));
rightQ.offer(new State(nodeRight.s.substring(1, 2) + nodeRight.s.substring(0, 1) + nodeRight.s.substring(2, 5), nodeRight.currentSteps + 1, nodeRight.previousMove = 1, nodeRight.allMoves.append("b")));
rightQ.offer(new State(nodeRight.s.substring(4, 5) + nodeRight.s.substring(0, 4), nodeRight.currentSteps + 1, nodeRight.previousMove = 2, nodeRight.allMoves.append("s")));
A quick fix is to create a StringBuilder for one of the nodes you create, and pass the existing one to the other one e.g.
leftQ.offer(new State(nodeLeft.s.substring(1, 2) + nodeLeft.s.substring(0, 1) + nodeLeft.s.substring(2, 5), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 1, new StringBuilder(nodeLeft.allMoves).append("b")));
leftQ.offer(new State(nodeLeft.s.substring(4, 5) + nodeLeft.s.substring(0, 4), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 2, nodeLeft.allMoves.append("s")));