Day 1 Question 2

Message Deciphering

Input file: crypt.in

Output file: crypt.out

Messages can be ciphered (encrypted) by systematically replacing letters of the alphabet by other letters. A simple cipher known as the Caesar cipher replaces each letter in the alphabet by the letter k positions later in the alphabet, where A is considered to follow Z . For example, if k = 6, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, and Z would be replaced by G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A, B, C, D, E, and F respecively. The message

   THE FULL MOON RISING IS A BAD SIGN

would be ciphered as

   ZNK LARR SUUT XOYOTM OY G HGJ YOMT

The inverse of the cipher is again a Caesar cipher with 26-k replacing k.

Your job as cryptanalist is to decode lines of text that have been encoded with a Ceasar cipher, each using a different unknown value of k. For example, if the input were

   ZNK LARR SUUT XOYOTM OY G HGJ YOMT
   FA NQ AD ZAF FA NQ FTMF UE FTQ CGQEFUAZ

the output would be

   THE FULL MOON RISING IS A BAD SIGN
   TO BE OR NOT TO BE THAT IS THE QUESTION

(the first line was ciphered with k=6 and the second line with k=12).

Of course there are 26 possible values of k and therefore 26 possible ciphers, so you will have to "guess" by selecting the most probable deciphering. The probability of a particular deciphering can be estimated using the probabilities of the letters it contains. In English, E is the most common letter, with probability 0.127, T is the next more common with probability 0.091, and so on. A complete table of letter probabilities is given below. The probability of a complete line of text can be approximated by the product of the probabilities of the letters it contains.

Input Specification

The input to your program consists of a line containing a positive integer n, followed by n lines each consisting of of upper case letters and spaces only. Each line is an English phrase or sentence, encrypted with a Caesar cipher with unknown k.

Output Specification

For each line of input, give the most probable deciphering.

Sample Input

2
ZNK LARR SUUT XOYOTM OY G HGJ YOMT
FA NQ AD ZAF FA NQ FTMF UE FTQ CGQEFUAZ

Output for Sample Input

THE FULL MOON RISING IS A BAD SIGN
TO BE OR NOT TO BE THAT IS THE QUESTION

Probabilities of Letters in English Text

       Letter     Probability       Letter   Probability
          A          .082             N          .067
          B          .015             O          .075
          C          .028             P          .019
          D          .043             Q          .001
          E          .127             R          .060
          F          .022             S          .063
          G          .020             T          .091
          H          .061             U          .028
          I          .070             V          .010
          J          .002             W          .023
          K          .008             X          .001
          L          .040             Y          .020
          M          .024             Z          .001