COS 226 Programming Assignment Checklist: Puzzle Search

Frequently Asked Questions

What will happen if I output the same word more than once? No deduction.

Will the word list contain duplicates? No.

Will each word in the word list appear in the puzzle? Not necessarily. Otherwise, the optimal solution would be to ignore the puzzle and just echo back each word in the word list!

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 should I time my program? You should definitely redirect the output to a file; otherwise you might end up measuring the speed of your display terminal instead of your program!

How do I ask my operating system to give Java more memory? Execute with java -Xmx300m WordSearcher to request 300MB of memory.

What was the command to get profiling? Execute with java -Xprof WordSearcher.

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).


% java WordSearcher < input.txt | sort | uniq > out1.txt
% puzzle226-sparc   < input.txt | sort        > out2.txt
% diff out1.txt out2.txt

What will a big input file look like? The biggest one available for download contains a 5000-by-5000 puzzle and over half a million words. This isn't grandma or grandpas little puzzle book. But, don't expect this one to be easy to solve.

Input, Output, and Testing

Input and output. Here is a sample input file that appeared in an immunity challenge on Survivor Africa! It happens that all word in the word list appear in the puzzle.

% cat puzzle-survivor-africa15.txt
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

When you execute your program, you should get the following output:

% java WordFinder < puzzle-survivor-africa15.txt
shaba
chakula
chaka
matwana
kubwa
pona
ndovu
vongonya
aliko
wageni
wendo
fora

Note that the words you output need not be in alphabetical order, nor in the order above. However, it is essential that you print one word per line and that you don't print out anything else, including the puzzle and original word list. We plan to check your solutions by piping the output through sort and uniq, and then using diff. Here are some more input files.

Reference solutions. For reference, we provide (heavily optimized) executable C code for our solution in Windows, Solaris, and OS X. We challenge you to develop a faster program! It is possible (ok, maybe impossible in Java) 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.

Submission and readme

We will compile your program with "javac WordSearcher.java", but, otherwise, 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.

Getting started

Download the directory puzzle. This directory is mirrored on arizona at /u/cos226/pub/puzzle. It contains a number of sample input files, a random problem instance generator, and reference solutions.
You can write and debug the scaffolding that you will need to read and write the character array, read and write the dictionary, and so forth without even thinking about the problem. We provide the program PuzzleIO.java to demonstrate how to read in the input. You may want to copy it to WordSearcher.java and use as a starting point.
Designing and implementing a good algorithm will require a good deal of thought and judicious use of data structures. First, think about what operations you'd like to perform on the puzzle and word list. Careful planning here will save you time in the long run. Now, implement a brute force data type for each (e.g., a 2D array for the puzzle and a string array for the word list). If your others ideas fail, you will at least have something to turn in. As always, avoid the temptation to over-optimize before you have a working solution and know where is the bottleneck.

Enrichment Links

Feel free to create your own word search puzzles. Send us your creations and we'll include our favorites on our web site.