m v j l i x a p e
j h b x e e n p p
h k t t h b s w y
r w a i n u y z h
p p f x r d z k q
t p n l q o y j y
a n h a p f g b g
h x m s h w y l y
u j f j h r s o a
Your program is to find words from the dictionary that can be spelled
out in the puzzle by starting at any character, then moving in a
straight line up, down, left, right, or on any of the four diagonals.
For example, the above array contains the word algorithm because
it can be spelled out by starting the lower right corner and moving up
and to the left; and it contains the word syzygy because it can
be spelled out by starting at the s on the third row and moving
down.
The purpose of this assignment is to give you more experience working with strings and to give you an opportunity to put to work the algorithms design skills that you are learning.
Input format. From standard input, read the integer N, then N lines of N characters each (with each characters separated by one space), followed by the word list (one per line). You may assume that the list of dictionary words is in lexicographic order. You may also assume that both the puzzle and the dictionary consist of only lowercase letters. Finally, you may assume that all of the words in the dictionary are at least four letters long.
Output format. Print out every dictionary word (one per line) that is contained somewhere in the puzzle. If a word appears in the puzzle more than once, print it only once.
Approach. We have covered a number of different algorithms that can be used effectively to solve this problem. Your task is to study the problem; come up with a strategy for solving it using some of the algorithms and data structures that you have learned; implement and test your solution; and then explain and defend your design in the writeup. A good writeup is particularly important for this assignment, because we expect to see a variety of solution strategies. You need to clearly explain not just what you did, but also why you did it, backed up with estimates of resource costs. Also, you should clearly explain whatever limitations you need to place on the puzzle size N and the dictionary size M. As usual, your goal is to find a decent method which works within reasonable bounds. You need not waste effort squeezing time and space out of a bad algorithm or implementing complex or highly tuned code. This problem can be solved efficiently with 200 or so lines of code (including comments and basic error checking).
Prize. An utterly useless prize will be awarded to the student who submits the "best" program. Indicate in your readme if you'd like to enter the contest. We will evaluate your programs by racing them off against each other on large (nondegenerate) puzzles. For this contest, the most important factor is raw speed.
Challenge for the bored. Search for words according to the rules of Boggle, instead of just vertically, horizontally, and diagonally.