Difference between revisions of "CISC220 F2023 Lab9"

From class_wiki
Jump to: navigation, search
(Created page with "==Lab #9== ===1. Word graphs === Two classes are provided in starter code [https://drive.google.com/file/d/13Ik1VIwu0HB8n7hV4iwAxc29OpzvlsLk/view?usp=sharing here]: <tt>Ma...")
 
(→‎1. Word graphs)
 
(31 intermediate revisions by the same user not shown)
Line 3: Line 3:
 
===1. Word graphs ===
 
===1. Word graphs ===
  
 +
Starter code for a <tt>WordGraph</tt> class is provided [https://drive.google.com/file/d/1KqoUTb_03A0bFuP022q5K_6MMorD2Dln/view?usp=sharing here] which reads in words (all the same length) from a dictionary.  As detailed in class on Nov. 9, the ''vertices'' in this graph are words (strings) that are all the same length, and an ''edge'' exists between two words <tt>w1</tt> and <tt>w2</tt> if and only if they differ by exactly one character.  For example, there is an edge between the strings ''dog'' and ''fog'' because the characters at index 0, ''d'' and ''f'', are different while the rest of the strings are the same.  Conversely, there is NOT an edge between ''dog'' and ''cot'' because they differ at two character indices, 0 and 2.
  
 +
The following dictionaries are supplied in the link above:
  
−
Two classes are provided in starter code [https://drive.google.com/file/d/13Ik1VIwu0HB8n7hV4iwAxc29OpzvlsLk/view?usp=sharing here]: <tt>Maze</tt> and <tt>UnionFind</tt>.  <tt>UnionFind</tt> is an implementation of the union/find data structure which uses an array to represent the equivalence class "uptrees", and <tt>Maze</tt> is a data structure to represent and draw N x M grids with walls (see the comments in <tt>maze.hh</tt> for details). 
+
* <tt>twos.txt</tt> 107 2-letter English words
 +
* <tt>threes.txt</tt> 1005 3-letter English words
 +
* <tt>fours.txt</tt> 3130 4-letter English words
 +
* <tt>fives.txt</tt> 5757 5-letter English words
 +
* <tt>toy.txt</tt> 10 5-letter English words
  
−
The <tt>wordgraph</tt> executable is called as follows: <tt>wordgraph <dictionary> <command> <0, 1, or 2 command parameters</tt>.  Commands and their parameters are explained below:
+
Five key data structures are declared in <tt>WordGraph</tt> and should be used by the functions 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 <tt>M->print()</tt> and <tt>U->print_horizontal()</tt> right before <tt>main()</tt> 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
+
* <tt>set<string> word_set</tt>: Stores all words read from the dictionary (which should be the same length). This is initialized for you in the constructor
 +
* <tt>map<string, set<string>> word_neighbors_map</tt>: Keys are words, values are sets of neighbor words. This is initialized by repeated calls to <tt>calculate_neighbor_words()</tt>
 +
* <tt>map<string, bool> word_visited_map</tt>: Scratch data structure for DFS
 +
* <tt>map<string, int> word_distance_map</tt>: Scratch data structure for BFS
 +
* <tt>map<string, string> word_path_map</tt>: Scratch data structure for DFS/BFS.  Keys are words, values are words visited JUST BEFORE key during DFS/BFS
  
−
====3_4_S_F_F_F_3====
+
The executable is called as follows: <tt>wordgraph <dictionary> <command> <0, 1, or 2 parameters</tt>>.  Commands and their parameters are explained below:
  
−
#########
+
* <tt>NUM_NEIGHBORS w</tt>: Print number of neighbors of word <tt>w</tt>
−
#S    | #
+
* <tt>NEIGHBORS w</tt>: Print all neighbors of word <tt>w</tt>, one per line
−
# + + +-#
+
* <tt>CONNECTED w1 w2</tt>: Using DFS, print "CONNECTED" if <tt>w1</tt> and <tt>w2</tt> are connected, "NOT CONNECTED" otherwise
−
# |  | #
+
* <tt>NUM_CONNECTED w</tt>: Using DFS, print number of words that are connected to <tt>w</tt>.  <tt>w</tt> itself counts as 1
−
# + +-+ #
+
* <tt>PATH_LENGTH w1 w2</tt>: Using BFS, print length of shortest path connecting <tt>w1</tt> and <tt>w2</tt>.  If they are not connected, print "NOT CONNECTED"
−
#      F#
+
* <tt>PATH w1 w2</tt>: Using BFS, print sequence of words on that path (one per line starting with <tt>w1</tt> and ending with <tt>w2</tt>).  If they are not connected, print "NOT CONNECTED"
−
#########
+
* <tt>LONGEST_PATH</tt>: Using BFS, test all possible pairs of words and print length of longest shortest path, then the pair of words on their own lines.  This can take seconds to minutes depending on the size of the dictionary, so for grading only small dictionaries will be used.
−
 
−
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====
+
If any word is not in the dictionary selected, print "ERROR" and nothing else.
  
−
#########
+
===2. Programming tasks===
−
#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====
+
These are core <tt>WordGraph</tt> functions that are required but not directly tested.  Since they don't generate output but have side effects on the data structures above, every print function should either call one of these or use the modified data structure(s).
  
−
#########
+
* <tt>calculate_neighbor_words(string &)</tt>
−
#S  | | #
+
* <tt>DFS_traversal(string &)</tt>
−
# + + + #
+
* <tt>BFS_traversal(string &)</tt>
−
# |  | #
 
−
# +-+-+ #
 
−
#      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===
+
These <tt>WordGraph</tt> functions will be directly tested and correspond one-to-one with the commands listed above:
  
−
* '''[1 point]''' There's a starter function called <tt>knock_down_all_walls()</tt> already provided in <tt>main.cpp</tt>.  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 <tt>find()</tt> and <tt>union_sets()</tt> in <tt>knock_down_all_walls()</tt> so that U IS updated after each wall is removed (this function is called when method "A" is chosen in the MSS).
+
* '''[0.5 points]''' <tt>print_num_neighbors(string &)</tt>
−
** Take a look at the helper functions in <tt>maze.hh</tt> called <tt>UF_index_to_rowcol()</tt> and <tt>rowcol_to_UF_index()</tt> 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.
+
* '''[0.5 points]''' <tt>print_neighbors(string &)</tt>
−
* '''[1 point]''' Fill in <tt>knock_down_til_solvable()</tt> in <tt>main.cpp</tt> (called when method "S" is selected). 
+
* '''[1 point]''' <tt>DFS_print_connected(string &, string &)</tt>  
−
* '''[1 point]''' Fill in <tt>knock_down_til_solvable_no_loops()</tt> in <tt>main.cpp</tt> (called for method "SNL")
+
* '''[1 point]''' <tt>DFS_print_num_connected(string &)</tt>
−
* '''[1 point]''' Fill in <tt>knock_down_til_solvable_no_loops_all_connected()</tt> in <tt>main.cpp</tt> (called for method "SNLAC")
+
* '''[0.5 points]''' <tt>BFS_print_path_length(string &, string &)</tt>
−
* '''[0.5 points]''' Modify the <tt>union_sets()</tt> function in <tt>unionfind.hh</tt> to use "union by size" when U's member variable <tt>do_smart_union</tt> is True 
+
* '''[1 point]''' <tt>BFS_print_path(string &, string &)</tt>
−
* '''[0.5 points]''' Modify the <tt>find()</tt> function in <tt>unionfind.hh</tt> to use "path compression" when U's member variable <tt>do_path_compression</tt> is True
+
* '''[0.5 points]''' <tt>BFS_print_longest_path()</tt>
  
−
'''You may work with a (human) partner on this lab'''
+
'''You may use AI on any part of this lab, but no human partner.'''
  
 
===3. Submission===
 
===3. Submission===
  
−
Submit 3 files to Gradescope: (1) your README, (2) your modified <tt>unionfind.hh</tt>, and (3) your modified <tt>main.cpp</tt>.  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)
+
Submit 2 files to Gradescope: (1) your README and (2) your modified <tt>main.cpp</tt>.  The README should contain your name, complete declarations of AI use, notes on any limitations or issues with your code, and your interpretation of any ambiguities in the assignment instructions. <tt>main.cpp</tt> should also contain your name and per-function comments on AI usage.

Latest revision as of 16:45, 10 November 2023

Lab #9

1. Word graphs

Starter code for a WordGraph class is provided here which reads in words (all the same length) from a dictionary. As detailed in class on Nov. 9, the vertices in this graph are words (strings) that are all the same length, and an edge exists between two words w1 and w2 if and only if they differ by exactly one character. For example, there is an edge between the strings dog and fog because the characters at index 0, d and f, are different while the rest of the strings are the same. Conversely, there is NOT an edge between dog and cot because they differ at two character indices, 0 and 2.

The following dictionaries are supplied in the link above:

  • twos.txt 107 2-letter English words
  • threes.txt 1005 3-letter English words
  • fours.txt 3130 4-letter English words
  • fives.txt 5757 5-letter English words
  • toy.txt 10 5-letter English words

Five key data structures are declared in WordGraph and should be used by the functions below:

  • set<string> word_set: Stores all words read from the dictionary (which should be the same length). This is initialized for you in the constructor
  • map<string, set<string>> word_neighbors_map: Keys are words, values are sets of neighbor words. This is initialized by repeated calls to calculate_neighbor_words()
  • map<string, bool> word_visited_map: Scratch data structure for DFS
  • map<string, int> word_distance_map: Scratch data structure for BFS
  • map<string, string> word_path_map: Scratch data structure for DFS/BFS. Keys are words, values are words visited JUST BEFORE key during DFS/BFS

The executable is called as follows: wordgraph <dictionary> <command> <0, 1, or 2 parameters>. Commands and their parameters are explained below:

  • NUM_NEIGHBORS w: Print number of neighbors of word w
  • NEIGHBORS w: Print all neighbors of word w, one per line
  • CONNECTED w1 w2: Using DFS, print "CONNECTED" if w1 and w2 are connected, "NOT CONNECTED" otherwise
  • NUM_CONNECTED w: Using DFS, print number of words that are connected to w. w itself counts as 1
  • PATH_LENGTH w1 w2: Using BFS, print length of shortest path connecting w1 and w2. If they are not connected, print "NOT CONNECTED"
  • PATH w1 w2: Using BFS, print sequence of words on that path (one per line starting with w1 and ending with w2). If they are not connected, print "NOT CONNECTED"
  • LONGEST_PATH: Using BFS, test all possible pairs of words and print length of longest shortest path, then the pair of words on their own lines. This can take seconds to minutes depending on the size of the dictionary, so for grading only small dictionaries will be used.

If any word is not in the dictionary selected, print "ERROR" and nothing else.

2. Programming tasks

These are core WordGraph functions that are required but not directly tested. Since they don't generate output but have side effects on the data structures above, every print function should either call one of these or use the modified data structure(s).

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

These WordGraph functions will be directly tested and correspond one-to-one with the commands listed above:

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

You may use AI on any part of this lab, but no human partner.

3. Submission

Submit 2 files to Gradescope: (1) your README and (2) your modified main.cpp. The README should contain your name, complete declarations of AI use, notes on any limitations or issues with your code, and your interpretation of any ambiguities in the assignment instructions. main.cpp should also contain your name and per-function comments on AI usage.

Retrieved from "http://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2023_Lab9&oldid=3290"