## ## 2004 Utah High School Programming Contest ## University of Utah ## ## README ## ############################################################################### The files in this directory provide a "skeleton" for implementing your solution to this year's take-home problem for the Utah High School Programming Contest. The skeleton compiles and runs, but does a relatively poor job at deciphering cryptograms. You will need to add your own code to the skeleton in order to improve its decryption abilities! COMPILING AND RUNNING THE SKELETON ---------------------------------- The skeleton is written in standard Java, and so it should compile easily with any modern Java compiler or IDE. If you have the `Ant' build tool for Java, you can use the provided `build.xml' file to compile the program. Once you have compiled the program, you can run the program by giving it the name of a cryptogram file. A simple cryptogram is provided with the source code in the file `sample.text'. Assuming your Java interpreter is named `java', running the command: java Decrypt sample.text should produce the output: Go to 1800 High-Five Lane and look for a tall man. He is "the one." If you have trouble compiling or running the skeleton program, send email to for assistance. OVERVIEW OF THE SKELETON SOURCE CODE ------------------------------------ The skeleton consists of the following classes: Decrypt defined in `Decrypt.java' Decrypt is the "main class" of the program. Its main method implements the overall program logic: parse the command line arguments, read the cryptogram file, decipher the cryptogram, and output the decoded result. The Decrypt class has helper methods for reading the input file and deciphering the cryptogram. Puzzle defined in `Puzzle.java' Puzzle is the class that collects the "input" information about a cryptogram puzzle and evaluates possible solutions (i.e., decryption ciphers). The most important input data is the cryptogram text, of course, but a Puzzle may also use other sources of information such as a dictionary of known English words. The primary job of a Puzzle object is to evaluate ciphers that are given to it: in other words, to decide how likely it is that a given cipher is the right cipher. Cipher defined in `Cipher.java' A Cipher represents a possible decryption method: e.g., a particular rotation algorithm or a particular substitution algorithm. The primary method of a Cipher is `decipher', which applies the Cipher's algorithm to a given string. The Cipher itself is only responsible for applying its algorithm. A Puzzle object is responsible for deciding whether or not a Cipher's algorithm is actually the "right" one for decrypting a message. Cipher is actually an interface (not a class): it defines a common way of interacting with all kinds of ciphers, but does not itself provide any implementation for ciphers. The actual details of creating ciphers and implementing decryption algorithms are contained in the classes that implement the Cipher interface: RotationCipher and SubstitutionCipher. Search defined in `Search.java' A Search object is responsible for implementing a search strategy to find the best decryption cipher for a Puzzle. The Search `findCipher' method creates Cipher objects and passes each one to a Puzzle object, which is responsible for evaluating each cipher individually. The `findCipher' method keeps track of the best cipher and returns it. In sum, Search is responsible for deciding what ciphers to test, and in what order. Other objects are responsible for actually applying a cipher to a cryptogram (this is done by a Cipher) and evaluating the quality of the result (done by a Puzzle). The skeleton implementation of the Search `findCipher' method only searches for rotation ciphers. You will need to improve the Search class so that it explores substitution ciphers as well. RotationCipher defined in `RotationCipher.java' A RotationCipher implements a particular letter rotation algorithm. For example, a RotationCipher might rotate every letter forward by one position, mapping 'A' to 'B', 'B' to 'C', ..., and 'Z' to 'A'. The rotation wraps around at the end of the alphabet. The distance of the rotation is determined when the RotationCipher object is created. There are 26 possible rotation algorithms (including the shift-by-zero algorithm). RotationCipher implements the Cipher interface. SubstitutionCipher defined in `SubstitutionCipher.java' A SubstitutionCipher implements a particular letter substitution algorithm, in which every letter is replaced by some other letter. SubstitutionCipher implements the Cipher interface. The SubstitutionCipher class is unimplemented in the skeleton. You will need to implement all of it! Dictionary defined in `Dictionary.java' A Dictionary represents a collection of known English words. The primary method of a Dictionary is `lookup', which searches for a given word in the dictionary. A Puzzle can use a Dictionary in order to evaluate the quality of a cipher. Words defined in `Words.java' Words is a simple container for a hard-coded list of English words. It is defined separately from the Dictionary class in order to separate the "raw list" of words from the internal data structures and code of the Dictionary class. The various objects of the program are brought together in the Decrypt class. + First, the Decrypt class creates a "default" Dictionary object from the raw list of words in the Words class. This is stored in the `DICT' member of the Decrypt class. + Later, the `decrypt' method of the Decrypt class is invoked to decode a given cryptogram string. + The method creates a Puzzle object from the input cryptogram and the default Dictionary. + It then creates a Search object and invokes its `findCipher' method to determine the cipher that best solves the puzzle. The best Cipher object is returned from the Search `findCipher' method. + Finally, that Cipher is applied to the cryptogram. The `main' method of Decrypt essentially just "wraps" input and output handling around the `decrypt' method. FINAL ADVICE ------------ The main "missing parts" of the skeleton are (1) an implementation of the SubstitutionCipher class, and (2) code in the Search class to generate and test SubstitutionCipher objects. You will need to think *carefully* about how to best implement this search. Your code will need to be substantially different from the skeleton code that handles rotation ciphers. Another important part of the code is the evaluation of ciphers in the Puzzle class. The skeleton has a very simple algorithm for determining the "score" for a cipher, based on the cipher's ability to turn a cryptogram into words that are found in the dictionary. You will need to improve the evaluation of ciphers to make use of other information (for example, letter and digraph frequencies) in addition to simple dictionary lookups. Your program will need to be able to handle inputs that contain English words that are not in your program's dictionary! The Dictionary class itself could also be greatly improved. For example, you could improve it to handle word variations: if "fly" is in the dictionary, your program might also guess that "flys", "flies", and "flying" are also in the dictionary. The dictionary should also be fast, but the current code does not implement a very fast lookup algorithm. If you have a question about the take-home problem, first check the list of frequently asked questions (FAQ) on the Web. With luck, your question will already be answered there! If you can't find an answer in the FAQ list, then contact us by sending email to . We will answer your question as soon as possible. We might also add your question to the frequently asked questions list. Finally, remember to check the 2004 Utah High School Programming Contest home page for late-breaking news and contest updates! Good luck! ############################################################################### ## End of file.