Description
Objectives • Experience implementing the Stack ADT using an array • Experience writing recursive methods Objectives This assignment requires you to implement a Stack interface using an array. Although there is a tester provided for this assignment, it does not include a comprehensive set of sets for each method. You should add your own tests to test cases not considered. Note: The automated grading of your assignment will include different and additional tests to those found in the A4Tester.java file. After implementing the Array in A4Stack.java, you will use the stack to solve a text-based maze. The strategy will be to push all of the maze positions onto the stack. If a dead-end is reached, recently visited positions can be popped off the stack (equivalent to backtracking in the maze) until the last fork in the road, and a different route can be attempted. When the end location of the maze is reached, the stack is holding all of the positions traveled on the path from the start to finish. Quick Start 1. Download all of the .java files found in the Resources > Assignments > a4 folder. 2. Read through the documentation provided in the Stack.java interface, there is a lot of very useful information that will help you with your implementation of each method in A4Stack.java. 3. Compile and run A4Tester.java. Work through implementing each method one at a time. Debug each method until all tests pass for that method before proceeding to the next method. 4. Once you have completed A4Stack.java, begin working on MazeRunner.java. 5. More detailed Maze instructions are found on the next page. 6. Here is a video explaining the process of solving a maze. CRITICAL: You must name the methods in A4Stack.java and MazeRunner.java as specified in the documentation and used in A4Tester.java or you will receive a zero grade. Remember that all methods specified in an interface must be implemented, or your code will not compile correctly. Any compile or runtime errors will result in a zero grade (as if the tester crashes it will not be able to award you any points for any previous tests that may have passed). Submission and Grading Submit A4Stack.java and MazeRunner.java with your name and student ID at the top using conneX. If you chose not to complete some of the methods required, you must provide a stub for the incomplete method(s) in order for our tester to compile. If you submit files that do not compile with our tester, you will receive a zero grade for the assignment. It is your responsibility to ensure you follow the specification and submit the correct files. Additionally, your code must not be written to specifically pass the test cases in the tester, instead, it must work on all valid inputs. We may change the input values when we run the tests and we will inspect your code for hard-coded solutions. Be sure you submit your assignment, not just save a draft. ALL late and incorrect submissions will be given a ZERO grade. A reminder that it is OK to talk about your assignment with your classmates, but not to share code electronically or visually (on a display screen or paper). We will be using plagiarism detection software. Solving the Maze There are a number of different .java files you will use to solve a text-based maze. Before looking at the Java files, first we will look at the format of the maze input files: Each input file should begin with 2 integers on the first line. The first integer is the number of rows the maze contains, the second is the number of columns. The size of the maze in the input file to the right is 9 rows by 11 columns. The second line has two integers representing the starting coordinates, which is where the maze begins. In the input file shown on the right, the starting coordinates are (0,1), representing row 0 and column 1. The third line has two integers representing the finish coordinates. For the input file on the right, the finish coordinates are row 8 and col 9. The remaining lines are maze data. The file shown on the right has 9 rows of maze data, each with 11 columns. H’s are considered walls, spaces are considered open pathways. The following diagram depicts the information explained above more visually: You have been provided with a number of Java classes to help you write a maze solver. The first class is MazeLocation.java. This class represents a position in the maze, which consists of a row and column. For example, we could make two MazeLocation variables to represent the start and finish of the maze shown above: MazeLocation start = new MazeLocation(0, 1); MazeLocation start = new MazeLocation(8, 9); row: 0 row: 1 row: 2 row: 3 row: 4 row: 5 row: 6 row: 7 row: 8 columns:01234567890 maze01.txt: 9 11 0 1 8 9 H HHHHHHHHH H H H HHH H HHH H H H H H HHHHHHH H H H H H H HHHHHHH H H H HHHHHHHHH H height: 9 rows width: 11 columns first line: <#rows> <#columns> second line: start coordinates third line: finish coordinates following lines: maze data start: row: 0 col: 1 finish: row: 8 col: 9 9 11 0 1 8 9 H HHHHHHHHH H H H HHH H HHH H H H H H HHHHHHH H H H H H H HHHHHHH H H H HHHHHHHHH H The next class is Maze.java. This class has three fields: the start and finish maze locations (described already), and a two-dimenstional character array called mazeData. Maze data is an array of characters representing the current state of the maze (which starts with H’s as walls and spaces as open paths). For example, mazeData for the sample maze would be the following: 0 1 2 3 4 5 6 7 8 9 10 0 H H H H H H H H H H 1 H H H 2 H H H H H H H H 3 H H H H 4 H H H H H H H H H 5 H H H 6 H H H H H H H H H 7 H H 8 H H H H H H H H H H Remember, the MazeLocation class allows us to locate a position in the maze. For example a MazeLocation with fields row:2 and col:3 would be at the following position: 0 1 2 3 4 5 6 7 8 9 10 0 H H H H H H H H H H 1 H H H 2 H H H H H H H H 3 H H H H 4 H H H H H H H H H 5 H H H 6 H H H H H H H H H 7 H H 8 H H H H H H H H H H The mazeData array is updated as the maze is explored. For example, when starting at MazeLocation (0, 1), an ‘o’ is written to the maze with the statement mazeToSolve.setChar(0,1,’o’); (representing the fact that the location (0,1) has been visited): The video outlines how you will continually update the mazeData array as you traverse through the maze, until (hopefully) finding a path to the finish location. The next page overviews a strategy to visit different locations until a solution is computed. 0 1 2 3 4 5 6 7 8 9 10 0 H H H H H H H H H H 1 H H H 2 H H H H H H H H 3 H H H H 4 H H H H H H H H H 5 H H H 6 H H H H H H H H H 7 H H 8 H H H H H H H H H H 0 1 2 3 4 5 6 7 8 9 10 0 H o H H H H H H H H H 1 H H H 2 H H H H H H H H 3 H H H H 4 H H H H H H H H H 5 H H H 6 H H H H H H H H H 7 H H 8 H H H H H H H H H H The MazeRunner.java file is what you will be modifying. You will be implementing the findPath method, which is a recursive method that uses a stack to solve the maze. NOTE: the only method you should modify is the findPath method. The general strategy to implement the findPath method is the following: 1. Update mazeData array by writing an ‘o’ to the current location 2. Check if you are the finish location, if so, you have solved the maze! 3. If not, check if there is an open path in a neighbouring location (meaning you can progress that way through the maze), and if so, push that location onto the stack and visit it (there are 4 neighbouring locations we can try – the order you want to progress through the maze is up to you). 4. If none of the neighbouring locations lead to the finish (i.e., we’re at a dead end) then pop off the stack so we can backtrack and attempt a different route (maybe we tried going down when we hit a fork in the road the first time, and found a dead end. This allows us to backtrack to that fork and go in a different direction). Write an ‘x’ every time we backtrack to keep track of the routes that resulted in a dead end. 5. If we have tried all of the options, the maze just isn’t solveable. The last method in the TA4Tester.java, allows you to test the different maze files by passing in a maze input file using the command line. After compiling, it is executed the following way: java A4Tester For example: java A4Tester maze01.txt Good luck!
