Project 3: Maze

Educational Objectives: Understand and experience the implementation of the Stack ADT and its application in the depth first search algorithm. Analyze algorithm complexity.

Statement of Work:

• Implement a generic Stack class template
• Use the generic Stack class template to implement the depth first search algorithm to find a route between two locations in a maze (two nodes in a graph).
• Analyze the run-time complexity of member functions of Stack.

Requirements:

This project contains two parts. In the first part, you will implement a Stack class template as an adaptor class. You have the freedom to use any C++/STL containers except the STL stack container. Note also that, you must not use the Vector class template you have implemented in Project 2: if you need to use the vector class, use the one provided in C++ STL. In the second part of this project, you will implement the depth first search algorithm. More specifically, you will design and implement a simulation that receives as input a rectangular 2-dimensional maze along with start and goal locations (as (row, col) coordinates) in the maze, and that produces a path (when one exists) through the maze from start to goal using depth-first search.

Task 1: Implement Stack as a generic adaptor class template

• You must implement Stack as an adaptor class template. You can use any C++ STL container except the C++ STL stack as the underlying adaptee class.
• Your implementation of Stack must be in the namespace of cop4530.
• You must provide the template definition and implementation in two different files Stack.h (containing Stack class template definition) and Stack.hpp (containing the implementation of member functions). You must include Stack.hpp inside Stack.h as we have done in Project 2.
• You must implement all the interface specified below for the Stack class template.

Stack interface (T is the template parameter, i.e., data type)

• Stack(): zero parameter constructor. Create an empty stack.
• ~Stack(): destructor. De-allocate memory if necessary.
• Stack(const Stack &rhs): copy constructor. Create the new stack with the elements of an existing stack rhs.
• Stack(Stack &&rhs): move constructor. Create the new stack with the elements of an existing stack rhs.
• Stack& operator=(const Stack &rhs): copy assignment operator.
• Stack& operator=(Stack &&rhs): move assignment operator.
• bool empty() const: return true if there is no element in the stack; return false otherwise.
• T& top(): return a reference to the top of the stack.
• const T& top() const: constant version of the above member function.
• void pop(): remove the first element in the stack and discard it.
• void push(const T& val): push a new element val into the stack.
• void push(T&& val): add a new element val to the stack. val should be moved instead of copied (if possible)
• int size(): return the number of elements in the current stack.

Analyzing the worst-case run-time complexity of the member function pop(). Give the complexity in the form of Big-O. Your analysis must be clearly understandable by others. Name the file containing the complexity analysis as "analysis.txt".

Task 2: Design and implement a simulation that simulates a rat pack finding food in a maze.

• In this part, you will design and implement a program that simulates a rat finding food in a maze. The input of the program is a file (redirected to the standard input) that describes the maze and the start and goal coordinates. The maze is described as a two dimensional rectangular array of square cells. The input has the following format:

  numrows numcols
  (first row of codes)
  (second row of codes)
  ....
  (last row of codes)
  start_row start_col goal_row goal_col

  File data numrows and numcols are the number of rows and columns in the mazes, respectivelye. Hence, the maze contains numrows * numcols cells. After that, there are numrows rows of codes describing the maze. Each row contains numcols codes; each code entry is an integer code in the range [0 - 15]. The code is interpreted as giving the "walls" of the cell by looking at the binary representation, with 1's bit = North wall, 2's bit = East wall, 4's bit = South wall, and 8's bit = West wall. (Interpret "up" as North.) For example, code 13 means a cell with North, South, and West walls but no East wall, because 13 = 8 + 4 + 1 = 1101(bin) (no 2's bit). start_row, start_col, goal_row, and goal_col give the starting and ending cell coordinates. Cell coordinates are numbered consecutively from left to right and top to bottom. For example, the left-top corner of the maze is cell (0, 0), and the right-bottom corner is cell (numrows-1, numcols-1). See the example maze files given in the project release for more details. An example maze description and the corresponding maze is as follows.

  4 5
  9 1 1 1 3
  8 0 0 0 2
  8 0 0 0 2
  12 4 4 4 6
  
   _ _ _ _ _ 
  |         |
  |         |
  |         |
  |_ _ _ _ _|
  
  

• Each cell in the maze (x, y) can at most connect to four neighboring cells: North to (x-1, y), South to (x+1, y), West to (x, y-1), and East to (x, y+1). Let mazecode[x][y] be the maze code for cell (x, y). You can check whether the cell has a wall for each given direction. For example, ((maze[x][y] & 0x1) == 0) means that (x, y) is connected to (x-1, y) (no walls to the north of (x, y)); and ((maze[x][y] & 0x8) == 0) means that (x, y) is connected to (x, y-1) (no walls to the west of (x, y)).
• In doing the depth first search, you program must search the directions in the following ORDER: North, East, South, West.
• The output of the program is a list of cells that the rat can follow from start to goal (See the output of maze.x).

Downloads:

Click here to download the provided tar file, which contains test_stack.cpp, sample executables test_stack.x, maze.x and maze_extra.x and some pre-made mazes files (maze0, maze1, etc). The sample executables were compiled on a linprog machine.

To run test_stack.x, do './test_stack.x'. To run maze.x, do './maze.x < maze0'.

Deliverables:

For Part 1, turn in all your source program files (Stack.h and Stack.hpp), makefile (to produce executable test_stack.x) and analysis.txt in a tar file via the Canvas system. It is due October 20, 11.59pm.

For part 2, turn in all your source program files (Stack.h, Stack.hpp, and proj3.cpp) and makefile (to produce executable proj3.x) in a tar file via the Canvas system. It is due October 27, 11:59pm.

Grading:

Part 1 (50 points):

• Typing 'make' in the subdirectory containing your submitted files with test_stack\ .cpp (or your modified test_stack.cpp) should produce the executable test_stack.x on linprog. If the program or makefile has any kind of (compiling) errors, no more than 10 points wil\ l be awarded.
• test_stack.x is successfully produced. (15 points)
• Pass all test cases in the provided test_stack.cpp. (15 points)
• Pass all test cases in another testing program (not provided). (5 points)
• Implementation of the functions (10 points)
• Complexity analysis for member function pop(): 2 points for the big O form and 3 points for explanation (5 points)

• Typing 'make' in the subdirectory containing your submitted files should produce the executable proj3.x on linprog. If the program or makefile has any kind of (compiling) errors, no more than 10 points will be awarded.
• proj3.x is successfully produced. (15 points)
• proj3.x successfully finds all paths for the given mazes (same output as the given maze.x) (25 points)
• proj3.x successfully finds all paths for other maze files (10 points)
• Extra point (10 points): proj3.x can display the maze and path from start to goal using ascii characters when the solution is found (same output as maze_extra.x)

Hints:

• Stack implementation should be fairly straightfoward.
• Run maze.x and maxe_extra.x to see how an acceptable program works and to analyze the supplied maze files. You can also use the supplied executable to check your own maze files.
• Pay particular attention to memory use. Make sure that your code does not access out of bound arrays. Be sure that your (Maze and Cell) objects do not leave memory unaccounted for during operation or upon termination.
• You can assume that the input maze file is always consistent and correct.
• There are many ways to get the answer in the second part: you just need to find one method that works for you.