Towers of Hanoi

Objectives

Create a last-in-first-out (LIFO) data structure.

Write a program that will solve the Towers of Hanoi.

Solve the problem using both recursion and iteration.

Use stack data structures more extensively.

Getting Started

Create a new Java project called P5 and import TowersOfHanoi-starter.jar.

---> https://www.cs.colostate.edu/~cs165/.Spring18/assignments/P5/archive/TowersOfHanoi-starter.jar

Your directory should look like this:

P5/  resources   Towers.jpg  src  MyStack.java  MyStackTestProgram.java  UserInterface.java  TowersOfHanoi.java  StdDraw.java 

Description

There are two parts to this assignment.

The first part is gaining a better understanding of how stacks work.

The second part is to understand how to implement the Towers of Hanoi algorithm.

Part One - Building a Stack

You will be using a generic ArrayList to create a stack and using the MyStackTestProgram class to test your implementation. The last index of the ArrayList is the top of the stack.

NOTE	You may use any method in ArrayList except contains, indexOf, and lastIndexOf.

Open the MyStack class.

Declare a private field of type ArrayList

Implement each method using the javadoc.https://www.cs.colostate.edu/~cs165/.Spring18/assignments/P5/doc/javadoc/MyStack.html

Start by implementing the toString() method since all of the tests in the MyStackTestProgram class depend on this method being correct.

Remember to incrementally develop. Test one method at a time.

WARNING

Your implementation of MyStack.java MUST pass all testing in order to use it for this assignment.

Part Two - Implementing Towers of Hanoi

Add code to the main method to initialize the puzzle by pushing all the discs onto the left stack, in descending order. Run the program with the command line arguments "10 -recursive" and you should see the picture shown below.

Use the specifications in the javadoc to implement the recursive method.

https://www.cs.colostate.edu/~cs165/.Spring18/assignments/P5/doc/javadoc/TowersOfHanoi.html#recursiveHanoi-int-int-int-int-

Use the specifications in the javadoc to implement the Move class.

https://www.cs.colostate.edu/~cs165/.Spring18/assignments/P5/doc/javadoc/TowersOfHanoi.Move.html

Use the specifications in the javadoc to implement the iterative version

https://www.cs.colostate.edu/~cs165/.Spring18/assignments/P5/doc/javadoc/TowersOfHanoi.html#iterativeHanoi-int-int-int-int-

import java.util.ArrayList;

import java.util.EmptyStackException;

/**

* The MyStack class represents a last-in-first-out (LIFO) stack of objects.

* MyStack uses a generic ArrayList. Your stack should work exactly like java.util.Stack,

* except that you only have to implement a subset of the methods, as shown below.

* @param the type of elements in this list

*/

