You are allowed to work on this lab in teams of two. You must complete this lab with your teammate only, although you may discuss lab concepts with other students. Please keep the Academic Integrity Policy in mind---do not show your code to anyone outside of the professors and tutors, and do not look at anyone else's code for this lab. If you need help, please contact the professor or the tutors.

The main goal of this lab are to use data structures to implement algorithms. Concepts you will be familiar with after this lab include:

• Stacks and Queues
• Depth-First Search
• Breadth-First Search
• using the debugger (expect a fair amount of that!)

Click here to get all the files containing the starter code for this project.

In this lab, you will implement two search algorithms—depth-first search and breadth-first search—for finding a path through a maze.

Search Algorithms

In class last week, you saw the following search algorithm:

Algorithm MazeSearch:
   mark Start as visited // add the start to the dictionary as its own previous
   add Start to DataStructure // either stack (for DFS) or queue (for BFS)
   while (DataStructure is not empty):
      Current = remove location from DataStructure
      if (Current == Destination): // found a path!
         build the Path found by tracing back previous pointers in the dictionary
         return Path
      else
         get the list of neighbors of current
         for each Neighbor of Current:
         if Neighbor not visited: // you can tell by checking if Neighbor can be found in the dictionary
            record that Neighbor has Current as its previous
            add Neighbor to DataStructure
   return no Path exists

The way this algorithm traverses through locations depends on which data structure is used to store visited locations. When we use a stack, the algorithm is called Depth-First Search (DFS). When a queue is used, it is commonly called Breadth-First Search (BFS).

In this lab you will implement both DFS and BFS, use them to find paths through a 2-D maze, and explore how the two search algorithms produce different paths.

Below is an overview of the files required for submitting this lab. Those highlighted in blue will require implementation on your part. Those highlighted in black are complete and should not be modified except for comments.

• For this lab, you will need to use the Standard Template Library's implementation of vectors, stacks, queues and dictionaries. Click on the links to get the web page describing all their methods. You will not have to implement any of these data structures for this lab.
• position.h, position.cpp: The Position class, which keeps track of the contents of a position in a maze.
• maze.h, maze.cpp: The Maze class, which is used to represent a maze and provide solutions to it.
• mazeUtils.h, mazeUtils.cpp: definitions for Maze helper functions which load a maze from a file and render an answer.
• myDictionary.h and myDictionary.cpp: an implementation of the kind of dictionary that you will need for this lab. It respects the ADT covered in class
• main.cpp: the main program which loads a maze from a file, solves it, and prints out the result.
• Makefile: The build instructions for your lab.
• labyrinths.zip: a .zip file containing several maze files. Their format is described below. Copy all these files in the cmake-build-debug folder of your project.

For each .cpp file, read the corresponding .h file very carefully. The comments that precede each function and method give you precise information about what the function or method is supposed to do.

The Maze Layout

Each maze is a rectangular grid. Each space in the grid is assumed to be connected to the adjacent spaces (left, right, up, and down, but not the diagonally adjacent spaces. The starting point of each maze is the upper left corner; the exit is in the bottom right corner.

The layout of a particular maze will be stored in a file with the extension .map; you can find several examples in your labyrinths.zip. A map file contains the following information:

• The width of the maze in squares (i.e., the number of columns in the map)
• The height of the column in squares (i.e., the number of rows in the map)
• For each row of the map, a string describing all of the spaces in that row.
  • Each # character is a wall.
  • Each . character is an open space.

For instance, the following is a valid map:

5 3
.#.#.
.#...
...#.

We have given you the code which loads files in this format; this explanation is just for reference.

The Position Class

We will represent a maze as a two-dimensional grid of pointers to Position objects. Each Position object contains relevant information for one place in the maze: the (X,Y) coordinates, where (0,0) is the upper-left and X increases as you move right, Y increases as you move down) and whether that position is a wall. The constructor of the Position class should take the X and Y coordinate values and initialize the other fields to suitable default values.

You will have to add a method to_string in this class. The function should unambiguously convert the coordinates of the Position object into a string. For example, the Position object at coordinates (3,51) should be converted to a different string from the Position object at coordinates (35,1). So make certain that you add at least one character between the X and Y coordinates.

The Maze Class

A maze object represents our knowledge of a particular maze. We can use this information to find a path through the maze using various search algorithms. You will write two methods—solveDepthFirstSearch and solveBreadthFirstSearch—which are very similar. These methods will return a vector<Position*>: a vector of Position pointers, which constitute a correct path through the maze from the start to the finish. If no such path exists, the method should return an empty vector.

The 2-D grid that you create for your maze should take the form of a data member positions of type Position***. This is an array of arrays of Position pointers. This way, you can write e.g. positions[0][0] to get the Position* which points to the Position object in the upper-left corner. You'll have to use nested for-loops to initialize positions correctly.

