CISC220 F2023 Lab7

Lab #7

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

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). The start and finish cells are always in the upper-left and lower-right corners of the maze, respectively
• 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 pseudo-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

The output of the program (when DEBUG is F) should be just a representation of the final maze M and the final union-find uptree U. This happens automatically with the calls to M->print() and U->print_horizontal() right before main() returns. Sample output from solution code for various methods creating a 3 x 4 maze with the same random seed are shown below:

3_4_A_F_F_F_3

#########
#S      #
# + + + #
#       #
# + + + #
#      F#
#########

0:3, 1:0, 2:5, 3:-1, 4:0, 5:0, 6:2, 7:0, 8:0, 9:8, 10:8, 11:7

3_4_S_F_F_F_3

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

0:-1, 1:0, 2:5, 3:-1, 4:0, 5:0, 6:2, 7:0, 8:0, 9:8, 10:8, 11:7

3_4_SNL_F_F_F_3

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

0:-1, 1:0, 2:5, 3:-1, 4:0, 5:0, 6:2, 7:0, 8:0, 9:8, 10:8, 11:7

3_4_SNLAC_F_F_F_3

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

0:3, 1:0, 2:5, 3:-1, 4:0, 5:0, 6:2, 7:0, 8:0, 9:8, 10:8, 11:7

2. Programming tasks

• [1 point] There's a starter function called knock_down_all_walls() already provided in main.cpp. This simply deletes random walls, one at a time and unconditionally, until they're all gone (DEBUG = T causes M and U as well as the last wall picked to be printed after each step). M changes, but U is NOT updated in the code provided. 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 function is called when method "A" is chosen 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 (called when method "S" is selected).
• [1 point] Fill in knock_down_til_solvable_no_loops() in main.cpp (called for method "SNL")
• [1 point] Fill in knock_down_til_solvable_no_loops_all_connected() in main.cpp (called for method "SNLAC")
• [0.5 points] Modify the union_sets() function in unionfind.hh to use "union by size" when U's member variable do_smart_union is True
• [0.5 points] Modify the find() function in unionfind.hh to use "path compression" when U's member variable do_path_compression is True

You may work with a (human) partner on this lab

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)