Description
This Assignment involves developing a Tower of Hanoi pule that makes use of an arraybased stack implementation. You will also implement a solver for this pule 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 implementing a recursive solution to the Tower of Hanoi pule.
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 ava proect in Eclipse. You can name this proect whatever you like, but TowerOfHanoi is a descriptive choice. f you are not familiar with the Tower of Hanoi pule,
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 ComparableDisk interface. Obects of this type will be used to represent the disks in this pule. This class must contain eactly the private field and publicly accessible constructormethods shown in the following:
You may add additional private methods to help organie your implementation of these functions, but may not add additional fields or public methods. e recommend writing some tests to help convince yourself that this class is correctly implemented before moving on to the net step.
THE ROD
2. As described in the wikipedia page, the Tower of Hanoi pule makes use of three rods. Add a new class called od which implement the Comparableod interface to your proect. This od class will implement many of the common StackADT operations, and will make use of a array based stack implementation as discussed in lecture. This class must contain eactly the private fields and publicly accessible constructormethods 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 private int 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 public Disk(int 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 public int int compareTo(Disk other) { return 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 public String String toString() { return return null null; }
1 private private int 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 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 public Rod(int int maxHeight, int 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 public void 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 public Disk pop() throws NoSuchElementException { return return null 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 public Disk peek() throws NoSuchElementException { return return null null; } /** * Indicates whether this rod is currently holding zero Disks. * @return true when there are no Disks on this rod. */ public public boolean boolean isEmpty() { return return false 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 public boolean boolean isFull() { return return false 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 public int int compareTo(Rod other) { return 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 organie your implementation of these functions, but may not add additional fields or public methods. e recommend writing some tests to help convince yourself that this class is correctly implemented before moving on to the net step.
THE TOWER OF HANOI
. Add a new class called TowerOfHanoi to your proect. This class makes use of your previously implemented Disk and od classes, to simulate the Tower Of Hanoi pule. This class must contain eactly the private field and publicly accessible constructormethods 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 public String String toString() { return return null 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 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 public TowerOfHanoi(int int width, int 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 public void void moveDisk(int int source, int 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 public boolean boolean isSolved() { return return false 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 3×5 game: * ” | | | \n” +
You may add additional private methods to help organie your implementation of these functions, but may not add additional fields or public methods. e recommend writing some tests to help convince yourself that this class is correctly implemented before moving on to the net step. . e are providing the following consolebased interface for interacting with your TowerOfHanoi implementation to help you further test and enoy 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 public String String toString() { return return null 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 public class class Main { public public static static void void main(String String[] args) { // puzzle initialization final final int int PUZZLE_HEIGHT = 5; // number of disks in the puzzle final final int int PUZZLE_WIDTH = 3; // number of rods in the puzzle final final String String ROD_LETTERS = “QWERTYUIOP”.substring(0, PUZZLE_WIDTH); // labels for r Scanner in in = new new Scanner(System.in in); TowerOfHanoi hanoi = new new TowerOfHanoi(PUZZLE_WIDTH, PUZZLE_HEIGHT); String String rodLabelSpaceing = “”; // used to space ROD X labels for for(int int i=0;i<PUZZLE_HEIGHT-2;i++) rodLabelSpaceing += ” “; boolean boolean isDone = false false; String String input = null 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 while (!isDone) { // display rod labels System.out.println(); for for(int 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 in.nextLine().toLowerCase(); if if (input.length() != 2) System.out.println(“WARNING: A move should consist of else else if if(input.equals(“zz”)) isDone = true true; else else { // convert input letters into rod indexes int int src = ROD_LETTERS.indexOf(input.toUpperCase().charAt(0)); int int dst = ROD_LETTERS.indexOf(input.toUpperCase().charAt(1));
. The last step of this assignment involves implementing a recursive solver for this pule. n addition to the required method signature below, we are providing you with a recursive algorithm to solve this pule you may have noticed this same algorithm on the wikipedia page. n order to test your implementation, you can uncomment the block of code labelled SAE FO STEP from your Main.ava 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 CS00 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 ybooks. 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