nrk's cryptogram solver
-----------------------

Building and Installing
-----------------------
You will need word list files organized by word length, one file for each 
word length.  For instance, all words of length 4 must be stored in one
file, while all words of length 5 must be stored in another.

If you have GNU make, the provided Makefile should work without problems
assuming you have gcc installed.  If not, change the Makefile to use
your C compiler.

The program expects the word list files to be present in dic/dic? [where
? is the length of words in that list.  single digit for 1-9, double
digit for 10-32], under the current working directory.  You can change
this behavior by editing dict.c and changing the values in the dicts
array initialization as appropriate.


History
-------
In the Fall of '02 I was the Teaching Assistant for a cryptography course.
Each student had to do a term project chosen out of a number of given 
choices. One of the projects was to build a program that would more-or-less 
solve Cryptograms or simple mono-alphabetic substitution ciphers.  My 
interest was piqued and on a boring weekend the following winter, I hacked 
up my own cryptogram solver.  


Random Notes
------------
It isn't terribly smart or anything like that.  All it does is a brute-force
search through possible legends for a ciphertext using a word list.  The only
smart parts are the algorithm in getMatchingWordsFromDict() [see legend.c] and
the extensive use and abuse of bit-masks to represent alphabet sets, their 
unions, intersections and complements [see solver.c].

getMatchingWordsFromDict() is truly a decent piece of work, as it manages to
convert what is essentially an O(n^2) [n == length of word] algorithm into 
a O(n) one by sacrificing a very very insignificant amount of memory and some 
really smart map creation and data manipulation.

If no solution can be obtained, a re-attempt is made by removing the longest
cipherword from consideration and trying just the other words.  This continues
until no word is left to be solved.  Obviously, the approach deteriorates
somewhat once you ignore more than 3 or so words.

On my PIII 700 MHz Linux box, it solves typical cryptoquips (from newspapers)
in about 200-300 milliseconds (with my almost 300,000 word dictionary).


Limitations
-----------
Won't work well (at all?) on machines where sizeof(int) < 4.
Won't work for words with more than 32 letters in them.


Bugs
----
None that I know of.


Things to Improve
-----------------
One thing that definitely needs to be improved is to avoid checking all
cipherwords for matching english words.  Instead, after each iteration of
solveWords [solver.c], one should check the current legend to see if all
cipher characters have a unique plain character mapping.  If so, we are
done and no further processing needs to be done.  This will be a big 
advantage if the cryptoquip is long.

Another possible improvement is to weight the words in the wordlists
by their occurrence likelihood.  This will avoid picking up strange
words [esp. 2 and 3 letter ones], when it is quite obvious that they
don't fit.  I haven't given much thought to this yet...

About
-----
You can find a web-based frontend to this solver at
http://www.cs.purdue.edu/homes/nrk/cryptoquip.html

You can also download the source code + my word list from the same
page listed above.

I am currently a graduate student in Computer Science at Purdue 
University.  You can reach me by e-mail at nrk@cs.purdue.edu.

I would love to hear about any bugs/issues that you encounter in
your use of this program.
