By popular demand, you may assume that all word in the word list are at least four characters long. The puzzle files have been cleaned up to accommodate this.
|
|
What will happen if I output the same word more than once? A minor deduction.
Will the word list contain duplicates? No.
Do I have to handle overlapping words? Definitely. For example, if the word noninterchangeability appears in the puzzle, then interchange, change, and ability should also be printed, assuming they appear in the word list.
How can I compare my results against the reference solutions since they appear in different orders? Sort them first. Unix users can automate the comparison process by using sort and diff.
How do I dynamically allocate a 2 dimensional array in C? See question 6.16 of Steve Summit's C FAQ.
|
|
Input and output.
Here is a
sample input file that appeared in an immunity challenge on
Survivor Africa!
When you execute your program, you should get the following output:
15
p d h y a o s t e m r o b k l
k s o l v x c t o e a g z k p
u w n l u d a i a s c h a k a
b t c e y k n m f n h p o g i
a e u k u b w a p d a a d y k
r p f c g d e t h t k t b c u
y o b g h a y w i s u r h a m
k n d o v u e a m a l i k o z
p a z h o r w n o i a u b m a
t e q i n l o a n e n l i p s
b y r u g v q r g w r k s u l
o l h i o w e s w e e o w l t
c w b r n d i a i n n x w h i
k n s u y j t s a d r i j v o
v f o r a h p a l o c n a e s
aliko
chaka
chakula
fora
kubwa
matwana
ndovu
pona
shaba
vongonya
wageni
wendo
Note that the words you output need not be in alphabetical order.
However, it is essential that you print one word per line and that you don't
print out anything else. We plan to check your solutions by piping the output
through sort, and then using diff.
Here are some
more input files.
% a.out < puzzle-survivor-africa15.txt
shaba
chakula
chaka
matwana
kubwa
pona
ndovu
vongonya
aliko
wageni
wendo
fora
Reference solutions. For reference, we provide executable code for our solution in Windows, Solaris, and OS X. We encourage you to develop a faster program! It is possible (but very difficult) to beat our program, but it is also possible that you will get most/all of the credit even if your method is not as efficient. In any case, be sure that your program is correct. There is no point in optimizing a program that generates wrong answers.
|
|
We will compile your program with "gcc *.c" so you are free to organize your program as you see fit. As usual, we encourage and reward sound design principles. Overly abstract and general interfaces are not needed, but the client-implementation-interface paradigm will likely be useful. The key to writing efficient programs is identifying which operations are critical, and choosing the right data structures to implement these operations.
Here is a template readme.txt file. Please answer all of the questions, and give a table of the CPU execution time for all of the sample inputs that your program is able to process. Unix users may find the shell script timeit.csh useful.
|
|
|
|
Feel free to create your own word search puzzles. Send us your creations and we'll include our favorites on our web site.