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.

Two classes are provided in starter code here: Maze and UnionFind. UnionFind is an implementation of the union/find data structure which uses an array to represent the equivalence class "uptrees", and Maze is 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 (MSS) 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 (or not -- your call)
• Random number SEED is an integer which makes random number sequences repeatable. If you want variability during testing, write "C" here instead to use the clock to automatically set a different seed for each run

2. Programming tasks

• [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 U's methods find() and union_sets() in knock_down_all_walls() so that U IS updated after each wall is removed (this is method "A" in the MSS).
  • Take a look at the helper functions in maze.hh called UF_index_to_rowcol() and rowcol_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] Fill in knock_down_til_solvable() in main.cpp (methods "S").
• [1 point] Fill in knock_down_til_solvable_no_loops() in main.cpp (method "SNL")
• [1 point] Fill in knock_down_til_all_connected in main.cpp (method "SNLAC")
• [1 point] 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++).

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)