logo CodeStepByStep logo

wordChain

Language/Type: C++ streams file input Map
Related Links:
Author: Marty Stepp (on 2016/06/16)

Write a function named wordChain that accepts two string parameters, the first representing an input filename and the second representing a starting word, and that produces a random "word chain" starting from the given word.

For this problem let's define a "word chain" as a sequence of words where the last two letters of the current word will be the first two letters of the next word. For example, here is a possible word chain that starts from the word "program":

program → amender → erected → edaciousness

The words you use in your word chain come from the given input file. You should assume that this file contains a sequence of words, one per line. Your function should open and read the contents of this input file and use those words when creating a word chain. If the file exists and is readable, you may assume that its contents consist entirely of words listed one-per-line in lowercase, and that each word in the dictionary is at least 2 letters long. For example, the file dictionary.txt might contain words in the format shown below (abbreviated by ...).

aah
aahed
...
zygoid
zygote

You are producing a random word chain, so the idea is that you should randomly choose a next word whose first two letters are the same as the last two letters of the current word. In our sample chain above, any word starting with "am" would be a valid choice for the second word; and if the second word chosen is "amender", then any word starting with "er" would be a valid choice for the third word. And so on. A word chain might have a duplicate in it; this is okay.

A word chain ends when you reach a two-letter word suffix that is not the start of any word in the dictionary. For example, in the chain shown above, we produced "edaciousness". There are no words in the dictionary that begin with "ss", so the chain ends and the function stops.

Your function should print the word chain to the console, one word per line. Here are several example outputs from the call of wordChain("dictionary.txt", "computer"); . The implication of the outputs below is that the given dictionary does not contain any words that begin with "gs", or "ss", or "ns", which is why the chains end there.

computer
erecting
ngatis
isocyanates
esthete
terminism
smug
uglying
ngati
tidings
computer
ere
reservednesses
espouse
serovar
arpeggio
iodines
eschalot
ototoxicity
tyeing
nganas
assentive
vestibule
lecherousness
computer
erotize
zecchins

Notice that the same word suffix/prefix could occur more than once in the same chain, such as "ng" in "erecting" / "ngatis" and again later in "uglying" / "ngati". If the start word passed in ends with a two-letter sequence that is not the start of any words in the input file, your function should simply print the start word and then exit.

If the file is missing/unreadable, or the start word's length is less than 2, your function should throw a string exception.

Constraints: Your solution should read the file only once, not make multiple passes over the file data. Similarly, don't store the entire file contents in a collection and loop over that entire collection multiple times. You should choose an efficient solution. Choose data structures intelligently and use them properly. You may create up to two additional data structures (stack, queue, set, map, etc.) as auxiliary storage. A nested structure, such as a set of vectors, counts as one additional data structure. (You can have as many simple variables as you like, such as ints or strings.)

Type your solution here:


This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.


Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.