Difference between revisions of "CISC220 F2023 Lab9"
(→1. Word graphs) |
(→1. Word graphs) |
||
(19 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 which reads in words (all the same length) from a dictionary and | + | 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: | |
− | The executable is called as follows: <tt>wordgraph <dictionary> <command> <0, 1, or 2 | + | * <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 | ||
+ | |||
+ | Five key data structures are declared in <tt>WordGraph</tt> and should be used by the functions below: | ||
+ | |||
+ | * <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 | ||
+ | |||
+ | 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> | * <tt>NUM_NEIGHBORS w</tt>: Print number of neighbors of word <tt>w</tt> | ||
Line 13: | Line 27: | ||
* <tt>CONNECTED w1 w2</tt>: Using DFS, print "CONNECTED" if <tt>w1</tt> and <tt>w2</tt> are connected, "NOT CONNECTED" otherwise | * <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>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, | + | * <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" |
− | * <tt>PATH w1 w2</tt>: Using BFS, | + | * <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. | * <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. | ||
Line 21: | Line 35: | ||
===2. Programming tasks=== | ===2. Programming tasks=== | ||
− | These are core functions that are required but not directly tested. | + | 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()</tt> | + | * <tt>calculate_neighbor_words(string &)</tt> |
* <tt>DFS_traversal(string &)</tt> | * <tt>DFS_traversal(string &)</tt> | ||
* <tt>BFS_traversal(string &)</tt> | * <tt>BFS_traversal(string &)</tt> | ||
− | These functions will be directly tested: | + | These <tt>WordGraph</tt> functions will be directly tested and correspond one-to-one with the commands listed above: |
− | * '''[0.5 points]''' <tt>print_num_neighbors()</tt> | + | * '''[0.5 points]''' <tt>print_num_neighbors(string &)</tt> |
− | * '''[0.5 points]''' <tt>print_neighbors()</tt> | + | * '''[0.5 points]''' <tt>print_neighbors(string &)</tt> |
* '''[1 point]''' <tt>DFS_print_connected(string &, string &)</tt> | * '''[1 point]''' <tt>DFS_print_connected(string &, string &)</tt> | ||
* '''[1 point]''' <tt>DFS_print_num_connected(string &)</tt> | * '''[1 point]''' <tt>DFS_print_num_connected(string &)</tt> | ||
− | * '''[ | + | * '''[0.5 points]''' <tt>BFS_print_path_length(string &, string &)</tt> |
− | * '''[ | + | * '''[1 point]''' <tt>BFS_print_path(string &, string &)</tt> |
* '''[0.5 points]''' <tt>BFS_print_longest_path()</tt> | * '''[0.5 points]''' <tt>BFS_print_longest_path()</tt> | ||
− | '''You may | + | '''You may use AI on any part of this lab, but no human partner.''' |
===3. Submission=== | ===3. Submission=== | ||
− | Submit 2 files to Gradescope: (1) your README and (2) your modified <tt>main.cpp</tt>. The README should contain your name | + | 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.