P08 TOWER OF HANOI

PROGRAMMING II

Pair Programming is NOT allowed for this assignment. 
This Assignment involves developing a Tower of Hanoi puzzle that makes use of an array-based
stack implementation. You will also implement a solver for this puzzle that is based on a recursive
algorithm.
OBJECTIVES AND GRADING CRITERIA
The main goals of this assignment include 1) implementing common stack operations using an array
data structure, 2) making use of this stack in an application, and 3) implementing a recursive
solution to the Tower of Hanoi puzzle.
25
points
5 zyBooks Tests: automated grading test results are visible upon submission, and allow
multiple opportunities to correct the organization and functionality of your code. Your
highest scoring submission prior to the deadline will be recorded.
25
points
5 Hidden Tests: automated grading tests are run after the assignment’s deadline. They
check for similar functionality and organizational correctness as the zyBooks Tests. But
you will NOT be able to resubmit corrections for extra points, and should therefore
consider and test your own code even more thoroughly.
GETTING STARTED
0. Create a new Java8 project in Eclipse. You can name this project whatever you like, but
TowerOfHanoi is a descriptive choice. If you are not familiar with the Tower of Hanoi puzzle,
P08 TOWER OF HANOI
LECTURE NOTES
please review the description from the top of this wikipedia page.
THE DISK
1. Create a new class called Disk which implements the Comparable<Disk interface. Objects of
this type will be used to represent the disks in this puzzle. This class must contain exactly the
private field and publicly accessible constructor/methods shown in the following:
You may add additional private methods to help organize your implementation of these
functions, but may not add additional fields or public methods. We recommend writing some
tests to help convince yourself that this class is correctly implemented before moving on to the
next step.
THE ROD
2. As described in the wikipedia page, the Tower of Hanoi puzzle makes use of three rods. Add a
new class called Rod which implement the Comparable<Rod interface to your project. This Rod
class will implement many of the common StackADT operations, and will make use of a arraybased stack implementation (as discussed in lecture). This class must contain exactly the private
fields and publicly accessible constructor/methods shown in the following:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private int size; // 1-9: restricts disk movement, and used for drawing
/**
* Constructs a new immutable disk object with the specified size.
* @param size is used for drawing and comparing against other disks.
* @throws IllegalArgumentException when size is not between 1 and 9.
*/
public Disk(int size) throws IllegalArgumentException { }
/**
* Compares one disk to another to determine which is larger, and therefore
* which can be moved on top of the other.
* @param other is a reference to the disk we are comparing this one to.
* @return a positive number when this.size other.size,
* a negative number when this.size < other.size, or
* zero when this.size == other.size, or other is null.
*/
@Override
public int compareTo(Disk other) { return 0; }
/**
* The string representation of this disk object includes its integer size
* surrounded by size-1 equals characters (=) on each side, and enclosed
* within angle brackets (<). For example:
* size 1: "<1"
* size 2: "<=2="
* size 3: "<==3=="
* @return the string representation of this disk object based on its size.
*/
@Override
public String toString() { return null; }
1 private int numberOfDisks; // tracks the number of disks on this rod
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
private Disk[] disks; // stores references to the disks on this rod
// index 0: bottom, index discNumber-1: top
/**
* Constructs a new rod that can hold a maximum of maxHeight Disks. The
* numberOfDisks new Disks will be created with sizes between 1 and
* numberOfDisks (inclusive), and arranged from largest (on bottom) to the
* smallest (on top) on this Rod.
* @param maxHeight is the capacity or max number of Disks a rod can hold.
* @param numberOfDiscs is the initial number of Disks created on this rod.
*/
public Rod(int maxHeight, int numberOfDisks) { }
/**
* Adds one new Disk to the top of this rod.
* @param disk is a reference to the Disk being added to this rod.
* @throws IllegalStateException when this rod is already full to capacity.
*/
public void push(Disk disk) throws IllegalStateException { }
/**
* Removes and returns one Disk from the top of this rod.
* @return a reference to the Disk that is being removed.
* @throws NoSuchElementException when this rod is empty.
*/
public Disk pop() throws NoSuchElementException { return null; }
/**
* Returns (without removing) one Disk from the top of this rod.
* @return a reference to the Disk that is being returned.
* @throws NoSuchElementException when this rod is empty.
*/
public Disk peek() throws NoSuchElementException { return null; }
/**
* Indicates whether this rod is currently holding zero Disks.
* @return true when there are no Disks on this rod.
*/
public boolean isEmpty() { return false; }
/**
* Indicates whether this rod is currently full to its capacity with disks.
* @return true when the number of Disks on this rod equals its max height.
*/
public boolean isFull() { return false; }
/**
* Compares one rod to another to determine whether it's legal to move the
* top disk from this rod onto the other.
* @param other is the destination rod we are considering moving a disk to.
* @return +1 when moving a disk from this rod to other is legal,
* -1 when moving a disk from this rod to other is illegal,
* or 0 when this rod is empty and there are no disks to move.
*/
@Override
public int compareTo(Rod other) { return 0; }
/**
* The string representation of this rod includes its max height number
* of rows separated by and ending with newline characters (\n). Rows
* occupied by a disk will include that disk's string representation, and
* other rows instead contain a single vertical bar character (|). All
* rows are centered by surrounding both sides with spaces until they are
* each capacity*2+1 characters wide. Example of 5 capacity rod w\3 disks:
* " | \n" +
You may add additional private methods to help organize your implementation of these
functions, but may not add additional fields or public methods. We recommend writing some
tests to help convince yourself that this class is correctly implemented before moving on to the
next step.
THE TOWER OF HANOI
3. Add a new class called TowerOfHanoi to your project. This class makes use of your previously
implemented Disk and Rod classes, to simulate the Tower Of Hanoi puzzle. This class must
contain exactly the private field and publicly accessible constructor/methods shown in the
following:
67
68
69
70
71
72
73
74
* " | \n" +
* " <=2= \n" +
* " <==3== \n" +
* "<====5====\n"
* @return the string representation of this rod based on its contents.
*/
@Override
public String toString() { return null; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
private Rod[] rods; // rods[0] starts filled to capacity with disks
// goal is to move all disks to rods[rods.length-1]
/**
* Constructs a new TowerOfHanoi puzzle with width rods that an hold a max
* of height disks each. The first of these rods begins with this maximum
* (height) number of disks, and each of the other rods begins empty.
* @param width is the total number of rods in this puzzle.
* @param height is the number of disks that begin on the first rod.
*/
public TowerOfHanoi(int width, int height) { }

/**
* Moves a single disk from the source rod to the target rod. These rods
* are indexed using a zero-based index, where 0 references the first rod
* where all disks begin, and the width-1 references the goal rods. If
* moving a disk from this source rod to this destination rod is illegal,
* then the message "WARNING: Illegal move." should be printed out to the
* console, instead of moving any disks.
* @param source is a zero-based index for the rod to move a disk from.
* @param destination is a zero-based index for the rod that disk moves to.
*/
public void moveDisk(int source, int destination) { }
/**
* Determines whether the puzzle has been solved. This happens when the
* goal rod (index width-1) is full, and each of the other rods are empty.
* @return true when all disks have been moved from the first to last rod.
*/
public boolean isSolved() { return false; }
/**
* The string representation of this puzzle is composed of the strings
* representing each rod. However the rows of each rod must be combined
* with the rows of the other rods, so that they appear horizontally
* aligned in the final string. Here is an example from a 3x5 game:
* " | | | \n" +
You may add additional private methods to help organize your implementation of these
functions, but may not add additional fields or public methods. We recommend writing some
tests to help convince yourself that this class is correctly implemented before moving on to the
next step.
4. We are providing the following console-based interface for interacting with your TowerOfHanoi
implementation to help you further test and enjoy the code that you have written so far.
38
39
40
41
42
43
44
45
* " | | | \n" +
* " <1 | | \n" +
* " <=2= <==3== | \n" +
* "<====5==== <===4=== | \n"
* @return the string representation of this puzzle's current state.
*/
@Override
public String toString() { return null; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// Contents of Main.java:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// puzzle initialization
final int PUZZLE_HEIGHT = 5; // number of disks in the puzzle
final int PUZZLE_WIDTH = 3; // number of rods in the puzzle
final String ROD_LETTERS = "QWERTYUIOP".substring(0, PUZZLE_WIDTH); // labels for r

Scanner in = new Scanner(System.in);
TowerOfHanoi hanoi = new TowerOfHanoi(PUZZLE_WIDTH, PUZZLE_HEIGHT);
String rodLabelSpaceing = ""; // used to space ROD X labels
for(int i=0;i<PUZZLE_HEIGHT-2;i++) rodLabelSpaceing += " ";
boolean isDone = false;
String input = null;

// SAVE FOR STEP 5:
// // prompt user to see puzzle solution
// System.out.print("[P]lay Puzzle or [S]ee Solution: ");
// input = in.nextLine();
// if(input.length() 0 && input.toLowerCase().charAt(0) == 's') {
// System.out.println(hanoi.toString());
// hanoi.solve(PUZZLE_HEIGHT, 0, PUZZLE_WIDTH-1, 1);
// isDone = true;
// System.out.println("Puzzle Solved.");
// }
// allow user to play with the puzzle
while (!isDone) {
// display rod labels
System.out.println();
for(int i=0;i<ROD_LETTERS.length();i++)
System.out.print(rodLabelSpaceing + "ROD " + ROD_LETTERS.charAt(i) + rodLab
// display current state of puzzle
System.out.print("\n\n" + hanoi.toString());
// prompt player to enter their move
System.out.print("\nEnter a two letter move (source rod then destination rod),
input = in.nextLine().toLowerCase();
if (input.length() != 2) System.out.println("WARNING: A move should consist of
else if(input.equals("zz")) isDone = true;
else {
// convert input letters into rod indexes
int src = ROD_LETTERS.indexOf(input.toUpperCase().charAt(0));
int dst = ROD_LETTERS.indexOf(input.toUpperCase().charAt(1));
5. The last step of this assignment involves implementing a recursive solver for this puzzle. In
addition to the required method signature below, we are providing you with a recursive algorithm
to solve this puzzle (you may have noticed this same algorithm on the wikipedia page). In order
to test your implementation, you can uncomment the block of code labelled “SAVE FOR STEP 5”
from your Main.java file.
6. Here are a couple of traces of running this program with the provide Main driver class. This log
includes playing through a few turns of a game. And this log shows the solution generated by the
solve() method.
7. Congratulations on finishing this CS300 assignment! After verifying that your work is correct,
and written clearly in a style that is consistent with the course style guide, you should submit your
work through zybooks. The most recent of your highest scoring submissions prior to the deadline
of 17:00 on Thursday, November 16th will be used as part of your score for this assignment.
Additional grading tests will then be run against your highest scoring submission, to determine
the rest of your assignment grade.
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// move disks between those rods
if(src != -1 && dst != -1)
hanoi.moveDisk(src,dst);
else
System.out.println("WARNING: Valid rod letters include only: " + ROD_LE
// check whether the puzzle has been solved yet
if(hanoi.isSolved()) {
System.out.println("\nCongratulations, you solved the puzzle!\n");
System.out.print(hanoi.toString());
isDone = true;
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* This method automatically solves the problem of moving number disks from
* the source rod to the destination rod, by making use of an extra
* auxiliary rod.
* @param number is the number of disks being moved.
* @param source is the zero-based index of the rod disks are moved from.
* @param destination is the index of the rod that disks are moved to.
* @param auxiliary is an extra rod index that disks can be moved through.
*/
public void solve(int number, int source, int destination, int auxiliary) {
// when the number of disks to move is greater than zero
// recursively move number-1 disks from the source to auxiliary rods
// move a single disk from the source to destination rods
// display the current state of the puzzle as a result of this move
// then recursively move number-1 disks from the auxiliary to destination rods
}