Tower of Hanoi move method

Question

So I have some code which solves the tower of hanoi problem. The code that I have written is pretty clunky and seems to repeat itself multiple times.

Was just wondering if there was some way of improving it and reducing the repetitive nature of it.

The move() method returns all the possible moves from a given composition.

 public static ArrayList<Stack[]> move(Stack<Integer> first, Stack<Integer> second, Stack<Integer> third) {
 // move first
 ArrayList<Stack[]> returnArrayList = new ArrayList<>();
 if (!first.isEmpty()) {
 Stack<Integer> newFirst = new Stack();
 newFirst.addAll(first);
 Stack<Integer> newSecond = new Stack();
 newSecond.addAll(second);
 Stack<Integer> newThird = new Stack();
 newThird.addAll(third);
 if (newSecond.isEmpty() || (int) newFirst.peek() < (int) newSecond.peek()) {
 newSecond.add(newFirst.pop());
 }
 Stack[] newStacks = {newFirst, newSecond, newThird};
 returnArrayList.add(newStacks);
 }
 if (!first.isEmpty()) {
 Stack<Integer> newFirst = new Stack();
 newFirst.addAll(first);
 Stack<Integer> newSecond = new Stack();
 newSecond.addAll(second);
 Stack<Integer> newThird = new Stack();
 newThird.addAll(third);
 if (newThird.isEmpty() || (int) newFirst.peek() < (int) newThird.peek()) {
 newThird.add(newFirst.pop());
 }
 Stack[] newStacks = {newFirst, newSecond, newThird};
 returnArrayList.add(newStacks);
 }
 // move second
 if (!second.isEmpty()) {
 Stack<Integer> newFirst = new Stack();
 newFirst.addAll(first);
 Stack<Integer> newSecond = new Stack();
 newSecond.addAll(second);
 Stack<Integer> newThird = new Stack();
 newThird.addAll(third);
 if (newFirst.isEmpty() || (int) newSecond.peek() < (int) newFirst.peek()) {
 newFirst.add(newSecond.pop());
 }
 Stack[] newStacks = {newFirst, newSecond, newThird};
 returnArrayList.add(newStacks);
 }
 if (!second.isEmpty()) {
 Stack<Integer> newFirst = new Stack();
 newFirst.addAll(first);
 Stack<Integer> newSecond = new Stack();
 newSecond.addAll(second);
 Stack<Integer> newThird = new Stack();
 newThird.addAll(third);
 if (newThird.isEmpty() || (int) newSecond.peek() < (int) newThird.peek()) {
 newThird.add(newSecond.pop());
 }
 Stack[] newStacks = {newFirst, newSecond, newThird};
 returnArrayList.add(newStacks);
 }
 // move third
 if (!third.isEmpty()) {
 Stack<Integer> newFirst = new Stack();
 newFirst.addAll(first);
 Stack<Integer> newSecond = new Stack();
 newSecond.addAll(second);
 Stack<Integer> newThird = new Stack();
 newThird.addAll(third);
 if (newSecond.isEmpty() || (int) newThird.peek() < (int) newSecond.peek()) {
 newSecond.add(newThird.pop());
 }
 Stack[] newStacks = {newFirst, newSecond, newThird};
 returnArrayList.add(newStacks);
 }
 if (!third.isEmpty()) {
 Stack<Integer> newFirst = new Stack();
 newFirst.addAll(first);
 Stack<Integer> newSecond = new Stack();
 newSecond.addAll(second);
 Stack<Integer> newThird = new Stack();
 newThird.addAll(third);
 if (newFirst.isEmpty() || (int) newThird.peek() < (int) newFirst.peek()) {
 newFirst.add(newThird.pop());
 }
 Stack[] newStacks = {newFirst, newSecond, newThird};
 returnArrayList.add(newStacks);
 }
 return returnArrayList;
 }

• User319: I don't think you'll ever enteir the second if (!first.isEmpty()) block. Or am I misunderstanding something?
• Small Legend: Yeah you're misunderstanding, the initial setup is first = {3,2,1} so it is not empty, thus that clause is true @User319
• User319: Ah, I was misreading returnArrayList as return ArrayList and didn't scan the rest of the line!

Answer 1

You have 3 comments in your method that devide it into 3 "named sections".

The proper representation of "named sections" in Java (and most other programming languages) is a method (aka function/procedure).

So your method should look like this:

public static ArrayList<Stack[]> move(Stack<Integer> first, Stack<Integer> second, Stack<Integer> third) { 
 ArrayList<Stack[]> returnArrayList = new ArrayList<>();
 moveFirst(first, second, third, returnArrayList);
 moveSecond(first, second, third, returnArrayList);
 moveThird(first, second, third, returnArrayList);
 return returnArrayList;
}

