(JAVA - DATA STRUCTURES) PLEASE, DO NOT AVOID MY QUESTION. THIS IS THE THIRD TIME I POST THIS QUESTION AND NOBODY WANTS TO HELP ME.

The code that you write for this assignment will build on top of two ADTs (List and Stack) and their implementations. Recall that the way Java has dealt with Stacks is rather odd: Stack is a class, rather than an interface, and the documentation recommends that you use a Deque instead. Rather than using Java's built in Stack methods, I've provided you with a Stack interface (Stack.java) and an implementation of a Stack (MysteryStackImplementation.class). The implementation of stack is just a class file, because you don't need to see how it is implemented in order to use it. For this assignment, you must use the Stack interface and implementation that I have providedyou may not use the built in Java Stack or Deque.

Maze.java

https://media.cheggcdn.com/media/4fa/4fafd055-dcfc-4753-ae59-510e00c06158/phpJguJLx (Can I post this? Is it a third party link?)

MazeSquare.java

/** * MazeSquare represents a single square within a Maze. * @author Anna Rafferty */ public class MazeSquare { //Wall variables private boolean hasTopWall = false; private boolean hasRightWall = false; //Location of this square in a larger maze. private int row; private int col; /** * Constructs a new maze square with walls as configured by * descriptor (7 = top and right, | is just right, _ is just * top, and * is neither top nor right) and located at the * given row and column. */ public MazeSquare(char descriptor, int row, int col) { this.row = row; this.col = col; if(descriptor == '7') { hasTopWall = true; hasRightWall = true; } else if(descriptor == '|') { hasTopWall = false; hasRightWall = true; } else if(descriptor == '_') { hasTopWall = true; hasRightWall = false; } else if(descriptor == '*') { hasTopWall = false; hasRightWall = false; } else { hasTopWall = false; hasRightWall = false; System.err.println("Unrecognized character for MazeSquare description: " + descriptor); } } /** * Returns true if this square has a top wall. */ public boolean hasTopWall() { return hasTopWall; } /** * Returns true if this square has a right wall. */ public boolean hasRightWall() { return hasRightWall; } /** * Returns the row this square is in. */ public int getRow() { return row; } /** * Returns the column this square is in. */ public int getColumn() { return col; } /** * Returns true if c is a valid identifier for a maze square */ public static boolean isAllowedCharacter(char c) { return c=='*' || c=='_' || c=='|' || c=='7'; } }

Stack.java

/** * An interface for the Stack ADT, adapted from Frank Carrano. * @author Jadrian Miles * @author Anna Rafferty */ public interface Stack { /** * Adds an item to the top of this stack. * @param item The item to add. */ public void push(T item); /** * Removes and returns the item from the top of this stack. * @return the item at the top of the stack. Throws an empty * stack exception if empty. */ public T pop(); /** * Returns the item on top of the stack, without removing it. * @return the item at the top of the stack. Throws an empty * stack exception if empty. */ public T peek(); /** * Returns whether the stack is empty. * @return true if the stack is empty; false otherwise */ public boolean isEmpty(); /** * Removes all items from the stack. */ public void clear(); }

REQUIREMENTS

• Correct command-line syntax and behavior (two different possible usages)
• load method returns true and false based on whether the maze file is properly formatted, and after load is called, the squares of the maze are stored in some way
• getSolution returns a stack of maze squares containing a solution (or an empty stack if no solution is possible

Part I: Understanding the Maze File Format Mazes are stored in text files and follow a particular format. We assume that our mazes are rectangular, and that they have walls along the entire outside of the maze, with no gaps in these outer walls. We will also specify a "start square" (S) and a "finish square" (F) to indicate the goal of the maze-solverto get from S to F. Maze files should have the following structure (both column numbers and row numbers start with O): Each row description includes a single character for each square in that row, and each character describes the right and top walls for its square. Specifically, there are four kinds of descriptors: 7 means that the square has both a top wall and a right wall (vertical bar or pipe) means that the square has a right wall, but no top wall _(underscore) means that the square has a top wall, but no right wall . * (asterisk) means that the square has neither a top wall nor a right wall Putting this together in a small example, if the input file contains the following (see maze.txt in the starter folder): Lines in file Interpretation 32 The maze has 3 columns and 2 rows 11 The start square is in the bottom middle. 20 The finish square is in the upper right. 7 (0,0) has a top wall; (0,1) has a top wall; (0,2) has a top and right wall *_7 (1,0) has neither top or right walls; (1,1) has a top wall; (1,2) has a top and right wall then the resulting maze would be printed as follows: 1 F 1 1 S Note that we specify only the top and right walls for each square, and not the bottom and left walls. This is sufficient to describe the whole mazemake sure to understand why this is. Part II: Loading and Printing the Maze The first step of the assignment is to finish the load method in Maze . Read through what's in Maze and MazeSquare in order to understand how the current code is organized. Decide how you'll be storing the squares of the maze. Modify Maze to include one or more) instance variable for storing the squares, and finish the load method. I recommend storing the squares as a list of MazeSquare s. The load method should return false if there are any squares that don't have *, 7, _, or as a descriptor, or the number of squares is inconsistent with the number of rows and columns specified at the beginning of the file. Don't forget to modify the constructor too (think that for each of the instance variable, what value makes sense for an empty maze). Complete the method getMazeSquare . A "stub" for this method is already provided in the Maze file (line 212). Now, you're ready to try out whether your methods function correctly. You'll be loading and printing a maze. Modify main so that with the following command line: java Maze maze.txt the file maze.txt is loaded and printed. At this point, the main should just involve constructing the maze and calling the load and print methodsit requires very little code. (Look in Maze for a print methodthis method will work correctly once you have a working getMaze Square .) Don't forget to compile before you run it. Before you move on, draw a maze on paper, and then make a maze file that represents that maze. Try loading the maze and printing it using the following command: java Maze where is replaced with the name of your maze file (put your maze file in the same folder). Part III: Solving the Maze Now it's time to solve the maze using the following algorithm. I'm giving you the steps; your job is to turn them into code: 1. Mark every square in the maze as unvisited. 2. Create an empty stack of maze squares. 3. Add the start square to the stack, and mark the start square as visited. 4. If the stack is empty, you're done and the maze is unsolvable. 5. If the top item is the finish square, you're done and the stack contains a solution to the maze. 6. If all squares adjacent to the top item (i.e. the squares up, down, right, or left from the top item-no diagonal adjacency) are either blocked by a wall or are marked visited already, remove the top item from the stack and go to step 4. 7. Otherwise, select a square that is adjacent to the top of the stack, unvisited, and accessible from the top of the stack (no wall between them). Mark this square as visited and push it on the stack. Go to step 4. You should implement this method in Maze . Specifically: Your Maze class must include a method with the following behavior and signature: 1 2 3 /** * Computes and returns a solution to this maze. If there are multiple * solutions, only one is returned, and get Solution makes no guarantees about * which one. However, the returned solution will not include visits to dead * ends or any backtracks, even if backtracking occurs during the solution * process. 4 5 6 7 8 9 10 11 * @return a stack of MazeSquare objects containing the sequence of squares * visited to go from the start square (bottom of the stack) to the finish square (top of the stack). If there is no solution, an empty stack is * returned. */ public Stack [--solve] For example, given the included maze. txt maze file, java Maze maze. txt on the command line should print the maze with no solution: F S However, java Maze maze.txt --solve should print the maze with the path of a solution marked: F Thus, you'll need to decide how to print a maze solution with the solution marked. Try to avoid duplicating code as much as possiblecan you modify the existing print method so that it can print a maze with or without a solution? If you modify print , make sure that the comment reflects what print now does. (Warning: your getsolution method shouldn't worry about displaying the solution thus shouldn't contain any printing statements, its purpose should be solely to get the solution as a stack and then return it.) Hint: You can add two parameters in the existing print : the first one can be a boolean indicating whether or not you'd like to print the solution; the second one is the Stack that stores the solution (the second argument should be null if the first argument is false ). Modifying print won't involve lots of code. Testing Your Solver One of the most important steps in writing code is testing to make sure it works (and debugging it when it doesn't!). For this assignment, you should create several maze files that differ in critical ways (e.g., one requires going left to find the solution, another requires going right). Test your program on these maze files does it solve all of them? You should create at least 2 maze files, but you may create morethe important thing about tests isn't how many you have but how well the tests cover the space of possibilities. Try to think about situations that you think could cause your code to fail, and create mazes that will tell you whether your code actually fails in that situation. Other Tips When testing and debugging your code on different mazes, try to isolate what method might be causing errors: print statements can help with this. When testing and debugging your code, it's also helpful to walk through it with a maze in front of you. I often draw out on paper what I think is happening in my code (variables, values for those variables, in this case a graphical version of the maze), and that allows me to walk step by step through my code to check whether what I think is true at each point is actually true. Writing things down helps you to check your assumptions, and often slows you down enough to recognize mistakes that you wouldn't see if you tried to keep everything in your mind as you read through the code on screen. Remember to look back at Java Style Guide for how to write understandable and maintainable code. One potential style issue on this assignment is having lots of printing code twicethink about how to avoid this. Part I: Understanding the Maze File Format Mazes are stored in text files and follow a particular format. We assume that our mazes are rectangular, and that they have walls along the entire outside of the maze, with no gaps in these outer walls. We will also specify a "start square" (S) and a "finish square" (F) to indicate the goal of the maze-solverto get from S to F. Maze files should have the following structure (both column numbers and row numbers start with O): Each row description includes a single character for each square in that row, and each character describes the right and top walls for its square. Specifically, there are four kinds of descriptors: 7 means that the square has both a top wall and a right wall (vertical bar or pipe) means that the square has a right wall, but no top wall _(underscore) means that the square has a top wall, but no right wall . * (asterisk) means that the square has neither a top wall nor a right wall Putting this together in a small example, if the input file contains the following (see maze.txt in the starter folder): Lines in file Interpretation 32 The maze has 3 columns and 2 rows 11 The start square is in the bottom middle. 20 The finish square is in the upper right. 7 (0,0) has a top wall; (0,1) has a top wall; (0,2) has a top and right wall *_7 (1,0) has neither top or right walls; (1,1) has a top wall; (1,2) has a top and right wall then the resulting maze would be printed as follows: 1 F 1 1 S Note that we specify only the top and right walls for each square, and not the bottom and left walls. This is sufficient to describe the whole mazemake sure to understand why this is. Part II: Loading and Printing the Maze The first step of the assignment is to finish the load method in Maze . Read through what's in Maze and MazeSquare in order to understand how the current code is organized. Decide how you'll be storing the squares of the maze. Modify Maze to include one or more) instance variable for storing the squares, and finish the load method. I recommend storing the squares as a list of MazeSquare s. The load method should return false if there are any squares that don't have *, 7, _, or as a descriptor, or the number of squares is inconsistent with the number of rows and columns specified at the beginning of the file. Don't forget to modify the constructor too (think that for each of the instance variable, what value makes sense for an empty maze). Complete the method getMazeSquare . A "stub" for this method is already provided in the Maze file (line 212). Now, you're ready to try out whether your methods function correctly. You'll be loading and printing a maze. Modify main so that with the following command line: java Maze maze.txt the file maze.txt is loaded and printed. At this point, the main should just involve constructing the maze and calling the load and print methodsit requires very little code. (Look in Maze for a print methodthis method will work correctly once you have a working getMaze Square .) Don't forget to compile before you run it. Before you move on, draw a maze on paper, and then make a maze file that represents that maze. Try loading the maze and printing it using the following command: java Maze where is replaced with the name of your maze file (put your maze file in the same folder). Part III: Solving the Maze Now it's time to solve the maze using the following algorithm. I'm giving you the steps; your job is to turn them into code: 1. Mark every square in the maze as unvisited. 2. Create an empty stack of maze squares. 3. Add the start square to the stack, and mark the start square as visited. 4. If the stack is empty, you're done and the maze is unsolvable. 5. If the top item is the finish square, you're done and the stack contains a solution to the maze. 6. If all squares adjacent to the top item (i.e. the squares up, down, right, or left from the top item-no diagonal adjacency) are either blocked by a wall or are marked visited already, remove the top item from the stack and go to step 4. 7. Otherwise, select a square that is adjacent to the top of the stack, unvisited, and accessible from the top of the stack (no wall between them). Mark this square as visited and push it on the stack. Go to step 4. You should implement this method in Maze . Specifically: Your Maze class must include a method with the following behavior and signature: 1 2 3 /** * Computes and returns a solution to this maze. If there are multiple * solutions, only one is returned, and get Solution makes no guarantees about * which one. However, the returned solution will not include visits to dead * ends or any backtracks, even if backtracking occurs during the solution * process. 4 5 6 7 8 9 10 11 * @return a stack of MazeSquare objects containing the sequence of squares * visited to go from the start square (bottom of the stack) to the finish square (top of the stack). If there is no solution, an empty stack is * returned. */ public Stack [--solve] For example, given the included maze. txt maze file, java Maze maze. txt on the command line should print the maze with no solution: F S However, java Maze maze.txt --solve should print the maze with the path of a solution marked: F Thus, you'll need to decide how to print a maze solution with the solution marked. Try to avoid duplicating code as much as possiblecan you modify the existing print method so that it can print a maze with or without a solution? If you modify print , make sure that the comment reflects what print now does. (Warning: your getsolution method shouldn't worry about displaying the solution thus shouldn't contain any printing statements, its purpose should be solely to get the solution as a stack and then return it.) Hint: You can add two parameters in the existing print : the first one can be a boolean indicating whether or not you'd like to print the solution; the second one is the Stack that stores the solution (the second argument should be null if the first argument is false ). Modifying print won't involve lots of code. Testing Your Solver One of the most important steps in writing code is testing to make sure it works (and debugging it when it doesn't!). For this assignment, you should create several maze files that differ in critical ways (e.g., one requires going left to find the solution, another requires going right). Test your program on these maze files does it solve all of them? You should create at least 2 maze files, but you may create morethe important thing about tests isn't how many you have but how well the tests cover the space of possibilities. Try to think about situations that you think could cause your code to fail, and create mazes that will tell you whether your code actually fails in that situation. Other Tips When testing and debugging your code on different mazes, try to isolate what method might be causing errors: print statements can help with this. When testing and debugging your code, it's also helpful to walk through it with a maze in front of you. I often draw out on paper what I think is happening in my code (variables, values for those variables, in this case a graphical version of the maze), and that allows me to walk step by step through my code to check whether what I think is true at each point is actually true. Writing things down helps you to check your assumptions, and often slows you down enough to recognize mistakes that you wouldn't see if you tried to keep everything in your mind as you read through the code on screen. Remember to look back at Java Style Guide for how to write understandable and maintainable code. One potential style issue on this assignment is having lots of printing code twicethink about how to avoid this