Data Structures and Algorithms

Lab 6: Labyrinth

Due on Sunday, March 20th 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

For this lab, you will write two data structures: a stack and a queue. You will then write a program which uses these data structures to find a path through a maze. Like the last team lab, your repository URL will be git@github.swarthmore.edu:cs35-s16/lab06-<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.

Completing this lab involves the following steps:

• Implement the CircularArrayList class. Make sure to test it thoroughly before you proceed; by making sure you have no bugs in CircularArrayList, you make it easier to find bugs in your later code.
• Implement the CircularArrayStack and CircularArrayQueue classes using the CircularArrayList. This should be pretty straightforward, since you’ll use CircularArrayList to the hard work. Regardless, make sure you test them thoroughly!
• Implement the Position class and test it; then, use this to implement and test the Labyrinth class which will solve the labyrinth for you.
• Implement the labyrinth_main function. You can do this with just one of CircularArrayStack or CircularArrayQueue, so you don’t have to implement everything in the order given here. As usual, make sure to test your labyrinth_main function using the RUN_MAIN utility function.

This webpage will give hints on how to implement and test each of these features and show examples of execution.

Implementing a CircularArrayList

Relevant files:

• list.h: A templated list interface. You will not change this file.
• circular_array_list.h: The file containing the CircularArrayList class.
• test_circular_array_list.cpp: A file where you will write tests for CircularArrayList.

You can use the lecture notes regarding both templated classes and array lists to complete this part of your assignment.

Since you are implementing a form of ArrayList, remember that it will be your responsibility to keep track of an array (e.g. contents), the size of that array (e.g. capacity), and the number of elements in the list which occupy positions in that array (e.g. size). You’ll also have to keep track of the offset (e.g. head_offset) which tells you the position of the first element in the array. Finally, it will be your responsibility to replace the contents array when the list grows beyond that array’s capacity. You should create an ensure_capacity method just like we did in class, which does the following:

• Create a new, bigger array
• Copy all of the elements from the old array into the new one, careful to put them into the right positions.
  • At this point, you could make things easier on yourself by copying the first element of the list into the first position of the new array; when you’re finished, you just have to remember to set head_offset to zero.
• Delete the old array and make contents point to the new array
• Update all of your fields (capacity, head_offset, etc.) to preserve the class’s invariants.

Testing the CircularArrayList

You should make sure to test the CircularArrayList thoroughly. It’s especially important that you exercise the ensure_capacity method and the head_offset functionality of the list.

One test to exercise ensure_capacity could be written something like this:

• Add a moderate number (e.g. 100) of elements to the end of the list.
• Make sure each element is where you think it should be.
• Remove many (e.g. half) of them from the end of the list.
• Check that each element is still where it should be and that the size is correct.
• Add a lot more (e.g. 1000) elements to your the end of your list.
• Verify the size and the value of each element.

This shouldn’t be the only way that you test ensure_capacity, but this testing algorithm is provided here to give you an idea of things to try. Note: this algorithm never adds things to the beginning of the list. This way, we’ll be able to see if there’s a bug in ensure_capacity (this test would fail) or if there’s a bug in e.g. how head_offset is handled (this test would pass but another test would fail).

To test head_offset, you can perform a similar test to the above but add the elements to the front of the list rather than to the end. You can also use a simpler algorithm like this:

• Add an element to the end of the list.
• Check that index zero contains that element.
• Add an element to the front of the list.
• Check that index zero contains the new element.
• Check that the size of the list is correct.

These are just a few of the many tests that you should write. Remember: each test helps you build confidence that your implementation of CircularArrayList is correct. Once you believe that the implementation is complete, you’ll have a much easier time isolating bugs in the rest of your code.

Implementing CircularArrayStack and CircularArrayQueue

Relevant files:

• ordered_collection.h: The templated OrderedCollection interface. You will not change this file.
• stack.h: The templated Stack interface. You will not change this file.
• queue.h: The templated Queue interface. You will not change this file.
• circular_array_stack.h: The file in which you will write your templated CircularArrayStack implementation.
• circular_array_queue.h: The file in which you will write your templated CircularArrayQueue implementation.
• test_circular_array_stack.cpp: A test program in which you will test your CircularArrayStack.
• test_circular_array_queue.cpp: A test program in which you will test your CircularArrayQueue.

