### 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