Due on Wednesday, October 31st 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.
We will be using Teammaker to form teams. You can log in to that site to indicate your preferred partner. Once you and your partner have specified each other, a GitHub repository will be created for your team. If you have any trouble using Teammaker, contact your instructor.
This lab comes in two parts:
maze
: A Maze SolverThe first part of this lab involves writing code for a program called maze
. This program will solve provided mazes using the depth- and breadth-first search algorithms discussed in class. To implement these algorithms, you will first need to create implementations of the Stack
and Queue
ADTs.
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, but you’ll probably want to refer to them.adts/impls/
: A directory containing reference implementations of our ADT definitions. These implementations simply act as wrappers for the C++ standard library classes.linkedQueue.h
/linkedQueue-inl.h
: The LinkedQueue
class, which you will implement.linkedStack.h
/linkedStack-inl.h
: The LinkedStack
class, which you will implement.position.h
/position.cpp
: The Position
class which keeps track of the contents in a particular 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
: Provided utility functions for the Maze
class, such as reading files and rendering solutions.main.cpp
: The program which reads a maze, solves it, and prints the result.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/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.
LinkedQueue
and LinkedStack
The LinkedQueue
and LinkedStack
classes appear in the like-named files in your starter code. As we discussed in lecture, these classes are easily implemented using a linked list; you can find a linked list implementation in the form of the STLList
class in the file adts/stlList.h
. You should proceed by implementing each of the methods marked TODO
in the files linkedQueue-inl.h
and linkedStack-inl.h
. These methods are not meant to be complex; they require very little code to complete. You do not need to throw your own exceptions from these objects’ methods since the underlying list will do so for you.
This lab includes an OrderedCollection
abstract class which describes the commonalities between queues and stacks (also as discussed in lecture). Note that e.g. LinkedQueue
is a subclass of both Queue
and OrderedCollection
, so it will need not only enqueue
and dequeue
methods but also offer
and take
methods. The offer
and take
methods can be implemented simply by calling enqueue
and dequeue
; we will rely on this commonality later to reduce the amount of code you need to write!
Once you’ve completed your LinkedQueue
and LinkedStack
implementations, run the unit tests (make tests
followed by ./tests
) to see if they are working correctly. The maze tests will fail, but all of your queue and stack tests should pass. After these tests pass, proceed to the Maze part of the lab.
Once you have completed your LinkedQueue
and LinkedStack
implementations, you are prepared to implement the search algorithms we discussed in lecture. We begin by considering how we will represent the mazes we intend to solve.
Each maze 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 maze is the upper left corner; the exit is in the bottom right.
The layout of a particular maze 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:
#
character is a wall..
character is an open space.For instance, the following is a valid map:
5 3
...##
.#...
...#.
Position
ClassWe will represent a maze as a two-dimensional grid of Position
objects. Each Position
object contains relevant information for one place in the maze: 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 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 two-dimensional grid that you create for your maze 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.
Maze
ClassA Maze
object represents our knowledge of a particular maze; we can use this information to find a path through the maze using various search strategies. This class has two public methods – solveBreadthFirst
and solveDepthFirst
– which will perform the appropriate search algorithm and return an answer. The answer is in the form of a List<Position*>*
: a pointer to a new list of positions which constitute a correct path through the maze from start to finish. These two algorithms are very similar: they only differ in which data structure they use to perform the search! Regardless of whether we are using a stack (depth first) or a queue (breadth first), the search algorithm goes as follows:
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 maze.
To avoid writing the same code twice, we can implement the above algorithm in the private method solve
. This method takes an argument of type OrderedCollection<Position*>
and uses that data structure during the search. Then, solveBreadthFirst
and solveDepthFirst
both call solve
, each providing an appropriate data structure. Your solve
method will return the list of positions that describe the correct path through the maze (or a nullptr
in the event that no such path exists).
Maze
ClassMake sure to run the provided unit tests on your code as you develop; definitely test your code once you’ve finished the Maze
class! It’ll be easier to find most bugs in your Maze
implementation by direct testing than it will be by trying to find them by hand by running the maze
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 maze. 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.
main
The implementation for main
is less work 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; it will return a Maze*
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:
$ ./maze test_data/cycle.map depth
@@###
#@@@#
#.#@#
#..@@
####@
Solutions to the provided test mazes 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:
"depth"
or "breadth"
to indicate the type of search to performIf 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.
Your maze
program should gracefully handle the following cases of invalid input:
"depth"
or "breadth"
.loadMap
).Note that you are not permitted to allow your program to crash in these cases; you must catch exceptions and print messages accordingly, using syntax similar to the following:
try {
... // do stuff
} catch (runtime_error e) {
... // handle error
}
Your program is required to run without any memory errors. Use valgrind
to determine if you have any memory errors; we will do so, and any errors reported by valgrind
will result in lost points. You should also use valgrind
as a debugging tool as you develop your program.
You are also required not to have any memory leaks, although memory leaks will be scored far more generously. You are encouraged to worry about memory leaks only after your program is working correctly. Once your program works, commit and push it and then consider making changes to solve leaks. It’s much better to have a correct, leaky program than it is to have a leak-free program that crashes.
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 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.)
For this part of your assignment, you will give written answers much in the same way as you did in Lab 4. 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 4 template for instructions on how to use LaTeX.
For this part of the lab, answer the following questions.
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, prove that the minOdd
function works perfectly. Clearly state your recursive invariant at the beginning of your proof.
Function minOdd(A,n)
If n = 0 Then
Return infinity
Else
min <- minOdd(A,n-1)
If A[n-1] < min And A[n-1] is odd Then
min <- A[n-1]
EndIf
Return min
EndIf
EndFunction
When you are finished, you should have
Maze
classmain
which provides a command-line interface to solve mazes