Assignment: Word Matching
What's a six-letter word that has an e as its first, third, and fifth letter? Can you find an anagram of pine grave. Or how about a word that starts and ends with ant (other than ant itself, of course)? And what was the name of the place where the dinosaur-killing asteroid is thought to have landed 65 million years ago? I think it was 'cat something" or at least it had "cat" in it.
One way to find answers to problems such as these is to search a list of words (such as the one available on most Unix systems in the file usr/dict/words or /usr/share/dict/words) for words matching a given pattern. Then you can easily find answers like as eleven, eyelet, grapevine, antiperspirant and Yucatan.
Task
Your task is to write a program, named math, that can find such matches.
The program is run from the command line, using this syntax:
match [-OPTION].......PATTERN [FILENAME]....
The program reads words from standard input (or from each of the named files in turn) and compares them with the pattern specified on the command line. A pattern is composed of letters and underscores (" '). A letter matches itself, an underscore matches any character_ The input consists of words separated by whitespace. If an input word matches the specified pattern, the word is written to standard output; otherwise., nothing is written for that word. The program stops when all of the input words have been read and processed.
The proceas of matching is controlled by command-line options.:
- With no options (or with the option -w), a word is matched if it matches the pattern in its entirety. Thus Match c_t match -w c_t) would match cat or cut but not cater or scotch.
- The options -p and -s specify that a word is matched if the pattern occurs as either a prefix {at the beginning) or a suffix (at the end). Thus match -p cat would match catfish or cataclysmic, and match -s cat would match scat or bobcat.
- The option -a allows the match to occur anywhere within a word. Thus math -a cat would match vaca.te and amplification.
- The option -e specifies that a word is matched if it is embedded within the pattern. Thus match -e vacata would match cat and ate.
- Normally the letters in a word match only if they agree in case with the pattern. The option -i makes the match ignore the case of the word. Thus match Cat would not match cat, whereas match -i Cat or match -i CAT would cat or CAT or even cat.
- Normally the pattern is matched exactly. However, if the option -j (for jumble) is specified, then the pattern is considered matched if any rearrangement of the pattern is matched. Thus match -j cat would also match act.
- The option -v reverses the sense of the match. The output will therefore consist of all of the words that do no: match the pattern.
- The option -n takes an argument that specifies constraints on the length of the matching wards.
By default, any length word is permitted. However match -n3 , 6 -p cat would match words that begin with at and that contain between 3 and 8 letters. As a special case, a minimum or maximum length of 0 or an omitted length) indicates no restriction. Thus, -n3, 0 or -13.3) specifies words of 3 or more letters, -n10 r 8 (or -n r El.) specifies words of 8 or fewer characters, and -n0, 0 (or -n,) specifies words of any length.
All options come before any other arguments, but more than one option can he specified. The w, p, s, a, and e. options are mutually exclusive. If more than one is specified, the Last-specified option takes precedence. Thus match -p -a at is equivalent to match -a cat. The other options are independent and can be specified in any order and any combination. For example match -a. -j cat (or match -j -a cat) would match factor or antacid, and match -a -n7, 7 cat would match Yucatan.
Hints
Download the file match_O. IP, which contains a skeleton version of the progra.m that works correctly when run with no options or file names, and with a pattern that contains no underscores_ Note that if no word is matched by the pattern the program exits with status I (the program status is. the value returned by main), and that if at least one word is matched it exits with status 0.
The skeleton also shows how you can use the standard getopt function to greatly simplify the processing of option arguments_ The function analyses the cornrnand-line parameters argc and argv for arguments that that begin with - and contain specified option letters., returning individual letters on successive calls and adjusting the variable optind to indicate which arguments it has processed. Consult topt documentation for details.
The skeleton contains enough option processing code for the first few levels of the assignment, but you will need to add additional capabilities for higher levels. And, of course, you will need to write the code that actually rise the option variables to control the program's operation. Note that at any point during the option-processing loop, variable opt opt contains the current option letter, and for options that take arguments, variable optarg is a pointer to the argument string. Adjusting airge and argv after the loop completes effectively removes the option arguments, so that argc will indicate how many additional arguments remain and aror will contain the argument values.
Function Points
1. Extend the program so that it correctly handles the -w, -p and -a options.
2. Extend the program so that it correctly handles the -a and -a options.
3. Extend the program so that it correctly handles the -v option.
4. Extend the program so that it correctly handles the -1 option.
5. Extend the program so that it correctly interprets patterns that contain underscores.
6. Extend the program so that it correctly handles the -n. option_ For this level, you can assume that the option argument will not omit length values. That is you can assume that it will explicitly specify the minimum and maximum lengths (either of which might be 0).
7. Extend the program so that it handles missing or incomplete arguments.
- When the argument for the -n option omits one or both of the length specifications, the program should assume a value of 0 for the missing length and proceed normally.
- For other errors, it should display an error message on the cerr stream, and exit with an appropriate status code. The output format should be should he
<< error massage as indicated below >>
Usage: match [-OPTION)... PATTERN IFILENMME)...
|
Condition
|
Error message (wrih x replaced by the option}
|
Status
|
|
Unrecongnised option
|
Unrecognised option -x
|
2
|
|
Missing option argument
|
Option -x requires an operand
|
2 |
|
Missing pattern
|
Missing pattern
|
2
|
8. Extend, the program so that if one or more filenames is specified on the command line, input is taken from each file in turn rather than from standard input_ lf a tile cannot be opened, the program should display the following error message on carr and exit with status 2.
Can't open file <)
9. Extend the program so that it correctly interprets the -j option when the pattern does not
contain underscores.
10. Extend the program so that it correctly interprets the -j option for all patterns.
Assessment Pairing
You are encouraged to work on this assignment in pairs. If you work as a pair, you must both hand in a soluLion, which should he id.entical. All work handed in will be checked using a similarity checker, if more that 2 solutions appear similar, marks will be withheld pending investigation.
Automatic assessment
The function points for this task will he assessed automatically using the demo and try programs under the task name match. You can run the demo version using demo- match and you can test your work using try. match < >. As the source code consists of more than one file, you'll need to submit your work as a zip file_
Scoring
The assignment will he submitted and assessed twice: once following the "core" hand-in date, and again following the 'extension' hand-in date_ The core submission will be given a score out of 10, based on the first 5 function points_ The extension submission will also he given a score out of 10, based on the last 5 function points.
Testing
Because the prog.ram makes extensive use of command-line arguments, you will probably find it easiest to test, at the command line. (it's possible to run programs with command-line arguments in NetBeans, but it's not convenient.)
As the program takes its input from the standard input stream, you can test it by typing word_s at the keyboard_ However, you might find it more convenient to redirect standard input to come from a file containing test data:
$› match -a cat < test.txt
And because the program acts as a filter, you can pipe it a dictionary file of words to find the answers to those questions at the start, or even solve today's 9-letter word search:
$› cat worda.txt | match e_e_e
eleven
eyelet
$› cat worda.txt | match -) pinegave
grapevine
$) cat worda.txt | match -n4 -p ant j match -a ant
antiperspirant
$) cat worda.txt | match -n3 -m -j plamgravm 1 match -a i
air
ani
gain
genie gin
give
given grain grapevine
grieve