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

Question

This is not homework, I don't have money for school so I am teaching myself whilst working shifts at a tollbooth on the highway (long nights with few customers).

I am trying to implement a simple version of the Hanoi Towers solver in Java. I am using stacks and a recursive function, without consulting external sources so as to get a chance to think myself.

I started with an array of arrays (int[][] pegs) but got stuck on the implementation of the "move" step, particularly how to know at which "height" I would need to "pick" from the starting-position array and at which "height" I would drop the disc at the destination-position array. Of course with Stack<Integer> it's the data structure that does this for me and I don't have to keep track of anything. I coded this version but felt negatively lazy about giving up; I am intrigued by stretching my brain and understanding how one could do it all with arrays.

Is it possible to implement this code using int[][] pegs? How? (A hint will suffice, I am just stuck on the approach, I can do the legwork myself after having identified the right path).

BTW, is the code I wrote "passable" Java or am I misusing things? (I am still unsure about 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();
  }
}

Astrology

You can definitely achieve this with arrays. Ultimately, all of this abstraction boils down to manipulation of arrays, so you're just giving up the ease of use that the extra layers bring. Good exercise, though. It can often be too easy to rely on the standard Java classes which make things easy whilst forgetting what's really going on. I am not an expert on this problem, I am only vaguely familiar with it, so I won't tell you whether you are doing the right thing. However, I do think you should look at your style. Try spacing things out more. That makes it a hell of a lot easier to read. – Unsure

Once this code is functional I would recommend publishing it to codereview.stackexchange.com, as that community will be good with your "is this passable code?" question. – Instantly

The code is functional, I will probably submit it for review there for general improvement suggestion. How about the specific question of "how to do this using an int[][]"? This belongs here, I think. – Astrology

i've been trying to understand your code but i'm confused about the 3rd line in main. you seem to add N_DISCS stacks to pegs. i think you need two loops in main, the new one goes before what you have now and adds N_PEGS stacks. currently i think it would crash if you tried it with N_DISCS < N_PEGS. also kudos for doing this. you will eventually get better (even if no-one gives a good answer here). keep writing code and try reading examples online too and try to think why it was written the way it was... good luck. – Lyonnaise

@andrewcooke: you are right, I am going to fix that bug... – Astrology

I'd advise you to create a basic implementation of Stack<Integer> yourself, based on arrays. Then, with that code you have created yourself, you can implement towers on hanoi much easier, with more abstraction and still all your own code. – Province

Answer 1

The best approach i can think of using simple arrays, is by treating them as the pegs, giving them a lenght that is equal to the number of discs you have, then, as you are using integers, making the value of each position equal to the size of the disc, then to move them you will need to scan the entire peg from the top to the bottom (what is top and bottom is up to you), and when you find the first one, move it to the next peg, this also includes scanning the receiving peg to look for a suitable location.

If you want to avoid the scanning of the peg, you can use additional variables, storing the latest know occuped or free position in the corresponding peg.

Also, a best approach would be using lists instead of simple arrays, but it could be another exercise.

Julianejuliann

Answer 2

My usual approach wouldn't explicitly represent pegs: I would just use a single value of type int[]. Each peg is just a number between 1 and 3, and each disc is at a fixed position in the array. For example:

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

Would be represented as either {1,1,3,1,2,3} or {3,2,1,3,1,1}, depending on whether you order the pegs from largest to smallest or smallest to largest.

The advantage to this representation: it greatly simplifies the algorithm for finding the next move. The disadvantage: it's not as close to how most people visualize the problem.

pseudocode for finding the next move using this representation, assuming discs 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;
}

Ddene