Goal Develop and implement a word ladder finder. Details A word ladder (aka doublet) is a...
Fantastic news! We've Found the answer you've been seeking!
Question:
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.
Expert Answer:
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
Related Book For
Posted Date:
Students also viewed these electrical engineering questions
-
The project for SITXFSA004 Develop and implement a food safety plan consists of 2 parts, Part A and Part B. Part A requires you to review any existing food safety plan as this may exist in your...
-
A company is planning to develop and implement a new computerized purchase order system in one of its manu- facturing subsidiaries. The vice president of manufacturing has requested that internal...
-
Design and implement a word unscrambler game in Java. Instructions Your program should read in a random word from a file calledwords.txt (note the lack of capitalization) that you provide. Thefile...
-
11. What is the Specific Gravity of Zinc ? 12. The barometric pressure for the day is 14.7 psi. The hangar shop air tank gage reads 120 psi. What is the absolute pressure inside the shop air tank? =...
-
During the Asian crisis, some local firms in Asia borrowed U.S. dollars rather than local currency to support local operations. Why would they borrow dollars when they really needed their local...
-
Describe the business culture in Egypt.
-
Who is the father of the term forensic accounting? a. Max Lourie b. James McCleland c. Maurice E. Peloubet d. Robert Lindquist e. Someone else
-
The budget director of Jupiter Helmets Inc., with the assistance of the controller, treasurer, production manager, and sales manager, has gathered the following data for use in developing the...
-
Tools Ch 11-Assignment The Basics of Capital Budgeting 1. Net present value (NPV) Evaluating cash flows with the NPV method The net present value (NPV) rule is considered one of the most common and...
-
Trickle bed reactors is widely used in the oil industry because of the advantages offered. In a trickle bed reactor, the oxidation of ethanol is to be carried out. The reaction is first order with...
-
Many novelists have agents who represent them to publishing houses. Novelists first approach agents by writing query letters that describe unpublished novels they have written. Query letters should...
-
Regarding GAAP and accrual vs. cash basis accounting. Which method is the most reliable financial results? Why? Which method will provides the most reliable financial results? Accrual basis is...
-
A 4.00-g copper coin at 22.5C drops 55.0 m to the ground. (a) Assuming 55.0% of the change in gravitational potential energy of the coin-Earth system goes into increasing the internal energy of the...
-
Multiply. (10+5)(3/6+2)
-
Kaspar Industries expects credit sales for January, February, and March to be $211,000, $270,600, and $315,300, respectively. It is expected that 75% of the sales will be collected in the month of...
-
The standard cost of product 5252 includes 1.90 hours of direct labor at $13.70 per hour. The predetermined overhead rate is $22.00 per direct labor hour. During July, the company incurred 4,000...
-
Exercise 13-15 (Algo) Dropping or Retaining a Segment [LO13-2] Thalassines Kataskeves, S.A., of Greece makes marine equipment. The company has been experiencing losses on its bilge pump product line...
-
A researcher reports a significant two-way between-subjects ANOVA, F(3, 40) = 2.96. State the decision to retain or reject the null hypothesis for this test.
-
Most pressure to legislate and enforce copyright laws for software has come from North America and Western Europe and not from other parts of the world. Why?
-
1. Some Web sites are not very useful, functional, or well organized. Why do you believe that Web sites are approached differently than other software development initiatives? What did Wells Fargo do...
-
What are the potential risks of a single organization controlling much of the market for essential software?
-
Pop Ltd buys 100 per cent of the shares of Sibling Ltd on 31 December 2002. The balance sheets of the two companies on 31 December 2003 are as shown. You are to draw up a consolidated balance sheet...
-
Dad and Mum Ltd bought 60 per cent of the shares of Child 1 and 2 Ltd on 31 March 2004. The balance sheets of the two companies on 31 March 2005 are as follows. You are to draw up a consolidated...
-
Papai Ltd bought 51 per cent of the shares in Sons and Co Ltd on 31 October 2007. From the following balance sheets you are to draw up the consolidated balance sheet as at 31 October 2008. Papai...
Study smarter with the SolutionInn App