Data Structures and Algorithms

Lab 5: Labyrinth

Due on Sunday, October 23rd at 11:59 PM. This is a team lab. You and your assigned lab partner(s) will complete this lab together. Make sure that you are familiar with the Partner Etiquette guidelines. You may discuss the concepts of this lab with other classmates, but you may not share your code with anyone other than course staff and your lab partner(s). Do not look at solutions written by students other than your team. If your team needs help, please post on the Piazza forum or contact the instructor or ninjas. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

Overview

This lab comes in two parts:

An application that solves a maze using (at the user’s option) either breadth-first or depth-first search.
Written answers to questions regarding algorithmic analysis.

Like the last team lab, your repository URL will be git@github.swarthmore.edu:cs35-f16/lab05-<team-name>. You can see a list of all of your repositories on the Swarthmore GitHub in the lower-right side of the main page; make sure to switch your view to the organization for this class to see them.

Part I: `labyrinth`: A Maze Solver

The first part of this lab involves writing code for a program called labyrinth. This program will solve provided mazes using the depth- and breadth-first search algorithms discussed in class. Implementations of the Stack and Queue interfaces have already been provided in your starting code.

Your Starting Code

When you clone your repository, you will see the following files. Files you may need to change appear in bold.

adts/: A directory containing the C++ definitions of the ADTs you will use for this lab. You are not permitted to change these files.
adts/impls/: A directory containing reference implementations of our ADT definitions. These implementations simply act as wrappers for the C++ standard library classes.
position.h/position.cpp: The Position class which keeps track of the contents in a particular position in a labyrinth.
labyrinth.h/labyrinth.cpp: The Labyrinth class which is used to represent a labyrinth and provide solutions to it.
labyrinthUtils.h/labyrinthUtils.cpp: Provided utility functions for the Labyrinth class, such as reading files and rendering solutions.
main.cpp: The program which reads a labyrinth, solves it, and prints the result.

ADT Implementations

For this and future labs, you will occasionally be provided with implementations of the ADTs we discussed in class. These implementations make use of the C++ standard template library (STL) and are written as classes named e.g. STLList. To use these classes, simply #include the header the same way you normally would, using the directory names as necessary (e.g. #include "adts/impls/stlList.h). These implementations provide objects that effectively translate the C++ STL objects (which have notoriously sophisticated interfaces) into the form that we’ve been using in class.

The Layout of a Labyrinth

Source: OpenClipArt.org

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

The layout of a particular labyrinth will be stored in a text data file with the extension .map; you can find several examples in your test_data directory. We have already written the code which loads files in this format for you; this explanation is just for reference. A map file contains the following:

