Partner MP

MP7 is a partner MP!

  • Part 1 and Part 2 of this MP can be completed with a partner!
  • The creative “Part 3” must be completed by yourself and must be unique (and different from your partner’s work).

You should denote who you work with in the PARTNERS.txt file in mp7. If you worked alone, include only your NetID in PARTNERS.txt.

Goals and Overview

In this MP you will:

A solved maze.

A solved maze.

Checking Out the Code

From your CS 225 git directory, run the following on EWS:

git fetch release
git merge release/mp7 -m "Merging initial mp7 files"

If you’re on your own machine, you may need to run:

git fetch release
git merge --allow-unrelated-histories release/mp7 -m "Merging initial mp7 files"

The mp7 directory will contain sample output including all 4 possible 2x2 mazes and one 50x50 maze. We encourage you to test your code by writing your own main.cpp that uses your classes in different ways.

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.

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 MP 7.1 before starting MP 7.2. Submission information is provided for each part in the respective sections below.

MP 7.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 ints. 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 MP 7.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 — MP 7.1

The following files are used to grade MP7:

All other files including your testing files will not be used for grading.

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

Videos

The makeMaze function

See the Doxygen.

The canTravel function

See the Doxygen.

The setWall function

See the Doxygen.

The solveMaze function

See the Doxygen.

The drawMaze function

See the Doxygen.

The drawMazeWithSolution function

See the Doxygen.

Testing MP 7.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.

MP 7.3: A Final Creative Component

Solo Portion

This creative part of the MP must be completed individually and must be significantly different from your partner’s creative work.

Similar to Part 2 of this MP, we are leaving the design of the creative component completely up to you!

Use main.cpp to generate a file, creative.png, that contains a creative maze. The only requirement is that this maze must not be a square maze similar to Part 2. For example, what if your maze was a circle? Or in the shape of a block I? What if you maze made us of ideas from MP1, MP2, MP4, or MP5? Be creative. Have fun.

As you complete Part 3, ensure that your Part 2 still continues to function as described. This means you may need to add a drawCreativeMaze() function instead of modifying your drawMazeWithSolution() or other function. You should find many of your existing helper functions still useful.

Sharing your maze:

You just made an amazing maze, awesome work! Feel free to share it with the world!

If you use #cs225 on a public post on a Facebook, Twitter, LinkedIn on Instagram we'll make sure to or the post!

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 MP7 by running the command time ./testsquaremaze.

Grading Information — MP 7.2

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 MP7:

All other files will not be used for grading.