cuhlecainez
New Coder
Right now I am trying to implemt DFS search within Tower of Hanoi. I am getting hung up with an error. I think it is something to do will my logic on the successor functions. Any advice where to start looking.
Console Log:
[1, 2, 3] [] []
[2, 3] [1] []
[3] [1] [2]
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
at java.base/java.util.Objects.checkIndex(Objects.java:373)
at java.base/java.util.ArrayList.get(ArrayList.java:425)
at HTProblem.tower2Successors(HTProblem.java:180)
at HTProblem.successors(HTProblem.java:73)
at HTProblem.dfs(HTProblem.java:49)
at HTProblem.main(HTProblem.java:15)
[CODE lang="java" highlight="55-297"]import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class HTProblem {
private static Stack<HTNode> stack = new Stack<HTNode>();
private static List<HTNode> path = new ArrayList<HTNode>();
private static HTNode initial;
private static HTNode goal;
private static HTNode current;
public static void main(String[] args) {
initialize();
dfs();
}
public static void initialize() {
List<Integer> tower1 = new ArrayList<Integer>();
List<Integer> tower2 = new ArrayList<Integer>();
List<Integer> tower3 = new ArrayList<Integer>();
List<List<Integer>> ht = new ArrayList<List<Integer>>();
for (int i = 1; i <= 3; i++) {
tower1.add(i);
}
ht.add(tower1);
ht.add(tower2);
ht.add(tower3);
goal = new HTNode(ht.get(2), ht.get(1), ht.get(0));
initial = new HTNode(ht.get(0), ht.get(1), ht.get(2));
stack.push(initial);
}
public static void dfs() {
while (true) {
if (stack.isEmpty()) {
System.out.println("No solution found");
return;
}
current = stack.pop();
if (current.equals(goal)) {
printState(current);
break;
} else {
printState(current);
successors(current);
path.add(current);
}
}
}
public static void successors(HTNode ns) {
int top1 = ns.head(1);
int top2 = ns.head(2);
int top3 = ns.head(3);
HTNode n1 = new HTNode(ns);
HTNode n2 = new HTNode(ns);
HTNode n3 = new HTNode(ns);
HTNode n4 = new HTNode(ns);
HTNode n5 = new HTNode(ns);
HTNode n6 = new HTNode(ns);
if (top1 > 0) {
tower1Successors(n1, n2, top1, top2, top3);
}
if (top2 > 0) {
tower2Successors(n3, n4, top1, top2, top3);
}
if (top3 > 0) {
tower3Successors(n5, n6, top1, top2, top3);
}
}
public static void tower1Successors(HTNode n1, HTNode n2, int top1, int top2, int top3) {
if ((top1 < top2 && top1 < top3)
|| ((top2 == 0) && (top3 == 0))
|| ((top2 == 0) && (top1 < top3))
|| ((top1 < top2) && (top3 == 0))) {
boolean duplicate = false;
n1.getT2().add(0, n1.getT1().get(0));
n1.getT1().remove(0);
for (HTNode n : path) {
if (n.equals(n1)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n1);
stack.push(n1);
}
duplicate = false;
printState(n2);
n2.getT3().add(0, n2.getT1().get(0));
n2.getT1().remove(0);
for (HTNode n : path) {
if (n.equals(n2)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n2);
stack.push(n2);
}
} else if ((top1 < top2) || (top2 == 0)) {
boolean duplicate = false;
n1.getT2().add(0, n1.getT1().get(0));
n1.getT1().remove(0);
for (HTNode n : path) {
if (n.equals(n1)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n1);
stack.push(n1);
}
} else if ((top1 < top3) || (top3 == 0)) {
boolean duplicate = false;
n1.getT3().add(0, n1.getT1().get(0));
n1.getT1().remove(0);
for (HTNode n : path) {
if (n.equals(n1)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n1);
stack.push(n1);
}
}
}
public static void tower2Successors(HTNode n3, HTNode n4, int top1, int top2, int top3) {
if ((top2 < top1 && top2 < top3)
|| (top1 == 0) && (top3 == 0)
|| (top1 == 0) && (top2 < top3)
|| (top2 < top1) && (top3 == 0)) {
boolean duplicate = false;
n3.getT1().add(0, n3.getT2().get(0));
n3.getT2().remove(0);
for (HTNode n : path) {
if (n.equals(n3)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n3);
stack.push(n3);
}
duplicate = false;
n4.getT3().add(0, n4.getT2().get(0));
n4.getT2().remove(0);
for (HTNode n : path) {
if (n.equals(n4)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n4);
stack.push(n4);
}
} else if ((top2 < top1) || (top1 == 0)) {
boolean duplicate = false;
n3.getT1().add(0, n3.getT2().get(0));
n3.getT2().remove(0);
for (HTNode n : path) {
if (n.equals(n3)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n3);
stack.push(n3);
}
} else if ((top2 < top3) || (top3 == 0)) {
boolean duplicate = false;
n3.getT3().add(0, n3.getT2().get(0));
n3.getT2().remove(0);
for (HTNode n : path) {
if (n.equals(n3)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n3);
stack.push(n3);
}
}
}
public static void tower3Successors(HTNode n5, HTNode n6, int top1, int top2, int top3) {
if ((top3 < top1) && (top3 < top2)
|| (top1 == 0) && (top2 == 0)
|| (top1 == 0) && (top3 < top2)
|| (top3 < top1) && (top2 == 0)) {
boolean duplicate = false;
n5.getT1().add(0, n5.getT3().get(0));
n5.getT3().remove(0);
for (HTNode n : path) {
if (n.equals(n5)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n5);
stack.push(n5);
}
duplicate = false;
n6.getT2().add(0, n6.getT3().get(0));
n6.getT3().remove(0);
for (HTNode n : path) {
if (n.equals(n6)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n6);
stack.push(n6);
}
} else if ((top3 < top1) || (top1 == 0)) {
boolean duplicate = false;
n5.getT1().add(0, n5.getT3().get(0));
n5.getT3().remove(0);
for (HTNode n : path) {
if (n.equals(n5)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n5);
stack.push(n5);
}
} else if ((top3 < top2) || (top2 == 0)) {
boolean duplicate = false;
n5.getT2().add(0, n5.getT3().get(0));
n5.getT3().remove(0);
for (HTNode n : path) {
if (n.equals(n5)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n5);
stack.push(n5);
}
}
}
public static void printState(HTNode n) {
if (n.equals(goal)) {
System.out.println("Solution Found!");
System.out.println(n.getT1() + " " + n.getT2() + " " + n.getT3());
} else {
System.out.println(n.getT1() + " " + n.getT2() + " " + n.getT3());
}
}
}
[/CODE]
Console Log:
[1, 2, 3] [] []
[2, 3] [1] []
[3] [1] [2]
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
at java.base/java.util.Objects.checkIndex(Objects.java:373)
at java.base/java.util.ArrayList.get(ArrayList.java:425)
at HTProblem.tower2Successors(HTProblem.java:180)
at HTProblem.successors(HTProblem.java:73)
at HTProblem.dfs(HTProblem.java:49)
at HTProblem.main(HTProblem.java:15)
Java:
import java.util.ArrayList;
import java.util.List;
public class HTNode {
private List<List<Integer>> ht = new ArrayList<List<Integer>>();
public boolean visited;
public HTNode(List<Integer> t1, List<Integer> t2, List<Integer> t3) {
ht.add(t1);
ht.add(t2);
ht.add(t3);
visited = false;
}
public HTNode(HTNode n) {
ht.add(n.getT1());
ht.add(n.getT2());
ht.add(n.getT3());
}
public List<Integer> getT1() {
return this.ht.get(0);
}
public List<Integer> getT2() {
return this.ht.get(1);
}
public List<Integer> getT3() {
return this.ht.get(2);
}
public int head(int tower) {
int value = 0;
List<Integer> temp = new ArrayList<Integer>();
if (tower == 1) {
temp.addAll(getT1());
if (temp.size() >= 1) {
value = temp.remove(temp.size() - temp.size());
}
}
if (tower == 2) {
temp.addAll(getT2());
if (temp.size() >= 1) {
value = temp.remove(temp.size() - temp.size());
}
}
if (tower == 3) {
temp.addAll(getT3());
if (temp.size() >= 1) {
value = temp.remove(temp.size() - temp.size());
}
}
return value;
}
public boolean equals(HTNode n) {
if (this.ht.get(0).equals(n.ht.get(0)) && this.ht.get(1).equals(n.ht.get(1)) && this.ht.get(2).equals(n.ht.get(2))) {
return true;
} else {
return false;
}
}
}
[CODE lang="java" highlight="55-297"]import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class HTProblem {
private static Stack<HTNode> stack = new Stack<HTNode>();
private static List<HTNode> path = new ArrayList<HTNode>();
private static HTNode initial;
private static HTNode goal;
private static HTNode current;
public static void main(String[] args) {
initialize();
dfs();
}
public static void initialize() {
List<Integer> tower1 = new ArrayList<Integer>();
List<Integer> tower2 = new ArrayList<Integer>();
List<Integer> tower3 = new ArrayList<Integer>();
List<List<Integer>> ht = new ArrayList<List<Integer>>();
for (int i = 1; i <= 3; i++) {
tower1.add(i);
}
ht.add(tower1);
ht.add(tower2);
ht.add(tower3);
goal = new HTNode(ht.get(2), ht.get(1), ht.get(0));
initial = new HTNode(ht.get(0), ht.get(1), ht.get(2));
stack.push(initial);
}
public static void dfs() {
while (true) {
if (stack.isEmpty()) {
System.out.println("No solution found");
return;
}
current = stack.pop();
if (current.equals(goal)) {
printState(current);
break;
} else {
printState(current);
successors(current);
path.add(current);
}
}
}
public static void successors(HTNode ns) {
int top1 = ns.head(1);
int top2 = ns.head(2);
int top3 = ns.head(3);
HTNode n1 = new HTNode(ns);
HTNode n2 = new HTNode(ns);
HTNode n3 = new HTNode(ns);
HTNode n4 = new HTNode(ns);
HTNode n5 = new HTNode(ns);
HTNode n6 = new HTNode(ns);
if (top1 > 0) {
tower1Successors(n1, n2, top1, top2, top3);
}
if (top2 > 0) {
tower2Successors(n3, n4, top1, top2, top3);
}
if (top3 > 0) {
tower3Successors(n5, n6, top1, top2, top3);
}
}
public static void tower1Successors(HTNode n1, HTNode n2, int top1, int top2, int top3) {
if ((top1 < top2 && top1 < top3)
|| ((top2 == 0) && (top3 == 0))
|| ((top2 == 0) && (top1 < top3))
|| ((top1 < top2) && (top3 == 0))) {
boolean duplicate = false;
n1.getT2().add(0, n1.getT1().get(0));
n1.getT1().remove(0);
for (HTNode n : path) {
if (n.equals(n1)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n1);
stack.push(n1);
}
duplicate = false;
printState(n2);
n2.getT3().add(0, n2.getT1().get(0));
n2.getT1().remove(0);
for (HTNode n : path) {
if (n.equals(n2)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n2);
stack.push(n2);
}
} else if ((top1 < top2) || (top2 == 0)) {
boolean duplicate = false;
n1.getT2().add(0, n1.getT1().get(0));
n1.getT1().remove(0);
for (HTNode n : path) {
if (n.equals(n1)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n1);
stack.push(n1);
}
} else if ((top1 < top3) || (top3 == 0)) {
boolean duplicate = false;
n1.getT3().add(0, n1.getT1().get(0));
n1.getT1().remove(0);
for (HTNode n : path) {
if (n.equals(n1)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n1);
stack.push(n1);
}
}
}
public static void tower2Successors(HTNode n3, HTNode n4, int top1, int top2, int top3) {
if ((top2 < top1 && top2 < top3)
|| (top1 == 0) && (top3 == 0)
|| (top1 == 0) && (top2 < top3)
|| (top2 < top1) && (top3 == 0)) {
boolean duplicate = false;
n3.getT1().add(0, n3.getT2().get(0));
n3.getT2().remove(0);
for (HTNode n : path) {
if (n.equals(n3)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n3);
stack.push(n3);
}
duplicate = false;
n4.getT3().add(0, n4.getT2().get(0));
n4.getT2().remove(0);
for (HTNode n : path) {
if (n.equals(n4)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n4);
stack.push(n4);
}
} else if ((top2 < top1) || (top1 == 0)) {
boolean duplicate = false;
n3.getT1().add(0, n3.getT2().get(0));
n3.getT2().remove(0);
for (HTNode n : path) {
if (n.equals(n3)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n3);
stack.push(n3);
}
} else if ((top2 < top3) || (top3 == 0)) {
boolean duplicate = false;
n3.getT3().add(0, n3.getT2().get(0));
n3.getT2().remove(0);
for (HTNode n : path) {
if (n.equals(n3)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n3);
stack.push(n3);
}
}
}
public static void tower3Successors(HTNode n5, HTNode n6, int top1, int top2, int top3) {
if ((top3 < top1) && (top3 < top2)
|| (top1 == 0) && (top2 == 0)
|| (top1 == 0) && (top3 < top2)
|| (top3 < top1) && (top2 == 0)) {
boolean duplicate = false;
n5.getT1().add(0, n5.getT3().get(0));
n5.getT3().remove(0);
for (HTNode n : path) {
if (n.equals(n5)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n5);
stack.push(n5);
}
duplicate = false;
n6.getT2().add(0, n6.getT3().get(0));
n6.getT3().remove(0);
for (HTNode n : path) {
if (n.equals(n6)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n6);
stack.push(n6);
}
} else if ((top3 < top1) || (top1 == 0)) {
boolean duplicate = false;
n5.getT1().add(0, n5.getT3().get(0));
n5.getT3().remove(0);
for (HTNode n : path) {
if (n.equals(n5)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n5);
stack.push(n5);
}
} else if ((top3 < top2) || (top2 == 0)) {
boolean duplicate = false;
n5.getT2().add(0, n5.getT3().get(0));
n5.getT3().remove(0);
for (HTNode n : path) {
if (n.equals(n5)) {
duplicate = true;
}
}
if (duplicate == false) {
path.add(n5);
stack.push(n5);
}
}
}
public static void printState(HTNode n) {
if (n.equals(goal)) {
System.out.println("Solution Found!");
System.out.println(n.getT1() + " " + n.getT2() + " " + n.getT3());
} else {
System.out.println(n.getT1() + " " + n.getT2() + " " + n.getT3());
}
}
}
[/CODE]