You have been given the declaration of the maze class. You only need to implement each of the methods. The real magic of making the program work happens in these methods, which find a path through the maze using the search algorithm given above.

In the maze solver functions, you will need a map to keep track of which Positions have been visited and from which other Position they were visited. You will need a dictionary that maps strings to Position pointers. An implementation of such a dictionary called MyDictionary has been provided as part of the starter code. The reason why the keys in this map are strings is complicated, but long story short, it will work better this way. To map a Position to a string, you will need to program a to_string method in the Position object that will return an unambiguous string representation of the coordinates of the Position object.

Testing the Maze class

Make sure to run tests on your code as you develop. Definitely test your code once you've finished the Maze class! It will be easier to find bugs in your Maze implementation by direct testing than it will be by trying to find them by hand running the maze program.

Your code should pass all the tests from the file test.cpp included in the starter code.
Important note: since both test.cpp and main.cpp contain a function called main, only one of them should be in the file CMakeLists.txt when you compile your code.

Some of the map files in labyrinths.zip have multiple possible solutions. As a result, your output may differ from the provided solutions depending on how you explore the maze. To get the same results as the provided solutions, you should explore neighboring spaces in the following order: up, left, right, and then down.

Implementing Main

The implementation of main should be less work than the Maze class. It just involves assembling the pieces you've constructed above. The loadMap and renderAnswer functions have been written for you. loadMap will read a map file and return a Maze* if loading was successful. Otherwise, it will throw a runtime_error. renderAnswer should produce a string containing a solution, which looks like the map from the input file, but contains @ characters on the path you found. For example, here is a possible execution of the program:

$ ./maze
Welcome to Comp116 PrgAsst 05: The A-Maze-ing Race.
where is your maze file? cycle.map
Which search algorithm to use (BFS or DFS)? DFS
What is the name of the output file? solution.txt

Invalid Inputs: Your maze program should gracefully handle the following cases of invalid input:

• The user provides a search type other than "BFS" or "DFS"
• The user provides an invalid maze file (to be handled by catching the exception from loadMap)

Memory Management

Your program should run without any memory errors. It's OK if your destructor(s) do not clean everything up, but you should at least make a reasonable attempt (you should not leak most of the memory you allocated), and in any case, you should avoid dereferencing uninitialized memory.
For this and future labs, graders will assign minor penalties for poor commenting and coding style. Here are some style tips for this lab:

• You should pick meaningful variable names.

  // good
  int *array = new int[size];
  // bad
  int *a = new int[size];
  

• You should use correct and consistent indentation. Lines of code within a block should be indented two spaces further than lines surrounding them.*

    //good
    if(condition) {
      cout << "Test" << endl;
    }
  
    //bad
    if(condition) {
  cout << "Test" << endl;
       }
  

  *if your text editor's default indenting is four spaces instead of two, don't stress about it. Just be consistent when indenting.
  
• You should use a code block whenever possible, even if it's not necessary. This will help you avoid subtle/messy errors in the future.

  //good
  if(condition) {
    cout << "Something" << endl;
  }
  
  //legal but bad
  if(condition)
    cout << "Something" << endl;
  			 

• Do write comments at the top of each file, indicating your name and the purpose of the code file

  /**
   * Name: Martin Gagne
   * Project: PrgAsst6
   * File: SafeIntArray.cpp
   * Content: implementation of the methods for the class SafeIntArray declared in SafeIntArray.h
   */
  

• You don't have to write a comment for each line of code, but do write comments about meaningful chunks of code such as a loop, if/else statement, etc.

  void insertAtHead(int value) {
    // make sure that there is room in the array for the additional element
    if (this->size == this->capacity) {
      this->expandCapacity();
    }
    // shift all the current element one position to the right
    for (int i=size-1; i>=0; i--) {
      this->theArray[i+1] = this->theArray[i];
    }
    //place the new element
    this->theArray[0] = value;
  }
  

• Do write comments describing the purpose and signature of each function declaration. Use @param to describe an input parameter, @return to describe what gets returned, and @throws to describe exceptions that should be thrown. An example lies below:

  /**
   * Retrieves the first element of the list.
   * @return The element at index 0 of this list.
   * @throws runtime_error If the list is empty.
   */
  virtual T peekHead() = 0;
  
  

To summarize the requirements of this lab:

• You should have a working maze class.
• You should have a main function which provides a simple interface to solve maze problems.
• The input should be validated, and your code should contain no memory errors.

Submit a .zip file containing the entire project folder for the programming assignment using the submission link on onCourse.

This lab write up is based off of the Labyrinth lab developed by the Computer Science Department of Swarthmore College.