CS35 Lab 6: A-maze-ing Race

Part 1 due by 11:59pm Friday, October 9, 2015
Full assignment due by 11:59pm Sunday, October 26, 2015

The objectives for this lab are to:

To accomplish these goals, your lab consists of four steps:
  1. Finish the implementation of CircularArrayList from lecture.
  2. Implement a templated stack and a templated queue.
  3. Thoroughly test all three.
  4. Create a program to search for a way to navigate through a maze. You will first implement Maze and Position classes that we have declared, and then use your stack and queue to implement depth-first search and breadth-first search for the Maze.
You'll complete steps 1-3 before break, as they are shorter than the last. The first part requires you to implement just one function for the CircularArrayList class. Although you are implementing both a stack and a queue for the second part, both of those implementations are short because each stack and queue method is implemented in terms of a list method.

As usual, clone lab6-<usernames> starting files for this lab.

Dynamically resizing arrays

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:

  1. Allocate memory on the heap for a new, bigger array.
  2. Copy items from the old array to the new array.
  3. Update the CircularArrayList class data (such as size, headPos, capacity) as needed.
  4. Free the memory for the old array.
  5. Point the array pointer to the new array.
Please test your expandCapacity function before starting the next portion of the lab. A good way to test this function is to add a moderately large (100s) number of items to the list, then remove some (~half) of those items, and then add a large number of new items to the list. (This should not be the only test you perform. The goal here is to make sure that your expandCapacity function works correctly for any list state, not just when items have been added -- but not removed -- from the list).

Implement a stack and a queue

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.

Solving a maze

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


$ 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.

An implementation strategy
Note: Below is a guide on how to proceed with implementation.

We have declared Maze and Position classes to help represent a maze. You should start by implementing these classes:

  1. The Position class represents one position in the maze; i.e., an x and y position in the maze. It stores relevant information for that position including x and y, whether it is a wall, whether is is on the found path, and the previous Position on the path.

    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?

  2. The Maze class represents the rectangular grid and walls of a maze. It stores the number of rows and columns in the maze, and a 2-dimensional Position array marking the positions of walls in the maze. You should complete the Maze by implementing the constructor as well as access and update functions that we've declared. Be sure to look closely at your class examples and notes for allocating a two-dimensional array on the heap.

    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?

  3. After you have thoroughly tested your Position and Maze implementations, implement breadth-first and depth-first search in solveMaze.cpp. For each search algorithm you'll need to keep track of a data structure (a queue or stack) containing the Positions left to explore as well as a Maze object containing the necessary information to navigate the maze
  4. You will need to carefully think about how to use the Maze and associated Position objects to keep track of what points in the maze have been visited and where they have been visited from.

    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):
         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.in 
The 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.in 
See 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.