public class MyStack {

private ArrayList items;

public MyStack() {

items = new ArrayList<>();

}

/**

* Pushes item onto the top of this stack

* @param item the item to be pushed onto this stack

* @return the item argument

*/

public E push(E item) {

items.add(item);

return item;

}

/**

* Removes the object at the top of this stack and returns that object as the value of this function.

* @return The object at the top of this stack (the last item)

* @throws EmptyStackException if stack is empty when called

*/

public E pop() {

return items.remove(items.size() - 1);

}

/**

* Looks at the object at the top of this stack without removing it from the stack.

* @return the object at the top of this stack (the last item)

* @throws EmptyStackException if stack is empty when called

*/

public E peek() {

return items.get(items.size() - 1);

}

/**

* Test if Stack is empty

* @return true if and only if this stack contains no items; false otherwise.

*/

public boolean isEmpty() {

return items.isEmpty();

}

/**

* Returns the number of items in the stack

* @return size of the stack

*/

public int size() {

return items.size();

}

/**

* Removes all the elements from the Stack. The Stack will be empty after this call

* (unless an exception occurs)

*/

public void clear() {

items.clear();

}

/**

* Returns the 1-based position where an object is on this stack.

* If the object o occurs as an item in this stack, this method

* returns the distance from the top of the stack of the occurrence

* nearest the top of the stack; the topmost item on the stack is

* considered to be at distance 1. The equals method is used to

* compare o to the items in this stack.

*

* Example:

*

 
* s.push(4);
 
* s.push(5);
 
* s.push(6);
 
* s.search(6); // 1
 
* s.search(5); // 2
 
* s.search(4); // 3
 
* s.search(27) // -1
 
* 

* @param o the desired object.

* @return the 1-based position from the top of the stack where the object is located;

* the return value -1 indicates that the object is not on the stack.

*/

public int search(Object o) {

int p = -1;

for (int i = items.size() - 1; i >= 0; i--) {

if (items.get(i).equals(o)) {

p++;

break;

}

p++;

}

return p;

}

/**

* Returns true if this stack contains the specified element.

* More formally, returns true if and only if this stack contains

* at least one element e such that (o==null ? e==null : o.equals(e)).

* @param o element whose presence in this ArrayList is to be tested

* @return true if this ArrayList contains the specified element

*/

public boolean contains(Object o) {

return false;

}

/**

* Returns the index of the first occurrence of the specified element in this stack,

* or -1 if this ArrayList does not contain the element. This is the index in the

* underlying ArrayList, NOT the position in the stack as defined in the search

* function. More formally, returns the lowest index i such that (o==null ?

* get(i)==null : o.equals(get(i))), or -1 if there is no such index.

* @param o element to search for

* @return the index of the first occurrence of the specified element in this ArrayList,

* or -1 if this ArrayList does not contain the element

*/

public int indexOf(Object o) {

return 0;

}

/**

* Returns the index of the last occurrence of the specified element in this stack,

* or -1 if this ArrayList does not contain the element. This is the index in the

* underlying ArrayList, NOT the position in the stack as defined in the search

* function. More formally, returns the highest index i such that (o==null ?

* get(i)==null : o.equals(get(i))), or -1 if there is no such index.

* @param o element to search for

* @return the index of the last occurrence of the specified element in this stack

*/

public int lastIndexOf(Object o) {

return 0;

}

/**

* String representation of a stack.

* Format is the same as {@link ArrayList#toString()} and

* the order is from bottom of the stack to the stop.

* @return string representation of a stack

*/

@Override

public String toString(){

StringBuilder b = new StringBuilder();

b.append("[");

for (E e : items) {

b.append(e);

if (items.iterator().hasNext()) {

b.append(",");

}

}

b.append("]");

return b.toString();

}

/**

* Returns the element at the specified position in this list.

* @param index index of the element to return. This is the index in the

* underlying ArrayList, NOT the position in the stack as defined in the search

* function.

* @return the element at the specified position in this list

* @throws IndexOutOfBoundsException if the index is out of range (index < 0 || index >= size())

*/

public E get(int index) {

return items.get(index);

}

}

-----------------------------------------------------------------------------------------------------------------

// TowersOfHanoi.java - solver program for Tower of Hanoi

// Author: ?????

// Date: ?????

// Class: CS165

// Email: ?????

/**

* ACKNOWLEDGEMENTS:

* This assignment was heavily copied from the wonderfully competent faculty at Princeton University.

* Permission to use the assignment was granted via email by Dr. Robert Sedgewick. We gratefully

* acknowledge the material from Princeton University used in this assignment! The original Princeton

* assignment is here: http://introcs.cs.princeton.edu/java/23recursion/AnimatedHanoi.java.html

* Copyright © 20002011, Robert Sedgewick and Kevin Wayne.

*/

