Solo MP This MP, as well as all other MPs in CS 225, are to be completed without a partner.
You are welcome to get help on the MP from course staff, via open lab hours, or Piazza!
Goals and Overview
In this MP you will:
- Implement the disjoint sets data structure.
- Create a program to generate random mazes.
- Applying a BFS traversal to a maze structure
- Represent a maze and its solution on a
PNG
.
Checking Out the Code
You can find the code for all our released assignments at the following public git repo.
You can either clone this or pull a zip file of the repo to your local computer. All the files for this MP are in the mp_mazes
directory. You should copy that directory into the directory you setup for your docker container.
Preparing Your Code
This semester for MPs we are using CMake rather than just make. This allows for us to use libraries such as Catch2 that can be installed in your system rather than providing them with each assignment. This change does mean that for each assignment you need to use CMake to build your own custom makefiles. To do this you need to run the following in the base directory of the assignment. Which in this assignment is the mp_mazes
directory.
mkdir build
cd build
This first makes a new directory in your assignment directory called build
. This is where you will actually build the assignment and then moves to that directory. This is not included in the provided code since we are following industry standard practices and you would normally exclude the build directory from any source control system.
Now you need to actually run CMake as follows.
cmake ..
This runs CMake to initialize the current directory which is the build
directory you just made as the location to build the assignment. The one argument to CMake here is ..
which referes to the parent of the current directory which in this case is top of the assignment. This directory has the files CMake needs to setup your assignment to be build.
At this point you can in the build directory run make as described to build the various programs for the MP.
You will need to do the above once for each assignment. You will need to run make
every time you change source code and want to compile it again.
Assignment Requirements
These are strict requirements that apply to both parts of the MP. Failure to follow these requirements may result in a failing grade on the MP.
- You are recommended to add descriptive comments throughout coding the MP. This will assist you in debugging process.
- You must name all files, public functions, public member variables (if any exist), and executables exactly as we specify in this document.
- Your code must produce the exact output that we specify: nothing more, nothing less. Output includes standard and error output and files such as Images.
- Your code must compile on the EWS machines using
clang++
. Being able to compile on a different machine is not sufficient. - Your code must be submitted correctly by the due date and time. Late work is not accepted.
- Your code must not have any memory errors or leaks for full credit.
- Your public function signatures must match ours exactly for full credit.
If using different signatures prevents compilation, you will receive a zero.
Tests for
const
-correctness may be performed separately from the other tests (if applicable).
Assignment Description
You will be implementing a Disjoint
set data structure and then implementing
a random maze generator and solver. The assignment is broken up into the two
following parts:
As usual, we recommend implementing, compiling, and testing the functions in Part 1 before starting Part 2. Submission information is provided for each part in the respective sections below.
Part 1: The DisjointSets
data structure
The DisjointSets
class should be declared and defined in dsets.h
and
dsets.cpp
, respectively. Each DisjointSets
object will represent a family
of disjoint sets, where each element has an integer index. It should be
implemented with the optimizations discussed in lecture, as up-trees stored in
a single vector
of int
s. Specifically, use path compression and
union-by-size. Each element of the vector represents a node. (Note that this
means that the elements in our universe are indexed starting at 0.) A
nonnegative number is the index of the parent of the current node; a negative
number in a root node is the negative of the set size.
Note that the default compiler-supplied Big Three will work flawlessly because
the only member data is a vector<int>
and this vector should initially be
empty.
The addelements
function
See the Doxygen for this function.
The find
function
See the Doxygen for this function.
The setunion
function
See the Doxygen for this function.
The size
function
See the Doxygen for this function.
Testing Part 1
The following command can be used to compile the DisjointSets
test
executable:
make testdsets
The following command can be used to run the test executable:
./testdsets
Provided Catch test cases are available as well by running:
make test
./test
Grading Information — Part 1
The following files are used to grade mp_mazes:
dsets.cpp
dsets.h
All other files including your testing files will not be used for grading.
Extra Credit Submission
For extra credit, you can submit the code you have implemented and tested for part one of mp_mazes. You must submit your work before the extra credit deadline as listed at the top of this page. See Handing in Your Code for instructions.
Part 2: The SquareMaze
random maze generator and solver
The SquareMaze
class should be declared and defined in maze.h
and
maze.cpp
, respectively. Each SquareMaze
object will represent a
randomly-generated square maze and its solution. Note that by “square maze”
we mean a maze in which each cell is a square; the maze itself need not be a
square. As always, we recommend reading the whole specification before
starting.
setWall
and canTravel
You should triple check that setWall
and canTravel
function exactly
according to their descriptions. An error in these two functions will not be caught by making
your own mazes but can cost you a majority of the points during grading.
Videos
The makeMaze
function
See the Doxygen.
The canTravel
function
See the Doxygen.
The setWall
function
See the Doxygen.
The solveMaze
function
This should be completed using BFS. Do not use DFS since due to the structure of mazes having very long paths it has been known to fail on some test cases running out of memory. Though these are recursive algorithms the solution should not implement them recursively.
See the Doxygen.
The drawMaze
function
See the Doxygen.
The drawMazeWithSolution
function
See the Doxygen.
Testing Part 2
Square Maze Testing
Since your mazes will be randomly generated, we cannot provide you with any
sample images to diff against. However, we have provided you with all four
possible 2x2 mazes. If you have your program create and solve a 2x2 maze, the
resulting image (with solution) should match one (and only one) of the provided
images m0.png
, m1.png
, m2.png
, and m3.png
. We strongly suggest that you
diff against these to make sure that you have formatted the output image
correctly.
We provide some basic code to test the functionality of SquareMaze
.
The following command can be used to compile the SquareMaze
test executable:
make testsquaremaze
The following command can be used to run the test executable:
./testsquaremaze
You can compare the console output of your program with the expected by
comparing it with the file soln_testsquaremaze.out
.
Catch Test Suite
Additional unit tests similar to how we will grade your MP are provided for you in tests/test_part2.cpp
. Once you have completed Part 2, you may uncomment the Part 2 tests and re-compile to include Part 2 tests:
// uncomment test_part2.cpp
make test
./test
Runtime Concerns
You should strive for the best possible implementation. This MP can be
implemented so that the given testsquaremaze.cpp
runs in less than a quarter
of a second on the EWS linux machines. To have a high probability of finishing
within the time constraints of the grading script, make sure you can run the
given testsquaremaze.cpp
in under 3 seconds on an unencumbered machine. You
can time mp_mazes by running the command time ./testsquaremaze
.
Grading Information — Part 2
- We will use
canTravel
to reconstruct your randomly generated maze in our own maze class, to check that it’s a tree and to compare your implementation to a correct implementation of this MP. This will requireheight*width*2
calls tocanTravel
. Therefore, it is very important thatcanTravel
works, and works quickly (constant time). If it doesn’t work, you will lose a lot of points. - We will use
setWall
to replace your maze with our own, for the purpose of testing all of your other functions independently of yourcreateMaze
.
setWall
and canTravel
You should triple check that setWall
and canTravel
function exactly
according to spec, as an error in these functions will not be caught by making
your own mazes but can cost you a majority of the points during grading.
The following files are used to grade mp_mazes:
dsets.cpp
dsets.h
maze.cpp
maze.h
All other files will not be used for grading.