|
|
What will happen if I output the same word more than once? No deduction - this is a change from last semester. The reference solution does not print duplicates.
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. (Yes, another application of sorting!) Unix users can automate the comparison process by using sort, uniq, and diff. You only need uniq if your program prints out duplicates. The following sequence of commands should produce no output (assuming our program has no bugs).
% myprogram < input.txt | sort | uniq > out1.txt % puzzle226-sparc < input.txt | sort > out2.txt % diff out1.txt out2.txt
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 uniq, 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 (heavily optimized) executable code for our solution in Windows, Solaris, and OS X. We challenge you to develop a faster program! It is possible (but very difficult) to beat our program, but it is also possible to get 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 "gcc226 *.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 a sampling 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.