Code Cracking 2: Improvements

For this assignment, we will improve our code-cracking program so that it can handle more challenging messages more efficiently. Our goal is to learn about improved search techniques and to gain experience them.

Implementation guidelines

I am assuming that your search method operates with respect to three key pieces of information: the partial key consisting of the subset of ciphertext letters assigned to given plaintext letters; the remaining unassigned ciphertext letters that have not be committed to a plain text letter; and the unassigned plaintext letters to which a remaining ciphertext letter could be assigned. This conceptualization leads no a nice recursive formulation of the algorithm. (Of course, you need to deal with avoiding unintended side-effects, etc.)

Requirements

  1. Improve pruning of search. Write a Java class, CrackCipher2, that improves upon your initial program. As your first improvement, you should enable dynamic pruning of search branches that most likely will be unfruitful. One way to do this is to use the partial key as it is being developed and look at what it does to the encrypted ciphertext. When a partial key maps some characters including space (which will tend to be assigned early), then some of the candidate plaintext may form complete words. Check such words against your dictionary and reject partial keys that lead to excessive non-words. Note, you will need to distinguish characters that are not translated by the partial key so that you can subsequently check only the complete words.
  2. Write a word weaver. Write a class, WordWeaver, that creates an efficient means to access all words that have a given letter in a given position. For each one of some maximum number of letter positions (say, seven), the class creates a HashMap<Character,HashSet<String>> that stores all of the words that have a given letter in the corresponding position. For example, the HashSet associated with the character ‘a’ in the second position might have the words: bat, cat, rat, ball, lathe, sack, and so on. The point of this class is the early elimination of unfruitful partial keys by identifying partial words that will never lead to dictionary words. Your WordWeaver class must include a public method, possibleWord(String aPartialWord) that returns true if the letters translated so far could lead to at least one word found in the dictionary or false if no such word exists with the given letters. For example, the partial word, ‘___xzj_er’, cannot become a valid word no matter which letters are selected for the remaining underscores. The partial key leading to this partial word can safely be rejected and further search on this path pruned.
  3. Expand pruning. Using your WordWeaver class, modify your CrackCipher2 program to prune search branches based on partial words in addition to complete words. With these two pruning methods in place, you should be able to decrypt the other two encrypted messages that I provide (on Eureka); I will be looking for a correct recovery of my original text as well as for a speedy solution. You will have noticed from the first part of the project, there may be multiple keys that yield completely valid messages. Thus, I am expecting the correct translation to appear with a reasonably small set of decodings.

Submission Instructions:

On your machine where you are doing your homework, create a folder called <your email name> followed by “P02”. For example, someone with email address “cjones” would create a folder called “cjonesP02”. Inside that folder, place plain text file(s) containing your answers to any written questions required of you. Also, place whatever Java and documentation files are necessary for your programming project in the same folder. Finally, either tar or zip the folder so that when I extract it, the folder ”<emailname>P02“ will be created. Finally, submit via Eureka.