public class TextHanoi
1: import java.util.Scanner;
3: /**
4: * Animate solving the Towers of Hanoi problem.
5: * (This program doesn't work very well in NetBeans.
6: * On the CS machine it looks like a little movie....)
7: *
8: * @author Mark Young (A00000000)
9: */
10: public class TextHanoi {
11: /** Maximum number of disks we can handle */
12: public static final int MAX = 12;
13: /** Default number of disks */
14: public static final int DEFAULT = 3;
15: /** The number of pags in the game */
16: public static final int NUM_PEGS = 3;
18: /** How many "frames" are left before we pause again */
19: private static int storedEnters = 0;
21: public static void main(String[] args) {
22: // introduce yourself
23: System.out.print("\n\n"
24: + "Text Hanoi\n"
25: + "----------\n\n"
26: + "This application shows you how to solve "
27: + "the Towers of Hanoi problem.\n\n");
29: // get the number of disks from the user
30: Scanner kbd = new Scanner(System.in);
31: System.out.print("How many disks? ");
32: int numDisks = kbd.nextInt();
33: kbd.nextLine();
35: // create and play the game
36: TextHanoi game = new TextHanoi(numDisks);
37: game.play();
38: }
40: // the game instance variable
41: private int numDisks; // how many disks there are
42: private int[][] pegs; // how those disks are arranged on the pegs
43: /* IMPLEMENTATION NOTE
44: * The rows of this array represent the pegs.
45: * The elements of each row show the sizes of the disks on that peg,
46: * with 0 indicating no peg.
47: * Each row has enuf spaces for all the disks, plus one more space.
48: * That extra space says how many disks are on this peg
49: * (for convenience -- we *could* just count them).
50: *
51: * Thus the initial set up for the three disk game would be:
52: * pegs == [[3,2,1, 3], [0,0,0, 0], [0,0,0, 0]]
53: * (all disks on first peg)
54: * after the first move it'd be:
55: * pegs == [[3,2,0, 2], [0,0,0, 0], [1,0,0, 1]]
56: * (smallest disk moved to end peg)
57: * and after the second move it'd be:
58: * pegs == [[3,0,0, 1], [2,0,0, 1], [1,0,0, 1]]
59: * (one disk on each peg)
60: */
62: /**
63: * Create the game.
64: *
65: * @param n the requested number of disks
66: */
67: public TextHanoi(int n) {
68: // chack for #disks out of the range we can handle
69: if (n > MAX) {
70: System.err.println("\nTextHanoi can only go up to "+MAX+" disks!");
71: n = MAX;
72: }
73: if (n <= 0) {
74: System.err.println("\nTextHanoi needs a positive number of disks!");
75: n = DEFAULT;
76: }
78: // set up the initial board
79: numDisks = n;
80: pegs = new int[NUM_PEGS][n+1];
81: for (int i = n; i > 0; i--) {
82: pegs[0][n-i] = i;
83: }
84: pegs[0][numDisks] = n;
85: }
87: /**
88: * Play the game.
89: * Announce the moves as they're made,
90: * and draw the resulting configuration of disks.
91: */
92: public void play() {
93: // announce the start of the game
94: System.out.println("\n\n"
95: + "Towers of Hanoi -- " + numDisks + " disks\n\n");
97: // show the board and all the moves
98: showPegs();
99: showMoves(numDisks, 0, 2, 1);
101: // announce the end of the game
102: System.out.println("\n\n"
103: + "Towers of Hanoi -- solved\n\n");
104: }
106: // show all the moves
107: /**
108: * Show the moves required to solve the Towers of Hanoi problem.
109: *
110: * @param n the number of disks
111: * @param s the index of the starting peg
112: * @param f the index of the ending peg
113: * @param x the index of the extra peg
114: */
115: private void showMoves(int n, int s, int f, int x) {
116: // if there are any disks to move
117: if (n > 0) {
118: // show all the moves required to clear the bottom disk
119: showMoves(n-1, s, x, f);
121: // show moving the bottom disk
122: moveOneDisk(s, f);
124: // show all the moves required to restack onto the bottom disk
125: showMoves(n-1, x, f, s);
126: }
127: }
129: /**
130: * Show moving a single disk.
131: *
132: * @param start the index of the source peg
133: * @param finish the index of the destination peg
134: */
135: private void moveOneDisk(int start, int finish) {
136: // announce the move
137: System.out.println("\n\n"
138: + "Move a disk from peg " + start + " to peg " + finish + "\n");
140: // update the configuration of the pegs
141: push(pegs[finish], pop(pegs[start]));
143: // show the new configuration
144: showPegs();
145: }
147: /**
148: * Remove the top disk from a peg.
149: *
150: * @param peg the array representing this peg
151: * @return the number/size of the disk being moved
152: */
153: private int pop(int[] peg) {
154: peg[numDisks]--;
155: int disk = peg[peg[numDisks]];
156: peg[peg[numDisks]] = 0;
157: return disk;
158: }
160: /**
161: * Put a disk onto a peg.
162: *
163: * @param peg the array representing the target peg
164: * @param disk the number/size of the disk being moved
165: */
166: private void push(int[] peg, int disk) {
167: peg[peg[numDisks]] = disk;
168: peg[numDisks]++;
169: }
171: /**
172: * Draw the pegs and disks on the screen.
173: */
174: public void showPegs() {
175: // draw the pegs level by level (top to bottom)
176: for (int n = numDisks; n > 0; n--) {
177: showPeg(0, n);
178: showPeg(1, n);
179: showPeg(2, n);
180: System.out.println();
181: }
182: // draw the bases of the pegs
183: System.out.println("------------0------------"
184: + "------------1------------"
185: + "------------2------------\n");
187: // pause
188: pause();
189: }
191: /**
192: * Pause briefly to let the user view the configuration.
193: * If there are "frames" to be shown,
194: * pause for a small amount of time
195: * to let the full screen appear as a frame of the "movie".
196: * If there are no "frames" remaining to be shown,
197: * wait for the user to press the enter key,
198: * noting whether the user has asked for multiple frames to be shown.
199: */
200: public void pause() {
201: // NOTE: wait until user presses Enter key
202: // BUT allow user to type a number
203: // and consider that as a number of Enter key presses
205: // if there are stored Enter-key presses remaining
206: if (storedEnters > 0) {
207: // announce that you're using a stored enter-key press
208: System.out.print("\nUsing a stored ENTER...");
209: // use the press
210: storedEnters--;
211: // wait 500ms so we get an "animation" effect
212: try {
213: Thread.sleep(500);
214: } catch (Exception e) {}
215: }
216: // otherwise (no stored enter-key presses)
217: else {
218: // wait for the user to press the enter key
219: Scanner kbd = new Scanner(System.in);
220: System.out.print("\nPress ENTER to continue...");
221: String in = kbd.nextLine();
223: // if there's anything on the line
224: if (!in.equals("")) {
225: // try to interprete it as a number
226: try {
227: // and use that many key presses in total
228: storedEnters = Integer.parseInt(in);
229: storedEnters--;
230: } catch (Exception e) {}
231: }
232: }
233: }
235: /**
236: * Draw one layer of one peg on the screen.
237: * One "layer" of a peg is the amount of space a disk would take up.
238: * If there is a disk at that layer, draw it.
239: * If there is no disk at that layer, draw a bit of the peg itself.
240: *
241: * @param p the number of the peg we're drawing
242: * @param n the layer of the peg we're drawing
243: */
244: private void showPeg(int p, int n) {
245: String spacer = " ";
246: String disker = "************";
247: int disk = pegs[p][n-1];
249: // if there's no disk at this level of the peg
250: if (disk == 0) {
251: // print out an empty peg segment
252: System.out.print(spacer + "|" + spacer);
253: } else {
254: // print out the disk with appropriate space
255: String front = spacer.substring(disk) + disker.substring(0, disk);
256: String back = disker.substring(0, disk) + spacer.substring(disk);
257: System.out.print(front + "*" + back);
258: }
259: }
261: }