Overview
The evil Spell Binder is loose, and it’s up to Letterman to save us! Letterman hasn’t been very
active lately, and his power of changing one word into another by changing only one letter
needs upgrading. Yes, in the old days he could change “night” into “light”, but can this new
Letterman 2.0 change “evil” into “good”? Only you can say!
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 a file that will be read from standard input (cin). 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'. Note that 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 wordgenerating
lines).
Note that we do not place a limit on the magnitude of N and neither should your code.
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 cases, it is good practice to place a comment on line 3 describing the
Version 122715
Current version by: David Snider and Laura Wendlandt
Originally composed by: David Paoletti
© 2016 Regents of the University of Michigan
1
nature of the dictionary in the test case. Any dictionaries with noteworthy characteristics for
testing purposes should also be commented. You should discard all existing comments from the
in
put 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:
S8/
/ Just a short example dictionary, all words of the same length.
// Although these words are in alphabetical order, that is not
// required.
chip
chop
junk
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 inserteach, 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.
Version 122715
Current version by: David Snider and Laura Wendlandt
Originally composed by: David Paoletti
© 2016 Regents of the University of Michigan
2
Example: “desserts&” both “desserts” and “stressed” are generated
Inserteach ( [] ): 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. Note that there will not be square
brackets without letters within them and that there will not be duplicate letters.
Example: “tre[an]d” “tread” and “trend” are generated
Example: “c[auo]t” “cat”, “cut”, and “cot” (but not “ct”) are generated
Optional ( ? ): If a question mark appears after a character, then the words with and
without that character are generated, in that order.
Example: “plead?” “plead” and “plea” are generated
Example: “len?d” “lend” and “led” are generated
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 following two characters.
Example: “st!ar” “star” and “tsar” are generated
Here is an example input file:
C6/
/This generates the dictionary:
//chip, chop, junk, shin, sin, ship, shop, shot, stop, pots
ch[io]p
junk
sh?in
sh[io]p
shot
stop&
Command line arguments
Your program should take the following casesensitive command line options (when we say a
switch is "set", it means that it appears on the command line when you call the program):
● stack, s : If this switch is set, use the stackbased routing scheme.
● queue, q: If this switch is set, use the queuebased routing scheme.
● change, c: If this switch is set, Letterman is allowed to change one letter into another.
● swap, p: If this switch is set, Letterman is allowed to swap any two adjacent
characters.
● length, l: If this switch is set, Letterman is allowed to modify the length of a word, by
inserting or deleting a single letter.
● output (W|M), o (W|M): Indicates the output file format by following the flag with a W
(word format) or M (modification format). If the output option is not specified, default to
word output format (W).If output is specified on the command line, the argument (either
W or M) to it is required. See the examples below regarding use.
Version 122715
Current version by: David Snider and Laura Wendlandt
Originally composed by: David Paoletti
© 2016 Regents of the University of Michigan
3
● begin <word>, b <word>: This specifies the word that Letterman starts with. This
flag must be specified on the command line, and when it is specified a word must follow
it.
● end <word>, e <word>: This specifies the word that Letterman must reach. This flag
must be specified on the command line, and when it is specified a word must follow it.
● help, h: If this switch is set, the program should print a brief help message which
describes what the program does and what each of the flags are. The program should
then exit(0) or return 0 from main.
Note: When we say stack, or s, we mean that calling the program with stack does the same
thing as calling the program with s. See getopt for how to do this.
Legal command line arguments must include exactly one of stack or queue (or their
respective shortforms s or q). If none are specified or more than one is specified, the program
should print an informative message to standard error (cerr) and call exit(1). A legal
command line must specify at least one of change, length, and swap or their respective
shortforms.
Examples of legal command lines:
● ./letter stack b ship e shot l < infile
○ This will run the program using a the stack algorithm and word output mode. The
only modifications allowed on words are inserting/deleting letters, NOT changing
one letter into another.
● ./letter b ship e shot c queue output W < infile | more
○ This will run the program using the queue algorithm, word output mode, and
letters can only be changed into other letters.
● ./letter stack output M b ship e shot length change < infile > outfile
○ This will run the program using the stack algorithm, modification output mode,
and letters can be changed, inserted, or deleted.
Examples of illegal command lines:
● ./letter queue s b ship e shot c < infile > outfile
○ Contradictory choice of routing
● ./letter b ship e shot c < infile | more
○ You must specify either stack or queue
● ./letter s b ship e shot < infile > outfile
○ You must specify at least one of change, length, and swap.
Routing schemes
You are to develop two routing schemes to help Letterman get from the starting word to the
ending word:
● A queuebased routing scheme
Version 122715
Current version by: David Snider and Laura Wendlandt
Originally composed by: David Paoletti
© 2016 Regents of the University of Michigan
4
● A stackbased routing scheme