public class TowersOfHanoi {

/**

* The user interface

*/

private static UserInterface ui;

/**

* The left tower, maps to the 0

*/

private static MyStack left = new MyStack<>();

/**

* The center tower, maps to 1

*/

private static MyStack center = new MyStack<>();

/**

* The right tower, maps to 2

*/

private static MyStack right = new MyStack<>();

/**

* Stack used for the iterative solution

*/

private static MyStack moves = new MyStack();

/**

* The Move class represents the action of moving one disc between pegs.

* Of course, if that disc is covered by other discs, you'll first have

* to move them off. And after the original disc is moved over, you'll

* want to put the other discs back on top.

*

* You will need the following fields:

*

*

1. A field to hold the disc number

   *

2. Three fields for the to/from/auxiliary pole numbers

   *

3. A field to tell you whether the disc is covered by smaller discs

   *

*

* The last field doesn't have a direct analog to the recursive implementation.

* However, before the first recursive call the disc in question was covered by

* a tower of smaller discs. After that recursive call returns, the disc

* is uncovered and can be moved. Then the second recursive call moved the smaller

* discs back on top of it.

*

* In the recursive version, the runtime stack keeps track of where in the method to

* jump back to when the recursive call returned, this effectively keeps a bit of state

* about how far along the computation is.

*

* In the iterative version, we have to store this information explicitly in the object:

* is the disc covered (and will require work before it can be moved) or is it now

* uncovered (and ready to be moved before finally moving the smaller discs back

* on top).

*/

public static class Move {

// YOUR CODE HERE: variables, constructor, and toString

}

public static void main(String[] args) throws InterruptedException {

if (args.length != 2) {

System.err.println("usage1: java TowersofHanoi depth <-recursive>");

System.err.println("usage2: java TowersofHanoi depth <-iterative>");

System.exit(-1);

}

// Parse tower depth

int depth = Integer.parseInt(args[0]);

// Parse options

String option = args[1];

// Setup initial state

// your code here: push discs onto left pole in inverted order

// Create user interface

ui = new UserInterface(depth);

// Call user interface to render (initial)

ui.draw(left, center, right);

// Solve Towers of Hanoi

if (option.equals("-recursive"))

recursiveHanoi(depth, 0, 1, 2);

else

iterativeHanoi(depth, 0, 1, 2);

// Wait for awhile

Thread.sleep(10000);

// Destroy user interface

System.exit(0);

}

/**

* The recursive solution for Towers of Hanoi.

* Implement the recursive solver for Towers of Hanoi, as follows:

*

*

1. The base case for the recursion is to return if asked to move disc 0.

   *

2. Make a recursive call to move the stack above the current disc from the source to the auxiliary pole.

   * For example, if the current disk is 5, you would want to recurse with disk 4 and the appropriate

   * arguments.

   *

3. Now the discs above are out of the way, {@link TowersOfHanoi#move(int, int, int)}

   * the requested disc to the destination pole.

   *

4. Make a recursive call to move the stack on the auxiliary pole back to the destination pole.

   *

* Verify that your solution works by running the program using the recursive option.

* @param disc the disc you are moving to the destination (auxiliary) pole.

* @param from the pole that the disk is currently on

* @param aux the auxiliary pole (provides supplementary or additional help) but won't be used to move this disk

* at this point of time.

* @param to the pole that the disk will move to

*/

public static void recursiveHanoi(int disc, int from, int aux, int to) {

if (disc == 1) {

System.out.println(from + "->" + to);

}

else {

recursiveHanoi(disc - 1, from, to, aux);

System.out.println(from + "->" + to);

recursiveHanoi(disc - 1, aux, from, to);

}

}

/**

* Iterative solution using stack.

*

*

1. Create a Move object using the arguments to iterativeHanoi() and push it onto

   * the MyStack field named "moves". Initially, this bottom disc is covered of

   * course. This represents the initial request to move the bottom disc.

   *

2. Enter a loop that processes moves from the stack until the stack is empty.

   * Within the loop:

   *

   *

   • pop a Move object from the top of the stack.

     *

   • If the requested move is for disc 0, just continue the loop (no work is required).

     *

   • If moving a currently covered disc:

     *

     *

     1. Push the Move object back onto the stack after marking it uncovered.

        * By the time we see it again, it will be uncovered.

        *

     2. Push a new Move object requesting that the disc covering it is moved

        * out of the way (onto the auxiliary). This is the analog of the first

        * recursive call in the recursive version.

        *

     *

   • If moving an uncovered disc:

     *

     *

     1. Perform the actual move of the disc by calling the move method

        * (since it is uncovered, it is free to be moved now).

        *

     2. Push a new Move object requesting that the disc that was previously

        * moved off onto the auxiliary be moved from there back on top of the

        * just-moved disc. This is analogous to the second recursive call.

        *

     *

   • If you continue until the stack is empty, this will solve the puzzle,

     * effectively tracing the same steps as the recursive version, modeling the

     * state of the algorithm with an explicit stack, rather than the runtime stack.

     *

   *

*

* @param disc the current disc

* @param from what pole the disc is on

* @param aux the auxiliary pole

* @param to what pole the disc is being moved to

*/

public static void iterativeHanoi(int disc, int from, int aux, int to) {

// your code here

}

/**

* Method to report and move a disc.

* @param disc the current disc

* @param source the pole the disc is on

* @param dest the pole the disc is being moved to

*/

static void move(int disc, int source, int dest) {

MyStack fromStack, toStack;

String fromName, toName;

// Translate integer to stacks and names

switch (source) {

case 0: fromStack = left; fromName = "left"; break;

case 1: fromStack = center; fromName = "center"; break;

default: fromStack = right; fromName = "right"; break;

}

switch (dest) {

case 0: toStack = left; toName = "left"; break;

case 1: toStack = center; toName = "center"; break;

default: toStack = right; toName = "right"; break;

}

// Print the move

System.err.println("Moved disc " + disc + " from " + fromName + " to " + toName + ".");

// Perform the move

toStack.push(fromStack.pop());

// Call user interface to render (updated)

ui.draw(left, center, right);

}

}

