Program Input

You must help Letterman navigate through the Spell Binder’s word traps. You will be given a starting and ending word, and a dictionary to search. The starting and ending words, and any other necessary flags, will be given on the command line when the program is run.

Input file format (The Dictionary)

The program gets its dictionary from standard input (cin). The dictionary can be in a file, and you redirect that file to cin when you run the program (details later). There are two different types of dictionaries that the program needs to be compatible with: complex (C) and simple (S).

For both dictionaries, the first line will be a single character specifying the dictionary type 'C' or 'S'. Unlike the output mode, which is given on the command line (see below), this is part of the file. The second line will be a single positive integer N indicating the number of lines in the dictionary not counting the first line and lines that are comments (i.e. for simple dictionaries, the number of words, and for complex dictionaries, the number of word-generating lines).

Comments may also be included in any input file. Comment lines begin with "//" (without quotes) in column 1, and are allowed anywhere in the file after the second line. When developing your test files, it is good practice to place a comment on line 3 describing the nature of the dictionary in the test file. Any dictionaries with noteworthy characteristics for testing purposes should also be commented. You should discard all existing comments from the input file; do not save them in memory as part of your data structures.

Additionally, there may be extra blank/empty lines at the end of any input file: your program should ignore them. If you see a blank line in the file, you may assume that you have hit the end.

Simple Dictionary

The first type of dictionary that your program needs to handle is the simple dictionary. This is a simple text file specifying the words in the dictionary, one word per line. Each “word” will be a sequence of alphabetic characters.

Each word in the dictionary is unique; there will never be two copies of the same word.

Here is a valid input file:

S

10

// Just a short example dictionary. Although these words // are in alphabetical order, that is not required.

chip

chop

junk

leet

let

shin

ship

shop

shot

stop

Complex Dictionary

The second type of dictionary that your program needs to handle is a complex dictionary. Like the simple dictionary, there will be one string per line. However, in this dictionary, each line could be a simple alphabetic string, like the simple dictionary, or it could contain special characters. If a line contains special characters, then it will be used to generate alphabetic words that are a part of the dictionary. Each line will contain at most one special character(except in the case of insert-each, where a pair of square brackets counts as one special character).

Here are the special characters that may be included:

- Reversal (&): If an ampersand appears at the end of the word, then both the word and

the reversal of the word are generated, in that order. An ampersand will not appear in the middle of a word.

- Example: “desserts&” - “desserts” and “stressed” are generated, in that order

- Insert-each ([]): If a set of characters appears inside square brackets, each character

is inserted into the word, generating N words in the order of the letters, where N is the number of characters within the square brackets. There will not be square brackets without letters within them and there will not be duplicate letters.

• - Example: “tre[an]d” - “tread” and “trend” are generated, in that order
• - Example: “c[auo]t” - “cat”, “cut”, and “cot” are generated, in that order
• - Swap (!): If an exclamation point appears after two characters, then the original string
• and the string with the two previous characters swapped are generated, in that order. An exclamation point will only occur if at least two characters precede it.
• - Example: “bar!d” - “bard” and “brad” are generated
• - Double (?): If a question mark appears after one character, then the original string and
• the string with the one previous character doubled are generated, in that order. A question mark will only occur if at least one character precedes it.
• - Example: “le?t” - “let” and “leet” are generated