public class TextHanoi
1: import java.util.Scanner;
2:
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;
17:
18: /** How many "frames" are left before we pause again */
19: private static int storedEnters = 0;
20:
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");
28:
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();
34:
35: // create and play the game
36: TextHanoi game = new TextHanoi(numDisks);
37: game.play();
38: }
39:
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 disk.
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: */
61:
62: /**
63: * Create the game.
64: *
65: * @param reqNumDisks the requested number of disks
66: */
67: public TextHanoi(int reqNumDisks) {
68: // chack for #disks out of the range we can handle
69: if (reqNumDisks > MAX) {
70: System.out.println();
71: System.err.println("TextHanoi can only go up to " + MAX
72: + " disks!");
73: reqNumDisks = MAX;
74: }
75: if (reqNumDisks <= 0) {
76: System.out.println();
77: System.err.println("TextHanoi needs a positive number of disks!");
78: reqNumDisks = DEFAULT;
79: }
80:
81: // set up the initial board
82: numDisks = reqNumDisks;
83: pegs = new int[NUM_PEGS][numDisks + 1];
84: for (int i = numDisks; i > 0; i--) {
85: pegs[0][numDisks-i] = i;
86: }
87: pegs[0][numDisks] = numDisks;
88: }
89:
90: /**
91: * Play the game.
92: * Announce the moves as they're made,
93: * and draw the resulting configuration of disks.
94: */
95: public void play() {
96: // announce the start of the game
97: System.out.println("\n\n"
98: + "Towers of Hanoi -- " + numDisks + " disks\n\n");
99:
100: // show the board and all the moves
101: showPegs();
102: showMoves(numDisks, 0, 2, 1);
103:
104: // announce the end of the game
105: System.out.println("\n\n"
106: + "Towers of Hanoi -- solved\n\n");
107: }
108:
109: // show all the moves
110: /**
111: * Show the moves required to solve the Towers of Hanoi problem.
112: *
113: * @param curNumDisks the number of disks
114: * @param start the index of the starting peg
115: * @param finish the index of the ending peg
116: * @param extra the index of the extra peg
117: */
118: private void showMoves(int curNumDisks, int start, int finish, int extra) {
119: // if there are any disks to move
120: if (curNumDisks > 0) {
121: // show all the moves required to clear the bottom disk
122: showMoves(curNumDisks - 1, start, extra, finish);
123:
124: // show moving the bottom disk
125: moveOneDisk(start, finish);
126:
127: // show all the moves required to restack onto the bottom disk
128: showMoves(curNumDisks - 1, extra, finish, start);
129: }
130: }
131:
132: /**
133: * Show moving a single disk.
134: *
135: * @param start the index of the source peg
136: * @param finish the index of the destination peg
137: */
138: private void moveOneDisk(int start, int finish) {
139: // announce the move
140: System.out.println("\n\n"
141: + "Move a disk from peg " + start + " to peg " + finish
142: + "\n");
143:
144: // update the configuration of the pegs
145: push(pegs[finish], pop(pegs[start]));
146:
147: // show the new configuration
148: showPegs();
149: }
150:
151: /**
152: * Remove the top disk from a peg.
153: *
154: * @param peg the array representing this peg
155: * @return the number/size of the disk being moved
156: */
157: private int pop(int[] peg) {
158: peg[numDisks]--;
159: int disk = peg[peg[numDisks]];
160: peg[peg[numDisks]] = 0;
161: return disk;
162: }
163:
164: /**
165: * Put a disk onto a peg.
166: *
167: * @param peg the array representing the target peg
168: * @param disk the number/size of the disk being moved
169: */
170: private void push(int[] peg, int disk) {
171: peg[peg[numDisks]] = disk;
172: peg[numDisks]++;
173: }
174:
175: /**
176: * Draw the pegs and disks on the screen.
177: */
178: public void showPegs() {
179: // draw the pegs level by level (top to bottom)
180: for (int n = numDisks; n > 0; n--) {
181: showPeg(0, n);
182: showPeg(1, n);
183: showPeg(2, n);
184: System.out.println();
185: }
186: // draw the bases of the pegs
187: System.out.println("------------0------------"
188: + "------------1------------"
189: + "------------2------------\n");
190:
191: // pause
192: pause();
193: }
194:
195: /**
196: * Pause briefly to let the user view the configuration.
197: * If there are "frames" to be shown,
198: * pause for a small amount of time
199: * to let the full screen appear as a frame of the "movie".
200: * If there are no "frames" remaining to be shown,
201: * wait for the user to press the enter key,
202: * noting whether the user has asked for multiple frames to be shown.
203: */
204: public void pause() {
205: // NOTE: wait until user presses Enter key
206: // BUT allow user to type a number
207: // and consider that as a number of Enter key presses
208:
209: // if there are stored Enter-key presses remaining
210: if (storedEnters > 0) {
211: // announce that you're using a stored enter-key press
212: System.out.print("\nUsing a stored ENTER...");
213: // use the press
214: storedEnters--;
215: // wait 500ms so we get an "animation" effect
216: try {
217: Thread.sleep(500);
218: } catch (Exception e) {}
219: }
220: // otherwise (no stored enter-key presses)
221: else {
222: // wait for the user to press the enter key
223: Scanner kbd = new Scanner(System.in);
224: System.out.print("\nPress ENTER to continue...");
225: String in = kbd.nextLine();
226:
227: // if there's anything on the line
228: if (!in.equals("")) {
229: // try to interprete it as a number
230: try {
231: // and use that many key presses in total
232: storedEnters = Integer.parseInt(in);
233: storedEnters--;
234: } catch (Exception e) {}
235: }
236: }
237: }
238:
239: /**
240: * Draw one layer of one peg on the screen.
241: * One "layer" of a peg is the amount of space a disk would take up.
242: * If there is a disk at that layer, draw it.
243: * If there is no disk at that layer, draw a bit of the peg itself.
244: *
245: * @param peg the number of the peg we're drawing
246: * @param layer the layer of the peg we're drawing
247: */
248: private void showPeg(int peg, int layer) {
249: String spacer = " ";
250: String disker = "************";
251: int disk = pegs[peg][layer - 1];
252:
253: // if there's no disk at this level of the peg
254: if (disk == 0) {
255: // print out an empty peg segment
256: System.out.print(spacer + "|" + spacer);
257: } else {
258: // print out the disk with appropriate space
259: String front = spacer.substring(disk) + disker.substring(0, disk);
260: String back = disker.substring(0, disk) + spacer.substring(disk);
261: System.out.print(front + "*" + back);
262: }
263: }
264:
265: }