-----------------------------------------------------------------------------------------------------------------

// UserInterface.java - user interface for Tower of Hanoi

import java.awt.Color; import java.awt.Font;

/** * Draws the Tower of Hanoi puzzle with poles and discs. */ public class UserInterface {

/** * Tower depth */ private static int depth;

/** * Create user interface * @param depth */ public UserInterface(int depth) {

// Store depth UserInterface.depth = depth; // Setup drawing canvas int WIDTH = 200; int HEIGHT = 20; StdDraw.setCanvasSize(3*WIDTH, 250+6*HEIGHT); StdDraw.setXscale(0, 4); StdDraw.setYscale(-3, 12); StdDraw.enableDoubleBuffering(); StdDraw.pause(1000); }

/** * a method that draws the current state of each pole. * @param left the left pole * @param middle the middle pole * @param right the right pole */ void draw(MyStack left, MyStack middle, MyStack right) {

// Clear screen and setup colors StdDraw.clear(); StdDraw.picture(2, 1, "resources/Towers.jpg");

// Draw puzzle for (int tower = 0; tower < 3; tower++) {

// Select tower MyStack discs = null; switch (tower) { case 0: discs = left; break; case 1: discs = middle; break; case 2: discs = right; break; } // Draw discs for (int disc = 0; disc < discs.size(); disc++) { // Disc number int number = discs.get(disc);

// Setup pen Color color = Color.getHSBColor(1.0f * number / depth, 0.7f, 0.7f); StdDraw.setPenColor(color); StdDraw.setPenRadius(0.035); // magic constant

// Draw disc double size = 0.5 * number / depth; // Compute position of towers and discs double y = (disc - 1.75) * 0.75; double x = 0.0; switch (tower) { case 0: x = 0.665; break; case 1: x = 1.970; break; case 2: x = 3.235; break; } StdDraw.setPenRadius(0.035); // magic constant StdDraw.line(x - size / 2.0, y, x + size / 2.0, y); StdDraw.setPenColor(Color.WHITE); StdDraw.setFont(new Font("TimesRoman", Font.BOLD, 20)); StdDraw.text(x, y-0.1, Integer.toString(number)); } }

StdDraw.show(); StdDraw.pause(500); }

}