CISC220 F2023 Lab9

Lab #9

1. Word graphs

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 wordgraph executable is called as follows: wordgraph <dictionary> <command> <0, 1, or 2 command parameters. Commands and their parameters are explained below:

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

2. Programming tasks

These are core functions that are required but not directly tested. Every print function should either call one of these or use data structures it has modified.

• calculate_neighbor_words()
• DFS_traversal(string &)
• BFS_traversal(string &)

These functions will be directly tested:

• [0.5 points] print_num_neighbors()
• [0.5 points] print_neighbors()
• [1 point] DFS_print_connected(string &, string &)
• [1 point] DFS_print_num_connected(string &)
• [1 point] BFS_print_path()
• [0.5 points] BFS_print_path_length()
• [0.5 points] BFS_print_longest_path()

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)