In completing the stack and queue implementations, please remember: most of the work is already finished. Your queue won’t have to worry about things like head offset or capacity; the CircularArrayList is taking care of that for you! Just make sure your object has an appropriate CircularArrayList field that you can use to implement its methods.

Note that both Stack and Queue are subtypes of OrderedCollection. The implementation of the OrderedCollection methods should be very easy: you just make your object call one of its own methods to perform the operation. To give you an example of this (and a starting point), part of CircularArrayStack has been written for you. You will have to write CircularArrayQueue from scratch, but you can use CircularArrayStack as a guide.

Testing CircularArrayStack and CircularArrayQueue

Remember to test these data structures thoroughly so that you can rely on them when you write your labyrinth solver. You don’t want to try to debug them by running your labyrinth_main!

When testing these data structures, make sure to examine the behavior that is specific to the data structure. If your tests for CircularArrayList are good, for instance, then you shouldn’t be trying to add lots of elements to a stack to see if ensure_capacity works; that’s not part of the implementation of CircularArrayStack. Instead, make sure that e.g. elements are returned in the opposite order that they were added (last-in-first-out).

Solving a Labyrinth

Relevant files:

• position.h/position.cpp: A Position class, describing a single position in the labyrinth.
• labyrinth.h/labyrinth.cpp: A Labyrinth class, describing the entire labyrinth and related operations on it.
• labyrinth_main.cpp: The file containing the main part of your program.
• program.cpp: A wrapper file for the main function. You will not need to change this file.
• test_labyrinth.cpp: A test program in which you will test your Position and Labyrinth classes as well as your labyrinth_main.

In this part of the lab, you will write a program which helps you to solve labyrinths. To solve them, you will use two strategies: a depth-first search and a breadth-first search. The OrderedCollection interface will make it possible to switch between these algorithms simply by changing which type of data structure (stack or queue) you create.

The Layout of a Labyrinth

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

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 – solve_breadth_first and solve_depth_first – which are extremely similar. To avoid duplicating a lot of code, both of these methods should call a solve method which takes an OrderedCollection* as an argument; this makes it possible to write solve_breadth_first and solve_depth_first in a single line each. All three 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, culminating in the solve method which finds a path through the labyrinth. Here’s an algorithm you can use to implement your solve method:

• Add the start position to your OrderedCollection 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 OrderedCollection you use.

Testing the Labyrinth Class

Make sure to stop and test your code at this point! Using your Labyrinth class, you should be able to write some simple tests that find valid paths. One test has been provided for you in test_labyrinth.cpp, but you should write more to be sure that there’s nothing you’re missing. Just like with the data structures above, it’ll be easier to find most bugs in your Labyrinth implementation by direct testing than it will be by trying to find them through labyrinth_main.

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 get_neighbors method: up, left, right, and then down.

Implementing labyrinth_main

The implementation for labyrinth_main is pretty easy; it just involves assembling the pieces you’ve constructed above. This is made simpler by the fact that the load_map and save_answer functions have been written for you. load_map will read a map file; it will return a Labyrinth* if load is successful and will throw a runtime_error otherwise. save_answer will write a solution file; a solution looks like the map from the map file but contains @ characters on the path that you found. For instance, one possible output for the above map file would be:

@@@##
.#@@@
...#@

If there is no solution, the save_answer function will write a file containing no @ symbols. Solutions to the labyrinth are given in the .solution.txt files in the test_data directory.

Your program will take three command-line arguments:

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

For instance, the following is a run of your program you might want to try:

./labyrinth test_data/easy.map test_output/easy.solution.txt depth

Testing utilities (CHECK_FILES_EQUAL and RUN_MAIN) have been provided in this lab in the same style as before.

Memory

Your program is required to run without any memory leaks or errors; you must free up all of the memory that you allocate and you must only use memory that you have allocated and initialized. We will use valgrind to determine if you have done this correctly, so you should as well. You should also consider using valgrind to find bugs in your program as you proceed; it’s one of two very powerful C++ debugging tools that we’ve discussed.

Coding Style Requirements

You are required to observe some good coding practices:

• 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 this image object to a file.
       * @param file The already-open stream into which this image should be written.
       * @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(ofstream& file);
  
  // Bad
  public:
      int save(ofstream& file);
  

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

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 points on your lab. Please don’t forget!

Summary of Requirements

When you are finished, you should have

• Completed implementations of CircularArrayList, CircularArrayStack, and CircularArrayQueue
• Tests for these data structures
• A working Labyrinth class
• A labyrinth_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
• A completed peer review