The objectives for this lab are to:
As usual, clone lab6-<usernames> starting files for this lab.
Relevant Files (those in blue require modification):
The CircularArrayList class can currently hold only a fixed number (10) of items. You should implement the private expandCapacity() method to expand the array when the array is full. The basic outline for doing this is:
Relevant Files (those in blue require modification):
Complete a stack and queue implementation, based on an existing list implementation, that inherits from and implements the provided Stack and Queue interfaces. We've declared an ArrayStack class for you to implement; in contrast, you will be not given a starting point for the Queue implementation, so be sure to create your own solution in an appropriately named file.
Please thoroughly test your stack and queue implementations before proceeding to the third part of this lab. We assure you that you do not want to debug your stack and queue implementations using your depth-first and breadth-first search programs.
Relevant Files (those in blue require modification):
In this part of the lab you will implement two search algorithms -- depth-first search and breadth-first search -- for finding a path through a maze.
Each maze is a rectangular space with an entrance at the upper left-hand corner, an exit at the lower right-hand corner, and some internal walls. Your algorithm must find a path through a given maze starting from the entrance and finishing at the exit, without passing through any walls. The path may move through the maze by going up, down, left, or right -- but not diagonally.
For example, here is one depiction of a 5x5 maze:
start --> * * * O O 1 1 * 1 1 O * * O O O * 1 1 1 O * * * * <-- finish Path: (0,0) (0,1) (0,2) (1,2) (2,2) (2,1) (3,1) (4,1) (4,2) (4,3) (4,4)The 0s represent open spaces in the maze and the 1s represent walls. The asterisks represent a path from the entrance to the exit of the maze. Locations in the maze are indexed by row and column, with (0,0) always being the entrance in the upper-left corner, and the exit always being (rows-1,columns-1) in the lower-right corner. (In this case, the 5x5 maze, the exit is at (4,4).)
Here are two example program executions, one with a successful search and one for which the maze had no solution:
$ ./solveMaze How many rows are in the maze? 5 How many columns are in the maze? 5 How many walls does the maze have? 7 Please enter the row and column position for each of the 7 walls: 1 1 2 1 3 1 1 3 2 3 3 3 4 3 start --> 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 <-- finish Searching with stack... found a path. The path has length 17. Path: (0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (4,2) (3,2) (2,2) (1,2) (0,2) (0,3) (0,4) (1,4) (2,4) (3,4) (4,4) start --> * O * * * * 1 * 1 * * 1 * 1 * * 1 * 1 * * * * 1 * <-- finish Searching with queue... found a path. The path has length 9. Path: (0,0) (0,1) (0,2) (0,3) (0,4) (1,4) (2,4) (3,4) (4,4) start --> * * * * * O 1 O 1 * O 1 O 1 * O 1 O 1 * O O O 1 * <-- finish $ ./solveMaze How many rows are in the maze? 5 How many columns are in the maze? 5 How many walls does the maze have? 4 Please enter the row and column position for each of the 4 walls: 3 0 2 1 1 2 0 3 start --> O O O 1 O O O 1 O O O 1 O O O 1 O O O O O O O O O <-- finish Searching with stack... no path was found. Searching with queue... no path was found.
The Makefile for this lab works slightly differently than from before, to make compiling and running your code more obvious. To run tests, you will run two commands; first one that builds the test executable, then one that runs it:
$ make testList $ ./testList
To use Valgrind with such a test, run it explicitly:
$ make testList $ valgrind ./testList
or
$ make testList $ valgrind --leak-check=full ./testList
Similarly, to run the main program, use:
$ make solveMaze $ ./solveMaze
With analogous commands for running with Valgrind. To run your stack/queue tests, use the same commands with the make target testStackQueue.
We have declared Maze and Position classes to help represent a maze. You should start by implementing these classes:
It has two constructors: a primary constructor that accepts an x and y value as arguments and constructs a Position for that position. All other class variables should be given default values for a Position (e.g., it is not a wall, not on the path, has not previous location). The second constructor is a default constructor that should set x and y to some invalid maze position, such as (-1,-1).
Using position.h as a guide, you should implement all the methods for the Position class one-by-one in the position.cpp file. Most of these are very simple, one or two line methods.
Stop and test: Can you construct a single Position? Can you access the x and y value? Can you create a list of Positions? Are you correctly storing information about the wall? the path?
Most of the Maze functions are simple one- or two-line functions. The getNeighbors(p) function is slightly more complicated: it returns a list of all valid non-wall neighbors for a given position p. A position is a valid non-wall neighbor of p if (1) it is up, down, left, or right of p, (2) it is within the bounds of the maze, and (3) it is not a wall.
Stop and test: Can you create a simple Maze? Try printing out the values at each grid location. What do you get if you call getNeighbors? Does it return the correct number and values of the numbers of a grid point?
With this data, the following pseudocode describes both breadth-first and depth-first search:
Add start position to data structure. Mark start position as visited. while (data structure is not empty): current = Remove position from data structure. if (current is exit): break for (each valid neighbor of current): if (neighbor has not been visited): Mark neighbor as visited. Record neighbor as visited from current. Add neighbor to the data structure.After this algorithm is complete current will be the maze's exit position if the search found a path, but will be some other position if the search failed. If the search succeeded you can reconstruct the path by checking from which position the exit was visited, and then checking from which position that position was visited, and so on, until you reach the maze entrance. You should print the maze and the path positions as in the examples above using the print method of the Maze class.
Testing your main program: I have provided three test files. You can use cin to obtain input for your program and then type in the values in the test file. This can get tedious, so a better strategy is to pipe in your input:
$ ./solveMaze < inputs/test0.inThe direction of the bracket is important - this tells unix to use the file test0.in as the standard input. cin will read the values as if they were typed in by a user. Alternatively, feel free to use file i/o as demonstrated in previous labs. You'll have to take the file name as input to the program:
$ ./solveMaze inputs/test0.inSee me if you are interested in pursuing this.
Working executable For an example working maze solver, see the following program:
$ ~jpolitz/public/cs35/solveMaze
Once you are satisfied with your program, hand it in by pushing to Github. We will check to make sure you've submitted (at least) the first part by Friday midnight. You are encouraged to go beyond this initial submission if possible.