The following is a checklist which provides a summary of the
assignment. This is meant only as a supplement; please read the original assignment
description.
Frequently Asked Questions:
(This is the only part of this checklist which will change during the
week.)
You may assume that
the wordlist in the input comes in alphabetical order.
To run your program on an
unsorted list, you may use the unix sort command as part of
the command line argument.
Here are some bigger sample inputs: a
20-by-20 puzzle
and a
30-by-30 puzzle.
You may assume that both the puzzle and the list of words are all
lowercase, and only consist of letters. This is NOT true for the
/usr/dict/words file on all systems. If you need a cleaned
up version, use the Unix command tr.
Overview:
The original assignment description is quite detailed, so this will be
a short checklist this week. The details of the assignment are given
there, and the Hints section even gives some suggestions for
making progress.
Input Format: As stated, your program should
expect to read an integer N from the command line, followed by N lines
of N characters each with characters separated by whitespace, followed
finally by a list of words for which to search. For example, a
complete inputfile, which could be used as cat inputfile |
a.out is given here. Alternatively, you
could combine a plain puzzlefile such as the
example given in the assignment, with a
different list of words, for instance with the command line:
(echo "9"; cat mysquare; cat /usr/dict/words) | a.out
You should only consider words that are 4-letters or longer -
ignore any others that are in the dictionary.
Output Format: Simply output all the words
which are contained somewhere in the puzzle. You may output them in
any order, however it would be nice if you make sure to only print out
a particular word once (even if it appears in several places in the
puzzle). If you want, you could also choose to describe the location
in the puzzle where each successful word lies.
readme: Make sure you explain what
you do and why. Give estimates of the time/space costs which might be
required, and any limitation you place on N or the dictionary size.
cos226 Class Page
rs@cs.princeton.edu
Last modified: March 1, 2001