Towers in Hanoi in Java using only int [] [] (can this be done?)

Question

This is not homework, I do not have money to study, so I teach myself while working, moving around the dining room on the highway (long nights with a small number of customers).

I am trying to implement a simple Hanoi Towers Java solution. I use stacks and a recursive function without consulting external sources to get an opportunity to think.

I started with an array of arrays ( int[][] pegs ), but got stuck in the implementation of the "move" step, in particular, how to find out at what "height" I need to "select" from the array of the original position and at which "height" I would flush the disk to the destination position array. Of course, with Stack<Integer> this is a data structure that does this for me, and I don't need to track anything. I encoded this version, but felt negatively lazy about surrender; I am intrigued by stretching my brain and understanding how all this can be done with arrays.

Is it possible to implement this code with int[][] pegs ? How? (Enough hint, I just get stuck on the approach, I can do my work on my own after determining the right path).

BTW, is this the code I wrote "passable" Java, or am I using things incorrectly? (I'm still not sure whether to focus on Java or C ++. I have e-books for both).

 package exercises; import java.util.ArrayList; import java.util.List; import java.util.Stack; public class HanoiTowers { private static final int N_DISCS = 6; private static final int N_PEGS = 3; private static int nMoves = 0; private static final int POSITION_END_PEG = N_PEGS - 1; private static final int POSITION_START_PEG = 0; public static void main(String[] args) { List<Stack<Integer>> pegs = new ArrayList<Stack<Integer>>(N_PEGS); for (int i = 0; i < N_PEGS; i++) { pegs.add(new Stack<Integer>()); } for (int i = 0; i < N_DISCS; i++) { pegs.get(POSITION_START_PEG).push(N_DISCS - i); } printPegs(pegs); moveTowers(pegs, POSITION_START_PEG, POSITION_END_PEG, N_DISCS); System.out.println(String.format("# moves: %d", nMoves)); } private static void moveTowers(List<Stack<Integer>> pegs, int fromPeg, int toPeg, int ofHeight) { if (ofHeight <= 0) { return; } int throughPeg = N_PEGS - fromPeg - toPeg; // Kind of a hack? moveTowers(pegs, fromPeg, throughPeg, ofHeight - 1); pegs.get(toPeg).push(pegs.get(fromPeg).pop()); nMoves++; printPegs(pegs); moveTowers(pegs, throughPeg, toPeg, ofHeight - 1); } private static void printPegs(List<Stack<Integer>> stacks) { for (int j = N_DISCS - 1; j >= 0; j--) { for (int i = 0; i < N_PEGS; i++) { Stack<Integer> stack = stacks.get(i); int disc = stack.size() < j + 1 ? 0 : stack.get(j); System.out.print(String.format("[%d]", disc)); } System.out.println(); } System.out.println(); } } 

Answer 1

The best approach I can come up with for using simple arrays is to treat them as bindings, giving them a length equal to the number of disks you have, and then when you use integers, making each value equal to the size of the disk, and then, to move them, you will need to scan the entire binding from top to bottom (which one is up and down is up to you), and when you find the first one, move it to the next step, this also includes scanning the receiving binding to find the suitable one places.

If you want to avoid binding scans, you can use additional variables by storing the last character occupation or free position in the corresponding column.

Also, the best approach would be to use lists instead of simple arrays, but this may be a different exercise.

Answer 2

In my usual approach, bindings are not explicitly specified: I would just use a single value of type int[] . Each step is just a number from 1 to 3, and each disk is in a fixed position in the array. For instance:

  ***** ********* * *********** *** ******* 

Will display as {1,1,3,1,2,3} or {3,2,1,3,1,1} , depending on whether you order bindings from largest to smallest or smallest to largest .

The advantage of this view: it greatly simplifies the search algorithm for the next step. Disadvantage: this is not as close as most people visualize the problem.

pseudo code to search for the next movement using this view, assuming the drives are listed from largest to smallest:

 nextMove (int[] world, int targetPeg) { move = no move for(int i = 0; i < world.length; i++) { if(world[i] != targetPeg) { move = from world[i] to targetPeg targetPeg = ∈ {1,2,3} ∖ {world[i],targetPeg} } } return move; }