COMP 2140 Assignment 2: A Run-time Stack and Merge Sorting a Linked List Helen Cameron and Stephane Durocher Due: Wednesday October 22 at noon Programming Standards When writing code for this course, follow the programming standards, available on this course’s website on Desire2Learn. Failure to do so will result in the loss of marks. Objective To test, using a backtracking algorithm, if a mouse can escape from a rectangular maze. Your Program General Overview: Your program must implement a backtracking algorithm that helps the mouse by systematically trying all the routes through the maze until it either nds the exit or exhausts all possible routes (and concludes that the mouse is trapped in the maze). If the backtracking algorithm nds a dead end, it retraces its path until it reaches a position from which there is an untried path. The backtracking algorithm always tries all directions (forward, backward, left, and right | no diagonal moves allowed) from any position it reaches. The Input : The input to the algorithm is a maze with walls (represented by 1 characters) and open passage ways (represented by 0 characters). The starting position of the mouse is represented by m and the exit from the maze by e . Your program should prompt the user to choose a le and then read the maze in from the le. The rst line of the input will contain the number of rows and the number of columns in a maze. Thus, the input might look like the following: 6 5 1 1 1 1 1 1 0 0 e 1 1 1 1 0 1 1 m 1 0 1 1 0 0 0 1 1 1 1 1 1 The maze will always have a wall around the outside, so you need not be concerned about the mouse falling o the maze as it explores all directions. The Backtracking Algorithm: The backtracking algorithm keeps a stack of positions that are the beginnings of paths it has yet to try. From the current position, the algorithm pushes onto the stack any untried open neighbouring positions (i.e., non-wall positions, if there are any), always looking forward, backward, left and right from the current position. At each step, the algorithm pops the top position o the stack and pushes the untried neighbouring positions onto the stack. The algorithm must mark each visited position with a period to avoid revisiting positions | so that it will not loop forever trying the same routes. The overall goal is to nd the path to the exit from the starting position. Thus, we need to remember how we got to the exit in the search process. The algorithm not only marks an unvisited neighbouring position as visited, but it also stores what position we got to the neighbour from. For example, if we visit position N because it is a neighbour to position C that we are currently at, then we also record at N that we came from C . These records will allow us to trace backwards through the path (i.e., from the exit to the mouse starting point) after the backtracking completes (assuming we manage to nd the exit). The backtracking algorithm works as follows: initialize the stack; goal = the position of the exit in the maze; start = the initial position of the mouse in the maze; push start onto the stack; while we haven t found the goal and the stack isn t empty f curr = pop the top position off the stack; currRow = the row number of position curr; currCol = the column number of position curr; check each of the four neighbouring positions of curr in turn: if the neighbour is a valid position f check if it is the goal if it s not the goal and it is open and has not been visited yet f visit it: mark it with . and set its previous position to curr; push it on the stack; g g g // end while Once the maze is processed, if we found the exit, we can mark the positions on the path with P (so we can see it when we print out the maze). The path-marking works as follows: curr = goal; while ( curr != start ) f if ( curr != goal ) set the maze element at position curr to P ; curr = previous position stored with this maze element by the backtracking algorithm; g Stack: Because the backtracking algorithm needs a stack, you must implement a stack class. Each item in the stack is the position of a cell in the maze | that is, the row and column number of the cell. The marker should be able to remove your stack implementation and replace with another stack implementation and still have your program work. Thus, you must provide a standard stack implementation with the standard methods ( push , pop , top , and isEmpty ). Use the linked-list implementation of a stack | you may use the code from class. The Output: Your program must print out the maze after you read it in, and after you have processed the maze to nd the path. For example, Assignment 2 COMP 2140 Fall 2014 Finding a path through a maze —————————- The input maze: 1 1 1 1 1 1 0 0 e 1 1 1 1 0 1 1 m 1 0 1 1 0 0 0 1 1 1 1 1 1 The path to the exit (marked with P ): 1 1 1 1 1 1 0 0 e 1 1 1 1 P 1 1 m 1 P 1 1 P P P 1 1 1 1 1 1 Path-finder program ends normally Here’s another example output: Assignment 2 COMP 2140 Fall 2014 Finding a path through a maze —————————– The input maze: 1 1 1 1 1 1 1 1 1 m 0 0 0 1 e 1 1 0 1 0 0 1 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 Mouse is trapped — exit not found (visited positions marked with . ): 1 1 1 1 1 1 1 1 1 m . . . 1 e 1 1 . 1 . . 1 1 1 1 . 1 . . 1 . 1 1 . 1 1 . 1 . 1 1 . . . . . . 1 1 1 1 1 1 1 1 1 Path-finder program ends normally Suggestions Here is a list of classes that your program might have, depending on how you implement things: The class matching the le name, which probably contains only the main method. Position class: Each instance contains the row and column of a position in the maze. This class probably only needs the standard accessors and mutators/action methods. Node class: Ordinary node class (you could use the code from class) for use by the stack. Each node stores a Position Stack class: Standard stack class (you could use the code from class). A maze eleand the previous position on the path from the mouse’s starting position to the exit (in case this maze element turns out to be one of the positions on the path from the starting position to the exit).
A maze class: Each instance contains the two-dimensional maze array, the number of rows and the number of columns, the starting position of the mouse and the position of the exit. The constructor for this class could be the method that prompts for the input le’s name and reads in the maze. The backtracking algorithm and the path-marking algorithm should be methods in this class. The String methods trim and split can be used to read the characters of a row of the maze: String inLine = inFile.readLine(); inLine = inLine.trim(); String tokens = inLine.split( “\\s+” ); for ( int i = 0; i < tokens.length; i++ ) System.out.println( “The next char in the row is ” + tokens[i].charAt(0) ); Hand-in Instructions Go to COMP2140 in Desire2learn, then click \Dropbox” under \Assessments” at the top. You will nd a dropbox folder called \Assignment 2″. Click the link and follow the instructions. Please note the following:
Submit ONE .java le. The .java le must contain all the source code. The .java le must be named A2<your last name><your student id>.java (e.g., A2Cameron1234567.java ).
Please do not submit anything else. We only accept homework submissions via D2L. Please DO NOT try to email your homework to the instructor or TAs. We reserve the right to refuse to grade the homework or to deduct marks if these instructions are not followed. Honesty Declaration NEW: You can check if you have handed in an honesty declaration by looking at your COMP 2140 grades on D2L. There’s a grade column for \Honesty declaration” (or shortened to \HD”), which should contain \Yes” | if it contains anything else, you have not given your instructor an honesty declaration. Your Assignment 2 (and any other work in this course) will not be marked unless you have handed in the blanket honesty declaration. (The honesty declaration is available on the course website in Desire2Learn under \General Information (all sections)” in the Content Browser. You should have handed in the honesty declaration to your instructor by September 18.) You must hand in the honesty declaration exactly ONCE this term and it will apply to all of your assignments and other work in this course.