Inital commitHEADmaster

5 files changed, 437 insertions, 0 deletions

diff --git a/labs/lab07_tohSolver/THComponent.java b/labs/lab07_tohSolver/THComponent.java
new file mode 100644
index 0000000..3a61dc5
--- /dev/null
+++ b/labs/lab07_tohSolver/THComponent.java
@@ -0,0 +1,113 @@
+import java.awt.Color;
+import java.awt.Graphics;
+import java.awt.Graphics2D;
+import java.awt.geom.Rectangle2D;
+import java.util.Random;
+
+import javax.swing.JComponent;
+
+@SuppressWarnings("serial")
+public class THComponent extends JComponent
+{
+	private int width;
+	private int height;
+	private int leftMargin = 10;
+	private int rightMargin = 10;
+	private int topMargin = 10;
+	private int bottomMargin = 10;
+	private int baseHeight = 10;
+	private double poleWidth = 10;
+	private TowerOfHanoi towers;
+	private int numberOfDiscs;
+	private double largestDiscSize;
+	private double smallestDiscSize = 20;
+	private double defaultReductionSize = 20.0;
+	private double defaultDiscHeight = 20.0;
+	private double[] discSizes;
+	
+	public THComponent(TowerOfHanoi aTowers)
+	{
+		towers = aTowers;
+		numberOfDiscs = towers.getNumberOfDiscs();
+		discSizes = new double[numberOfDiscs];
+	}
+	
+	public void paintComponent(Graphics g)
+	{
+		Graphics2D g2 = (Graphics2D) g;
+		
+		width = this.getWidth();
+		height = this.getHeight();
+
+		int drawingWidth = width - (leftMargin + rightMargin);
+		int drawingHeight = height - (topMargin + bottomMargin);
+
+		// draw the base;
+		
+		Rectangle2D.Double rect = new Rectangle2D.Double(leftMargin , height - (bottomMargin + baseHeight), drawingWidth, baseHeight);
+		g2.draw(rect);
+		
+		// draw poles;
+		
+		double halfDistance = ((double) drawingWidth / 6);
+		largestDiscSize = (halfDistance * 2) - poleWidth;
+		
+		for(int i = 1; i <= 5; i = i + 2)
+		{
+			rect.setRect((leftMargin + (halfDistance * i)) - (poleWidth / 2), topMargin, poleWidth, drawingHeight - baseHeight);
+			g2.draw(rect);
+		}
+		
+		// draw discs
+		
+		double totalReduction = (largestDiscSize - smallestDiscSize) / (numberOfDiscs - 1);
+		double actualReduction;
+		
+		if(totalReduction > defaultReductionSize)
+		{
+			actualReduction = defaultReductionSize;
+		}
+		else
+		{
+			actualReduction = totalReduction;
+		}
+		
+		double totalHeight = drawingHeight - baseHeight;
+		double tempDiscHeight = totalHeight / (numberOfDiscs + 1);
+		double actualDiscHeight;
+		
+		if(tempDiscHeight > defaultDiscHeight)
+		{
+			actualDiscHeight = defaultDiscHeight;
+		}
+		else
+		{
+			actualDiscHeight = tempDiscHeight;
+		}
+		
+		for(int i = 0; i < numberOfDiscs; i++)
+		{
+			discSizes[i] = largestDiscSize - (actualReduction * ((numberOfDiscs - 1) - i));
+		}
+		
+		int[][] t = new int[3][];
+		for(int i = 0; i < 3; i++)
+		{
+			t[i] = towers.getArrayOfDiscs(i);
+		}
+			
+		for(int i = 0; i <= 2; i++)
+		{
+			for(int j = 0; j < t[i].length; j++)
+			{
+				double x = (leftMargin + (halfDistance * (1 + (2 * i)))) - (discSizes[t[i][j]] / 2);
+				double y = ((topMargin + drawingHeight) - baseHeight) - (actualDiscHeight * (j + 1));
+				rect.setRect(x,y,discSizes[t[i][j]],actualDiscHeight);
+				g2.setColor(Color.GREEN);
+				g2.fill(rect);
+				g2.setColor(Color.BLACK);
+				g2.draw(rect);
+			}
+		}
+	}
+}
diff --git a/labs/lab07_tohSolver/THFrame.java b/labs/lab07_tohSolver/THFrame.java
new file mode 100644
index 0000000..0c672e2
--- /dev/null
+++ b/labs/lab07_tohSolver/THFrame.java
@@ -0,0 +1,84 @@
+import javax.swing.JFrame;
+
+public class THFrame
+{
+	public static void main(String[] args) throws InterruptedException
+	{
+		int numDiscs = 4;
+		TowerOfHanoi towers = new TowerOfHanoi(numDiscs);
+		THComponent thc = new THComponent(towers);
+		
+		
+		JFrame frame = new JFrame();
+		frame.setTitle("Tower of Hanoi");
+		frame.setSize(500,500);
+		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
+		
+		frame.add(thc);
+		
+		frame.setVisible(true);
+		
+		Thread.sleep(5000);
+		
+		towers.moveTopDisc(0, 1);
+		thc.repaint();
+		Thread.sleep(500);
+
+		towers.moveTopDisc(0, 2);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(1, 2);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(0, 1);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(2, 0);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(2, 1);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(0, 1);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(0, 2);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(1, 2);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(1, 0);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(2, 0);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(1, 2);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(0, 1);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(0, 2);
+		thc.repaint();
+		Thread.sleep(500);
+		
+		towers.moveTopDisc(1, 2);
+		thc.repaint();
+		Thread.sleep(500);
+		
+	}
+}
diff --git a/labs/lab07_tohSolver/THSolverFrame.java b/labs/lab07_tohSolver/THSolverFrame.java
new file mode 100644
index 0000000..53a15bb
--- /dev/null
+++ b/labs/lab07_tohSolver/THSolverFrame.java
@@ -0,0 +1,70 @@
+/*Alexander Pickering
+ *Data Structures Mon. Wed. @ 09:30
+ *Lab 7 
+ */
+import javax.swing.JFrame;
+
+public class THSolverFrame
+{
+	public static void main(String[] args) throws InterruptedException
+	{
+		int numberOfDiscs = 10;
+		TowerOfHanoi towers = new TowerOfHanoi(numberOfDiscs);
+		THComponent thc = new THComponent(towers);
+		
+		
+		JFrame frame = new JFrame();
+		frame.setTitle("Tower of Hanoi");
+		frame.setSize(500,500);
+		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
+		
+		frame.add(thc);
+		
+		frame.setVisible(true);
+		
+		//Thread.sleep(5000);
+		
+		solveTower(towers, thc,numberOfDiscs);
+		
+		System.out.println("DONE!!!");
+	}
+	
+	public static void solveTower(TowerOfHanoi towers, THComponent thc, int numPlates) throws InterruptedException
+	{
+		movePlateAndUp(towers,0,numPlates,2,thc);
+	}
+	private static void movePlateAndUp(TowerOfHanoi towers, int towerfrom, int depth, int towerto, THComponent thc) throws InterruptedException
+	{
+		if(depth == 1)
+		{
+			//We are the top block
+			towers.moveTopDisc(towerfrom,towerto);
+			animate(thc);
+		}
+		else
+		{
+			//Find a tower to put everything on top of
+			int unusedTower = 0;
+			if(towerfrom == 0 || towerto == 0)
+			{
+				unusedTower = 1;
+				if(towerfrom == 1 || towerto == 1)
+				{
+					unusedTower = 2;
+				}
+			}
+			//Move everything on top of what we want to move somewhere else
+			movePlateAndUp(towers,towerfrom,depth-1,unusedTower,thc);
+			//Move us
+			towers.moveTopDisc(towerfrom,towerto);
+			animate(thc);
+			//Move everything that was on top of use back on top of us
+			movePlateAndUp(towers,unusedTower,depth-1,towerto,thc);
+		}
+	}
+	private static void animate(THComponent thc) throws InterruptedException
+	{
+		thc.repaint();
+		Thread.sleep(50);
+	}
+}
diff --git a/labs/lab07_tohSolver/TowerOfHanoi.java b/labs/lab07_tohSolver/TowerOfHanoi.java
new file mode 100644
index 0000000..76b673d
--- /dev/null
+++ b/labs/lab07_tohSolver/TowerOfHanoi.java
@@ -0,0 +1,170 @@
+
+public class TowerOfHanoi
+{
+	// TO DO: Instance Variables
+	private HStack towers[] = new HStack[3];
+	private int numDiscs;
+	/* Construct the Towers of Hanoi (3 towers) with aNumDisc
+	 * on the first tower. Each tower can be identified by an
+	 * integer number (0 for the first tower, 1 for the second
+	 * tower, and 2 for the third tower). Each disc can be identified
+	 * by an integer number starting from 0 (for the smallest disc)
+	 * and (aNumDisc - 1) for the largest disc.
+	 */
+	public TowerOfHanoi(int aNumDiscs)
+	{
+		towers[0] = new HStack();
+		towers[1] = new HStack();
+		towers[2] = new HStack();
+		for(int i = 1; i <= aNumDiscs; i++)
+		{
+			towers[0].push(aNumDiscs-i);
+		}
+		numDiscs = aNumDiscs;
+	}
+	
+	/* Returns an array of integer representing the order of
+	 * discs on the tower (from bottom up). The bottom disc should
+	 * be the first element in the array and the top disc should be
+	 * the last element of the array. The size of the array MUST
+	 * be the number of discs on the tower. For example, suppose
+	 * the tower 0 contains the following discs 0,1,4,6,7,8 (from top
+	 * to bottom). This method should return the array [8,7,6,4,1,0]
+	 * (from first to last). 
+	 * @param tower the integer identify the tower number.
+	 * @return an array of integer representing the order of discs.
+	 */
+	public int[] getArrayOfDiscs(int tower)
+	{
+		return towers[tower].toArray();
+	}
+	
+	/* Gets the total number of discs in this Towers of Hanoi
+	 * @return the total number of discs in this Towers of Hanoi
+	 */
+	public int getNumberOfDiscs()
+	{
+		// TO DO
+		return numDiscs;
+	}
+	
+	/* Gets the number of discs on a tower.
+	 * @param tower the tower identifier (0, 1, or 2)
+	 * @return the number of discs on the tower.
+	 */
+	public int getNumberOfDiscs(int tower)
+	{
+		return towers[tower].getLength();
+	}
+	
+	/* Moves the top disc from fromTower to toTower. Note that
+	 * this operation has to follow the rule of the Tower of Hanoi
+	 * puzzle. First fromTower must have at least one disc and second
+	 * the top disc of toTower must not be smaller than the top disc
+	 * of the fromTower.
+	 * @param fromTower the source tower
+	 * @param toTower the destination tower
+	 * @return ture if successfully move the top disc from
+	 *         fromTower to toTower.
+	 */
+	public boolean moveTopDisc(int fromTower, int toTower)
+	{
+		if(towers[fromTower].getLength() == 0)
+		{
+			return false;
+		}
+		if(towers[toTower].getLength() == 0)
+		{
+			towers[toTower].push(towers[fromTower].pop());
+			return true;
+		}
+		else if(towers[fromTower].peek() < towers[toTower].peek())
+		{
+			towers[toTower].push(towers[fromTower].pop());
+			return true;
+		}
+		else
+		{
+			return false;
+		}
+	}
+
+	public String toString()
+	{
+		String s = "[" + towers[0].toString() + "," + towers[1].toString() + "," + towers[2].toString() + "]";
+		return s;
+	}
+
+	public class HStack
+	{
+		private HNode head;
+		private int length;
+		public HStack()
+		{
+			length = 0;
+		}
+		public int peek()
+		{
+			return head.getData();
+		}
+		public int pop()
+		{
+			int output = head.getData();
+			head = head.getNext();
+			length--;
+			return output;
+		}
+		public void push(int i)
+		{
+			head = new HNode(i,head);
+			length++;
+		}
+		public boolean hasNext()
+		{
+			return head != null;
+		}
+		public int getLength()
+		{
+			return length;
+		}
+		public String toString()
+		{
+			String output = "";
+			for(HNode tmp = head; tmp != null; tmp=tmp.getNext())
+			{
+				output += tmp.getData() + " ";
+			}
+			return output;
+		}
+		public int[] toArray()
+		{
+			int[] output = new int[length];
+			int i = length-1;
+			for(HNode tmp = head; tmp != null; tmp = tmp.getNext())
+			{
+				output[i] = tmp.getData();
+				i--;
+			}
+			return output;
+		}
+
+	}
+	public class HNode
+	{
+		private HNode next = null;
+		private int data;
+		public HNode(int d, HNode n)
+		{
+			data = d;
+			next = n;
+		}
+		public int getData()
+		{
+			return data;
+		}
+		public HNode getNext()
+		{
+			return next;
+		}
+	}
+}
diff --git a/labs/lab07_tohSolver/lab07_solveTower.pdf b/labs/lab07_tohSolver/lab07_solveTower.pdf
new file mode 100644
index 0000000..c8d02f9
--- /dev/null
+++ b/labs/lab07_tohSolver/lab07_solveTower.pdf