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.
![](latex-319fb3066babd97d697bf70612a3c7f0.png)
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 inCircularArrayList
, you make it easier to find bugs in your later code. - Implement the
CircularArrayStack
andCircularArrayQueue
classes using theCircularArrayList
. This should be pretty straightforward, since you’ll useCircularArrayList
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 theLabyrinth
class which will solve the labyrinth for you. - Implement the
labyrinth_main
function. You can do this with just one ofCircularArrayStack
orCircularArrayQueue
, so you don’t have to implement everything in the order given here. As usual, make sure to test yourlabyrinth_main
function using theRUN_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 theCircularArrayList
class.test_circular_array_list.cpp
: A file where you will write tests forCircularArrayList
.
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.
- 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
- 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
![Ouroboros](ouroboros.png)
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 templatedOrderedCollection
interface. You will not change this file.stack.h
: The templatedStack
interface. You will not change this file.queue.h
: The templatedQueue
interface. You will not change this file.circular_array_stack.h
: The file in which you will write your templatedCircularArrayStack
implementation.circular_array_queue.h
: The file in which you will write your templatedCircularArrayQueue
implementation.test_circular_array_stack.cpp
: A test program in which you will test yourCircularArrayStack
.test_circular_array_queue.cpp
: A test program in which you will test yourCircularArrayQueue
.
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
![Map](map.png)
Relevant files:
position.h
/position.cpp
: APosition
class, describing a single position in the labyrinth.labyrinth.h
/labyrinth.cpp
: ALabyrinth
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 themain
function. You will not need to change this file.test_labyrinth.cpp
: A test program in which you will test yourPosition
andLabyrinth
classes as well as yourlabyrinth_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.
- Each
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
![Labyrinth](http://static.dolimg.com/lucas/movies/labyrinth_01-299728d532fa.jpg)
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
- If that neighbor has not been visited:
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:
![Well-dressed people (style)](/~zpalmer/cs35/s16/labs/style.png)
-
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 afoo
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
, andCircularArrayQueue
- 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