CISC220 F2023 Lab7

Lab #8

1. Maze generation using union/find

As mentioned in class on Oct. 24 and more fully discussed on Oct. 26, the union/find data structure can be used to generate rectangular mazes using grid cells as the set elements and connectivity as the equivalence relation. Three approaches were outlined:

• Knock down random walls one at a time until the START and FINISH are connected. Nothing else is considered
• Same as above, but now only knock down a wall if the cells on either side of it are NOT already connected
• Same as above, but only stop on the condition that the maze is solvable AND that every cell in it is connected to every other cell

Two classes are provided in starter code here: Maze and UnionFind. UnionFind is a stub for the union/find data structure which uses an array to represent the equivalence class trees, and Maze is just a data structure to represent and draw N x M grids with walls (see the comments in maze.hh for details). A sample 3 x 4 maze is shown below:

#########
#S|     #
# +-+ + #
#   | | #
# +-+ +-#
#      F#
#########

The maze executable takes a single command-line maze specification string in the form ROWS_COLS_METHOD_SMART_PATH_DEBUG_SEED that sets maze parameters and other options as follows:

• ROWS and COLS should be positive integers
• METHOD = A : Knock down walls randomly until ALL gone
• METHOD = S : Knock down walls until SOLUTION is found (start and finish are connected)
• METHOD = SNL : Same as S, but make sure cells on each side of wall to be removed are not already connected, ensuring NO LOOPS
• METHOD = SNLAC : Same as SNL, but keep going until cells are ALL CONNECTED to each other
• SMART, PATH, and DEBUG are T or F, where SMART enables smart union, PATH enables path compression, and you can use debug to turn on extra printing
• Random number SEED is an integer or write C to use the clock for a different seed each time

You have several programming tasks:

• [0.5 points] Fill in the find(), union_sets(), and union_sets_by_size() functions in unionfind.hh. All of these functions were given in class (the last two were called union() and union_by_size(), but union is a reserved keyword in C++).
• [1 point] There's a starter function called knock_down_all_walls() already provided in main.cpp. This simply knocks down random walls one at a time until they're all gone, drawing the current "maze" M after each step. The union/find data structure U which is associated with M is NOT updated, however. Fill in appropriate calls to find() and union_sets() in knock_down_all_walls() so that U IS updated after each wall is removed (this is called "option 1" in the code).
  • Take a look at the helper functions in maze.hh called UF_index_to_rowcol() and row_to_UF_index() for going back and forth between referring to a grid cell by its row and column vs. by its index in the union/find array.
• [1 point] Write knock_down_til_solvable in main.cpp (first bullet above, but "option 2" in the code).
• [1 point] Write knock_down_til_solvable_better in main.cpp (second bullet above, "option 3" in the code)
• [0.5 points] Write knock_down_til_all_connected in main.cpp (last bullet above, "option 4" in the code)

2. Testing

• [0.5 points] Show sample mazes generated by YOUR solutions to options 2, 3, and 4 for the 5 x 5 default option and something larger, like 8 x 16. You do not need to show intermediate versions of the mazes as they are generated--just the final version.
• [0.5 points] Generate (but don't show) a 100 x 100 maze 10 times using option 4, WITH and WITHOUT smart union. What is the min, max, and average height of the one remaining equivalence class tree over those 10 runs (again, with and without smart union)? NOTE: height is not the same as size! You will need to write your own function to compute the height of your final tree

3. Submission

Submit 3 files to Gradescope: (1) your README, (2) your modified unionfind.hh, and (3) your modified main.cpp. The README should contain your name and your partner's name, notes on any limitations or issues with your code, and your interpretation of any ambiguities in the assignment instructions. Both code files should also contain your name(s)