Prog 3: Decipher

Changes:

2/17/16 Shown in green:  Changed output words to be "Original and Changed text"

2/15/16  Shown in blue:  Changed output for decode to always show both forward and reverse values; Changed output words.

2/12/16 

• 1. Showed sample output for the various cases

  2. Explained how to get rid of extra carriage return character on input

  3. Noted that negative transposition values must also be handled

  4. Explicitly noted the number of words in the dictionary

  5. Gave permission for any sort (including sequential) to be used

Write a program to figure out what some encrypted line of text says by trying all possible decryption possibilities. For each decryption possibility look up all the words in a dictionary to see if it is recognizable English. The steps will be: 

• 1. Take the original input line where words are separated by white space (space, tab, or return)

1. Transpose each character by some amount. This approach is called the Caesar cipher. For instance transposing by +1 would convert "abc" to "bcd", and would convert "xyz" to "yza", where transposing letters at the end of the alphabet "wraps around" back to the beginning of the alphabet.  Similarly, if using this approach with all printable ASCII characters between character 32 (space) and character 126, then transposing "hey \~Z" by 1 would give: "ifz!] ["   Note that in this case we have 95 characters total, and again the character '~' at the end wraps around to the space character at the beginning of the range.

2. Take the resulting transposed text and find the first white-space separated string.  Look it up in the dictionary and keep track of whether or not it was found.  Repeat for the next string and keep going until you have reached the end of the input or you have processed enough strings to have a good idea of whether or not many of the strings were found in the dictionary.  Repeat this whole step where the entire line is reversed.  Store these statistics.

3. After trying all possibilities (both forwards and backwards), the transposition and direction with the greatest number of words found in the dictionary is the one selected to be displayed as the decrypted text.

Further Explanation

In order to try and decode the message, it is helpful to fully understand how the original plain text was encrypted in the first place. The first step reverses text. For instance sample input of

     hard work

when transposed by 1 would look like

     ibse!xpsl

Note that non-alphabetic characters are also transposed. 

In our case of trying to decrypt some ciphertext you don't know what the transposition value is, but you know it has to be between 0..95. (Using 96 would transpose each character around back to itself, so is not helpful. Thus values >95 simply replicate existing options and so are not necessary.) 

You need to know the following concepts in order to write this program:

Everything from the previous programs; arrays of char; string functions; reading text from a file; binary dictionary search

Notes:

Write the program in stages, as indicated below.  Each of the below stages is worth a certain amount out of the 55 points for program execution.

1. (15 points) Run the program to create encoded text, in forwards order only.  This should look like:

   1. 1. Author: Dale Reed            Program #3: Decipher         TA: Omigood Ness, T 6:00 AM  Feb 7, 2016                  System: XCode on Mac           Choose from the following options:     1. Encode some text                     2. Decode using user-entered values     3. Decode automatically                 4. Exit program                      Your choice: 1  Enter the text to be encoded: all generalizations are false Enter direction (1 Forwards or 2 Reverse): 1 Enter transposition value: 3Original and changed text are:  all generalizations are false doo#jhqhudol}dwlrqv#duh#idovh  Done. 

2. First write the code to read in a whole "line" of user input using:

3.    char userInput[ 81];

4.    cin.getline( userInput, 80); 

5. If you are previously  using   cin >> menuOption;  to  read in the user's menu choice, then you will have a problem with the above two lines because the carriage-return character is still sitting on the input buffer.  To strip that off additionally define a single character such as   char c;   and read that in  using cin >> c;   to get rid of this carriage return.

6. Next write a function that takes a character and a number value, does the transposition (including any appropriate wrap-around), and returns the new character.  This should handle the full range of ASCII printable characters from character 32 (space) to character 126 ('~').  Call this function on each character of the userInput array, and print it out.

7. (5 points) Repeat the above step, except reverse the entire input line end-for-end before encoding it.  Running this code should now look like:

   1. 2. 1. Author: Dale Reed            Program #3: Decipher         TA: Omigood Ness, T 6:00 AM  Feb 7, 2016                  System: XCode on Mac           Choose from the following options:     1. Encode some text                     2. Decode using user-entered values     3. Decode automatically                 4. Exit program                      Your choice: 1  Enter the text to be encoded: all generalizations are false Enter direction (1 Forwards or 2 Reverse): 2 Enter transposition value: 3Original and changed text are:  eslaf era snoitazilareneg lla hvodi#hud#vqrlwd}loduhqhj#ood  Done.

• 1. (10 points) Now implement step 2, to decode using a value given as input by the user.  Apply this to both the original input value as well as to the reverse of the input value.  This should look like:

     1. 1. Author: Dale Reed            Program #3: Decipher         TA: Omigood Ness, T 6:00 AM  Feb 7, 2016                  System: XCode on Mac           Choose from the following options:     1. Encode some text                     2. Decode using user-entered values     3. Decode automatically                 4. Exit program                      Your choice: 1  Enter the text to be decoded: doo#jhqhudol}dwlrqv#duh#idovh Enter transposition value: -3Original and changed text are:  doo#jhqhudol}dwlrqv#duh#idovh all generalizations are false   <-- Forwards eslaf era snoitazilareneg lla   <-- Reverse  Done. 

  2. Your program should handle negative transposition values as well as positive ones.

  3. (25 points) Have the program try all possibilities automatically, using dictionary lookup to see which is the most likely real transformation.  

  4. You will need to use this dictionary of 34840 words for this, where those words are all between length 3 and 6 characters long.  See this sample program on how to read words from a file into an array using C++ commands.

  5. Add a search function to look up a word in the dictionary. See this program for an example of binary search for integers, and modify it to use strcmp to compare strings.  Alternatively you could use the sequential search shown in the program that reads words in from a file (shown above).

• • 1. Add code to store each of the following items, for each possible transposition value and direction.  

       1. How many words were found in the dictionary

       2. The direction (representing "forward" or "reverse")

       3. The transposition value (0..95)

    2. Apply and display the transformation with the best statistics (i.e. the most number of words found in the dictionary)

Turning In Your Program

The name of the program you will turn in should be prog3 followed by your netid and the .cpp file extension.  In other words, if your netid is reed then your program would be called prog3reed.cpp     You must also zip up the file you turn in.  After zipping your program (e.g.prog3reed.cpp), you will likely end up with a file called something like prog3reed.zip.   Only turn in this single file, turning it in on Blackboard into the assignment Program3: Decipher.  Failing to follow these naming conventions and failure to turn in a zip file will result in a 5 point deduction, even if everything else is perfect in your program.