The width of the labyrinth in squares (that is, the number of columns in the map).
The height of the labyrinth in squares (that is, 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
...##
.#...
...#.

The `Position` Class

We will represent a labyrinth as a two-dimensional grid of Position objects. Each Position object contains relevant information for one place in the labyrinth: the (X,Y) coordinates (where (0,0) is in the upper-left), whether that position is a wall, and some fields which will be used during the search to construct an appropriate path through the labyrinth. The constructor of the Position class should take the X and Y coordinate values and initialize the other fields to suitable default values (like NULL or false).

The two-dimensional grid that you create for your labyrinth should take the form of a member field positions of type Position***: 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 properly.

The `Labyrinth` Class

Source: lucasfilm.com

A Labyrinth object represents our knowledge of a particular labyrinth; we can use this information to find a path through the labyrinth using various search strategies. You will write two methods – solveBreadthFirst and solveDepthFirst – which are extremely similar. These methods will return a List<Position*>*: a pointer to a new list of positions which constitute a correct path through the labyrinth from start to finish. If no such path exists, the method should instead return NULL.

You have been provided the declaration of the Labyrinth class; you merely 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 labyrinth. Here’s an algorithm you can use to implement your solver method:

Add the start position to your data structure
Mark the start position as visited
While there are positions left in the data structure:
- Take a position from the data structure; call it the current position.
- If the current position is the exit, then remove everything from the data structure; we’re finished!
- Otherwise, for each neighbor of the current position:
  - If that neighbor has not been visited:
    - Mark the neighbor as visited
    - Record the current position as previous to the neighbor
    - Add the neighbor to the data structure

At the end of the loop, you can determine whether you found a path by looking at the exit position; if that position has been visited, you just need to follow the previous position pointers backward from it until you reach the start to describe the path to take (in backwards order). If the exit position has not been visited, then there is no possible path through the labyrinth. The above algorithm works for both depth-first and breadth-first search, depending on which kind of data structure you use.

Testing the `Labyrinth` Class

Make sure to run the provided unit tests on your code as you develop; definitely test your code once you’ve finished the Labyrinth class! It’ll be easier to find most bugs in your Labyrinth implementation by direct testing than it will be by trying to find them by hand by running the labyrinth program.

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

Implementing `main`

The implementation for main is less work the Labyrinth 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; it will return a Labyrinth* if load is successful and will throw a runtime_error otherwise. renderAnswer will produce a string containing a solution, which looks like the map from the map file but contains @ characters on the path that you found. For instance, here is a possible execution of the program:

$ ./labyrinth test_data/cycle.map depth
@@###
#@@@#
#.#@#
#..@@
####@

Solutions to the provided test labyrinths are given in the .solution.txt files in the test_data directory; if a map is unsolvable, then its solution file will be missing.

Your program will take two command-line arguments:

The name of the map file containing the labyrinth to solve
Either "depth" or "breadth" to indicate the type of search to perform

If there is a solution to the provided map, your program should print the rendering of that solution. If there is no solution, your program should print a message to that effect.

Invalid Inputs

Your labyrinth program should gracefully handle the following cases of invalid input:

The user provides an invalid number of command-line arguments.
The user provides a search type other than "depth" or "breadth".
The user provides an invalid labyrinth file (to be handled by catching the exception from loadMap).

Memory

Your program is required to run without any memory errors. Some small memory leaks are acceptable, although you should make at least some effort to free up memory that you use (e.g. write a destructor for Labyrinth). Use valgrind to detemrine if you have any memory errors; we will do so, and any errors reported by valgrind will result in lost points. You should also consider using valgrind to find bugs in your program as you proceed; it’s a very powerful C++ debugging tool.

Coding Style Requirements

You are required to observe some good coding practices:

Source: OpenClipArt.org

You should pick meaningful variable names.

// Good
int* pixels = new int[size];
// Bad
int* p = new int[size];

You should use correct and consistent indentation. Lines of code within a block (that is, surrounded by { and }) should be indented four spaces further than the lines surrounding them.
```
// Good
if (condition) {
    cout << "Test" << endl;
}
// Bad
if (condition) {
cout << "Test" << endl;
    }
```
You should use a block whenever possible, even if it’s not necessary. This helps you avoid subtle or messy bugs in the future.
```
// Good
if (condition) {
    cout << "Something" << endl;
}
// Bad
if (condition)
    cout << "Something" << endl;
```
Any new methods or fields in your header files should have comments explaining their purpose and behavior. You are permitted to omit documentation for methods that are inherited from other classes; that is, if your class has a foo method because its superclass has a foo method, you don’t need to document that method.
```
// Good
public:
    /**
     * Saves the image represented by this object to a file.
     * @param filename The name of the file to save.
     * @return The number of pixels in the saved image.
     * @throws runtime_error If the image could not be saved due to an I/O error.
     */
    int save(std::string filename);

// Bad
public:
    int save(std::string filename);
```
Your method/field documentation does not have to be in the format above, but you must describe the method’s behavior, its parameters, its return value, and any exceptions that it may throw. (If you’re indifferent, the above syntax is a good one to know; it’s a de facto standard used by Javadoc, Doxygen, and other tools that automatically process source code comments into other formats like searchable webpages.)

Part II: Algorithmic Analysis

For this part of your assignment, you will give written answers much in the same way as you did in Lab 3. Your submission must be in a typeset PDF format according to that lab’s requirements; please see that link for instructions and see your Lab 3 template for instructions on how to use LaTeX.

For this part of the lab, answer the following questions.

Prove each of the following claims by induction.
- The sum of the first \(n\) odd numbers is \(n^2\). That is, \(\sum\limits_{i=1}^{n} 2i-1 = n^2\).
- \(\sum\limits_{i=1}^{n} \dfrac{1}{2^i} = 1 - \dfrac{1}{2^n}\)
- \(\sum\limits_{i=1}^{n} 3^i = \frac{3}{2}(3^n - 1)\)
The function minOdd, given below in pseudocode, takes as input an array \(A\) of size \(n\) of numbers and returns the smallest odd number in the array. If no odd numbers appear in the array, it returns ∞ (infinity). Using induction and loop invariants, prove that the minOdd function works correctly. (HINT: you should use the loop invariant “\(S(k):\) at the beginning of the loop iteration where \(i=k\), min is equal to the smallest odd number in the first \(i\) elements of the array”.)
A palindrome is a sequence of letters which is the same when reversed; for instance, “civic” is a palindrome in and of itself. We often ignore spaces in phrases to form palindromes; thus, we would view “taco cat” as “tacocat” and this is also a palindrome.
- Write an algorithm which inputs a string containing only letters and determines the size of the largest palindrome that the string contains. For instance, given the string “purplehelper”, the substring “plehelp” is a palindrome of 7 characters. Your solution must run in \(O(n^2)\) time (where \(n\) is the length of the string).
- Justify the runtime of your algorithm. That is, explain why it takes \(O(n^2)\) time and will not have a worse runtime for any input.

Peer Review

As this is a team assignment, you are required to complete a peer review of your lab partner or partners. You must do this even if everything is fine. You should complete this peer review after you have turned in your assignment. The peer review comes in the form of a simple Google Form and can be accessed here; in most cases, it will likely take less than a minute to complete. If you have trouble accessing this peer review, please make sure that you are logged into Google using your Swarthmore credentials.

Your peer review will be kept private; only course staff will have access to this information. You can also update your peer review after you have submitted it. However, if you do not submit a peer review, you will lose participation grade points. Please don’t forget!

Summary of Requirements

When you are finished, you should have

A working Labyrinth class
A main which provides a command-line interface to solve labyrinths
The ability to handle bad command-line arguments or user input
No memory errors!
Code which conforms to the style requirements above
Written answers to the algorithmic analysis questions in PDF form
A completed peer review