Goal Develop and implement a word ladder finder. Details A word ladder (aka doublet) is a...

Transcribed Image Text:

Goal Develop and implement a word ladder finder. Details A word ladder (aka doublet) is a type of puzzle created by Charles Dodgson (aka Lewis Carroll) in the 1800s. The premise of the puzzle is to "convert" one word into the other by a sequence of single-letter changes, with each change generating a valid English word. For example, you can change beer into wine via the sequence beer-beet - bent - lent-lint-line - wine. There may be other ladders for these words as well. Your program should begin by reading words from the file sgb-words.txt; the file consists of 5757 words used to test the Stanford GraphBase. Note that all words have exactly five letters. Each word should have two values connected to it: • A pointer to a word (and its connected data) • A linear list of pointers to other words Initialize the pointer for each word to NULL. Then, examine each pair of words- there are 16 568 646 such pairs. If the pair has a Hamming distance of 1, then add each word-a pointer to the word, actually to the other word's list. Read two five-letter words from the keyboard. Find both words in the word list. If either word is not in the list, stop and output that no word ladder exists. Otherwise, do the following algorithm. Preconditions w₁ and we are words in the word list Postconditions S contains a word ladder from w₁ to W₂ 1: procedure GENLADDER(W₁,W₂) Clear S 2: Add W₂ to a queue Q while Q is not empty do Dequeue Q into w 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: for each word v in w.list do if v.ptr = NULL then v.ptr - w Enqueue v in Q end if end for end while if w₁.ptr NULL then Append W₁ to S ww₁.ptr while w # NULL do Append w to S ww.ptr 16: 17: 18: 19: 20: 21: end procedure end if end while After running the algorithm, if S is empty then there is no ladder. Otherwise, display the contents of S in order to obtain the ladder. What to turn in Turn in your source code and Makefile. If you are using an IDE, compress the folder containing the project and submit that. Goal Develop and implement a word ladder finder. Details A word ladder (aka doublet) is a type of puzzle created by Charles Dodgson (aka Lewis Carroll) in the 1800s. The premise of the puzzle is to "convert" one word into the other by a sequence of single-letter changes, with each change generating a valid English word. For example, you can change beer into wine via the sequence beer-beet - bent - lent-lint-line - wine. There may be other ladders for these words as well. Your program should begin by reading words from the file sgb-words.txt; the file consists of 5757 words used to test the Stanford GraphBase. Note that all words have exactly five letters. Each word should have two values connected to it: • A pointer to a word (and its connected data) • A linear list of pointers to other words Initialize the pointer for each word to NULL. Then, examine each pair of words- there are 16 568 646 such pairs. If the pair has a Hamming distance of 1, then add each word-a pointer to the word, actually to the other word's list. Read two five-letter words from the keyboard. Find both words in the word list. If either word is not in the list, stop and output that no word ladder exists. Otherwise, do the following algorithm. Preconditions w₁ and we are words in the word list Postconditions S contains a word ladder from w₁ to W₂ 1: procedure GENLADDER(W₁,W₂) Clear S 2: Add W₂ to a queue Q while Q is not empty do Dequeue Q into w 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: for each word v in w.list do if v.ptr = NULL then v.ptr - w Enqueue v in Q end if end for end while if w₁.ptr NULL then Append W₁ to S ww₁.ptr while w # NULL do Append w to S ww.ptr 16: 17: 18: 19: 20: 21: end procedure end if end while After running the algorithm, if S is empty then there is no ladder. Otherwise, display the contents of S in order to obtain the ladder. What to turn in Turn in your source code and Makefile. If you are using an IDE, compress the folder containing the project and submit that.

Answer rating: 100% (QA)

maincpp include WordLadderh include using namespace std int main string dictFile wordBegin wordEnd outFile cout Enter the name of the dictionary file cin dictFile cout endl cout Enter the name of the ... View the full answer