This lab consists of three parts:

1. Implement the expandCapacity function for the CircularArrayList from lecture.
2. Implement a templated stack class and a templated queue class, using an existing list implementation.
3. Implement Maze and MazePosition classes that we have declared, and then use your stack and queue to implement depth-first search and breadth-first search for the Maze.

The first two parts of this lab are substantially 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 function is a one-line call to a function of an existing list. You may, and should, work with a partner on this lab.

As usual, run update35 to obtain the cs35/labs/05 directory and the starting files for this lab.

The CircularArrayList class can currently hold only a fixed number (10) of items. You should implement the private expandCapacity() function 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. (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).

Complete a stack and queue implementation, based on an existing list implementation, that inherits from and implements our Stack and Queue interfaces. We've declared an ArrayStack class for you to implement; if you want, though, you may ignore our definition and instead implement a LinkedStack class based on the templated LinkedList implementation from class. You must declare and implement either an ArrayQueue or LinkedQueue class that inherits from the Queue interface. 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 e.g. linkedqueue.h or arrayqueue.h.

You may assume that the list implementation performs adequate error-checking; each stack and queue function can be a single call to an existing list function.

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.

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

  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.

Note: Below is a guide on how to proceed with implementation. You are expected to employ modular testing. While I haven't provided a simple test file this week, you should be creating test programs to make sure each of your implementations are working in isolation. The ninjas cannot and will not be able to help you if you are using the main solveMaze program as your testing method.

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

A MazePosition is a simple class that represents one position in the maze; i.e., a row and column position in the maze. It has two constructors: a primary constructor that accepts a row and column as arguments and constructs a MazePosition for that position. The second constructor is required to prevent subtle C++ problems, but will not be used in your actual program. (This second constructor should set row and column to some invalid maze position, such as (-1,-1).) You should implement both constructors and the getRow() and getColumn() methods, and then test your implementation.

Stop and test: Can you constructor a single MazePosition? Can you access the row and column value? Can you create a list of MazePositions?

A Maze represents the rectangular grid and walls of a maze. It stores the number of rows and columns in the maze, and a 2-dimensional boolean array marking the positions of walls in the maze. (The positions of walls are marked as true, and open spaces are false.) We've implemented the Maze constructor and destructor for you, as a demonstration of how to allocate and free 2-dimensional arrays on the heap. You should complete the Maze by implementing the access and update functions that we've declared.

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?

After you have thoroughly tested your MazePosition and Maze implementations, implement breadth-first and depth-first search in solveMaze.cpp. For each search algorithm you'll need to keep track of the following data:

• A data structure (a queue or stack) containing the MazePositions left to explore.
• A 2-dimensional array storing, for each position in the maze, whether you've already visited that position.
• A 2-dimensional array marking, for each position p in the maze, from what position you first visited p during your search.

The Maze constructor and destructor contains an example of how to create and initialize a 2-dimensional array on the heap. (Also note that the above information is redundant; with a careful representation you can combine the data representing if a position has been visited with the data recording where that position was 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):
         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.

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 < 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 last week's lab. You'll have to take the file name as input to the program:

$ ./solveMaze test0.in 

See me if you are interested in pursuing this.

Once you are satisfied with your program, hand it in by typing handin35 at the unix prompt.

You may run handin35 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize after handing in some programs that you'd like to make a few more changes to them.

Home Page