And the code in that named sections would be moved to this new methods:

 public static ArrayList<Stack[]> moveFirst(Stack<Integer> first, Stack<Integer> second, Stack<Integer> third, ArrayList<Stack[]> returnArrayList) { 
 if (!first.isEmpty()) {
 Stack<Integer> newFirst = new Stack();
 newFirst.addAll(first);
 Stack<Integer> newSecond = new Stack();
 newSecond.addAll(second);
 Stack<Integer> newThird = new Stack();
 newThird.addAll(third);
 if (newSecond.isEmpty() || (int) newFirst.peek() < (int) newSecond.peek()) {
 newSecond.add(newFirst.pop());
 }
 Stack[] newStacks = {newFirst, newSecond, newThird};
 returnArrayList.add(newStacks);
 }
 if (!first.isEmpty()) {
 Stack<Integer> newFirst = new Stack();
 newFirst.addAll(first);
 Stack<Integer> newSecond = new Stack();
 newSecond.addAll(second);
 Stack<Integer> newThird = new Stack();
 newThird.addAll(third);
 if (newThird.isEmpty() || (int) newFirst.peek() < (int) newThird.peek()) {
 newThird.add(newFirst.pop());
 }
 Stack[] newStacks = {newFirst, newSecond, newThird};
 returnArrayList.add(newStacks);
 }
}

I skip the copy of the others...

Next thing to do is to use the refactoring capability of your IDE:
in the method moveFirst:

• place the cursor on variable Name first in the line if (!first.isEmpty()) { (either one)
• From the IDEs refactoring tools select "Rename in File"
• change the name of first to a
• place the cursor on variable Name second in the line newSecond.addAll(second);
• From the IDEs refactoring tools select "Rename in File"
• change the name of second to b
• place the cursor on variable Name third in the line newThird.addAll(third);
• From the IDEs refactoring tools select "Rename in File"
• change the name of third to c
• repeat this to rename newFirst, newSecond and newThird to d, e and f respectively.

The new names are rather poor by intension to make a point soon....

It should now look like this:

public static ArrayList<Stack[]> movea(Stack<Integer> a, Stack<Integer> b, Stack<Integer> c, ArrayList<Stack[]> returnArrayList) { 
 if (!a.isEmpty()) {
 Stack<Integer> d = new Stack();
 d.addAll(a);
 Stack<Integer> e = new Stack();
 e.addAll(b);
 Stack<Integer> f = new Stack();
 f.addAll(c);
 if (e.isEmpty() || (int) d.peek() < (int) e.peek()) {
 e.add(d.pop());
 }
 Stack[] newStacks = {d, e, f};
 returnArrayList.add(newStacks);
 }
 if (!a.isEmpty()) {
 Stack<Integer> d = new Stack();
 d.addAll(a);
 Stack<Integer> e = new Stack();
 e.addAll(b);
 Stack<Integer> f = new Stack();
 f.addAll(c);
 if (f.isEmpty() || (int) d.peek() < (int) f.peek()) {
 f.add(d.pop());
 }
 Stack[] newStacks = {d, e, f};
 returnArrayList.add(newStacks);
 }
}

Then go to method moveSecond

• place the cursor on variable Name second in the line if (!first.isEmpty()) { (either one)
• From the IDEs refactoring tools select "Rename in File"
• change the name of second to a
• place the cursor on variable Name first in the line newSecond.addAll(first);
• change the name of first to b
• place the cursor on variable Name third in the line newThird.addAll(third);
• From the IDEs refactoring tools select "Rename in File"
• change the name of third to c
• repeat this to rename newFirst, newSecond and newThird to e, d and f respectively (mind the new order of e and d).

the result shuld be like this:

public static ArrayList<Stack[]> moveFirst(Stack<Integer> b, Stack<Integer> a, Stack<Integer> c, ArrayList<Stack[]> returnArrayList) { 
 if (!a.isEmpty()) {
 Stack<Integer> e = new Stack();
 e.addAll(b);
 Stack<Integer> d = new Stack();
 d.addAll(a);
 Stack<Integer> f = new Stack();
 f.addAll(c);
 if (e.isEmpty() || (int) d.peek() < (int) e.peek()) {
 e.add(d.pop());
 }
 Stack[] newStacks = {e, d, f};
 returnArrayList.add(newStacks);
 }
 if (!a.isEmpty()) {
 Stack<Integer> e = new Stack();
 e.addAll(b);
 Stack<Integer> d = new Stack();
 d.addAll(a);
 Stack<Integer> f = new Stack();
 f.addAll(c);
 if (f.isEmpty() || (int) d.peek() < (int) f.peek()) {
 f.add(d.pop());
 }
 Stack[] newStacks = {e, d, f};
 returnArrayList.add(newStacks);
 }
}

If you now look at this two methods, you see that the logic is exactly the same in both except the order in which the new stack objects are created. The only important difference is the order of arguments in the method signature.

This means that you can change you original method to this:

public static ArrayList<Stack[]> move(Stack<Integer> first, Stack<Integer> second, Stack<Integer> third) { 
 ArrayList<Stack[]> returnArrayList = new ArrayList<>();
 moveFirst(first, second, third, returnArrayList);
 //moveSecond(second, first, third, returnArrayList);
 moveFirst(second, first, third, returnArrayList);
 moveThird(first, second, third, returnArrayList);
 return returnArrayList;
}

And guess what: this will also work with the method moveThird:

public static ArrayList<Stack[]> move(Stack<Integer> first, Stack<Integer> second, Stack<Integer> third) { 
 ArrayList<Stack[]> returnArrayList = new ArrayList<>();
 moveFirst(first, second, third, returnArrayList);
 //moveSecond(second, first, third, returnArrayList);
 moveFirst(second, first, third, returnArrayList);
 //moveThird(first, second, third, returnArrayList);
 moveFirst(third, second, first, returnArrayList);
 return returnArrayList;
}

Now you can delete the methods moveSecond and moveThird.

You can use the same technique to merge the two if blocks into a single parameterized method.