This is a two-part lab:
Note: This is a two-part, two-week lab assignment. However, the lab is due in three weeks because of spring break. This lab is not designed to make you work over spring break, nor are you expected to. There is however two weeks worth of work in this lab, and we do expect you to work on it this week. Plan accordingly.
As with most assignments for the rest of the semester, you will be working with a partner. Both partners should be present and working on the code together. You will both be responsible for understanding all concepts, so dividing and conquering is not an option. The academic integrity policy applies to the entire pair; you cannot work or share code with anyone outside your partner.
You and your lab partner will share the same git repository,
which is named lab05-<user1>-<user2>.git
.
Please access your lab by cloning the appropriate git
repository, e.g.:
$ git clone git@github.swarthmore.edu:CS35-S18/lab05-mgagne1-lmeeden1.gitYou can also get the ssh git url from CS35 github org. For this lab, we also are hosting several test files. Instead of giving everyone identical copies of the somewhat large files, you will create a symbolic link to the folder containing the files.
$ cd ~/cs35/lab05 $ ln -s /usr/local/doc/lab05-data/ ./test_data
In this lab, you will implement two search algorithms—depth-first search and breadth-first search—for finding a path through a maze.
Algorithm MazeSearch: mark Start as visited add Start to DataStructure while (DataStructure is not empty): Current = remove location from DataStructure if (Current == Destination): // found a path! build the Path found return Path else for each Neighbor of Current: if Neighbor not visited: mark Neighbor visited process Neighbor add Neighbor to DataStructure return no Path existsThe 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.
/usr/local/include/cs35/
, the same
directory as last week. You can have a look at the ADTs for stacks and queues here.stlList.h, stlQueue.h, stlStack.h
in the directory above. You will not have to implement a Stack or Queue 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.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.test_data
: a directory containing several maze files. The format is described below.tests.cpp
: a collection of unit tests for your maze program.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, e.g.,
/* ADTs */ #include <cs35/List.h> #include <cs35/Stack.h> /* Implementations */ #include <cs35/stlList.h> #include <cs35/stlStack.h> int main(){ List<int>* list = new STLList<int>; STLStack<int> stack; }
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 test_data
directory. A map file contains
the following information:
5 3 .#.#. .#... ...#.We have given you the code which loads files in this format; this explanation is just for reference.
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, X increases as you move right, Y increases as you move down), whether that position is a wall, and some fields which will be used during the search to construct an appropriate path through the maze. The constructor of the Position class should take the X and Y coordinate values and initialize the other fields to suitable default values (like nullptr or false).
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.
solveDepthFirstSearch
and solveBreadthFirstSearch
—which are very similar.
These methods will return a ListYou 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.
At the end of the loop, you can determine whether a path has been found by looking at the exit position and seeing if it has been visited. If so, you just need to follow the previous position pointers backward until you reach the start. This gives you the path to take (in reverse order). If the exit position has not been visited, then there is no possible path through the maze.
Some of the 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 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.
main
should be less work than the Maze
class. It just
involves something 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 CS35 lab 05: The A-Maze-ing Race.
where is your maze file? test_data/cycle.map
Which search algorithm to use (BFS or DFS)? DFS
@@###
#@@@#
#.#@#
#..@@
####@
Invalid Inputs: Your maze
program should
gracefully handle the following cases of invalid input:
WrittenLab.tex
which
contains the problems below. For further details about LaTeX, see the
file LearningLaTeX.tex
.
function maxEven(A,n): max = -infinity for i = 0..n-1: if A[i] > max and A[i] is even then: max = A[i] end if end for return max end function
Give a method to determine the three fastest dachshunds. What is the minimum number of races you need to arrange?
// good int *array = new int[size]; // bad int *a = new int[size];
//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.
//good if(condition) { cout << "Something" << endl; } //legal but bad if(condition) cout << "Something" << endl;
/** * 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;
These additional features are optional – we'll look at them, but they won't be for credit. Make sure you complete and push both parts of the main lab before starting any extra challenge, and note in your README file that you've done extra challenges so the graders know which version of your lab to grade. (There's a chance your added features will break our grading scripts; we'll grade the base version of your lab to ensure you don't get penalized in the off-chance your extra features break our grading scripts)
To summarize the requirements of this lab:
Once you are satisfied with your code, hand it in using git. Remember the add, commit, push development cycle. You can push as many times as you like, but only the most recent submission will be graded. You may want to run git status to confirm all modifications have been pushed.