CCO '98 P2 - Message Deciphering - DMOJ: Modern Online Judge

CCO '98 P2 - Message Deciphering

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 2.0s

Memory limit: 64M

Problem type

Canadian Computing Competition: 1998 Stage 2, Day 1, Problem 2

Messages can be ciphered (encrypted) by systematically replacing letters of the alphabet with other letters. A simple cipher known as the Caesar cipher replaces each letter in the alphabet with the letter $k$ $k$ positions later in the alphabet, where A is considered to follow Z. For example, if $k = 6$ $k = 6$ , ABCDEFGHIJKLMNOPQRSTUVWXYZ would be replaced by GHIJKLMNOPQRSTUVWXYZABCDEF respectively. The message

Copy

THE FULL MOON RISING IS A BAD SIGN

would be ciphered as

Copy

ZNK LARR SUUT XOYOTM OY G HGJ YOMT

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

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

Copy

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

the output would be

Copy

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$ $k = 6$ and the second line with $k = 12$ $k = 12$ ).

Of course, there are $26$ $26$ possible values of $k$ $k$ and therefore $26$ $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$ $0.127$ , T is the next more common with probability $0.091$ $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.

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	.061	V	.010
J	.002	W	.023
K	.008	X	.001
L	.040	Y	.020
M	.024	Z	.001

Input Specification

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

The input will have at most 500 characters of input (including spaces).

Output Specification

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

Note that all the data are generated such that there is only one unique most probable deciphering.

Sample Input

Copy

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

Sample Output

Copy

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

Comments

0

thunder200911133 commented on May 14, 2024, 1:44 p.m.

There will be only inverse Cipher right? Or is it we need to consider both way?

Tommy_Shan commented on May 13, 2022, 4:27 p.m.

This might be useful

C++:

Copy

map<char, double> prob = {{'A', 0.082}, {'B', 0.015}, {'C', 0.028}, {'D', 0.043}, {'E', 0.127}, {'F', 0.022}, {'G', 0.020}, {'H', 0.061}, {'I', 0.061}, {'J', 0.002}, {'K', 0.008}, {'L', 0.040}, {'M', 0.024}, {'N', 0.067}, {'O', 0.075}, {'P', 0.019}, {'Q', 0.001}, {'R', 0.060}, {'S', 0.063}, {'T', 0.091}, {'U', 0.028}, {'V', 0.010}, {'W', 0.023}, {'X', 0.001}, {'Y', 0.020}, {'Z', 0.001}};

Python:

Copy

prob = {"A": 0.082, "N": 0.067, "B": 0.015, "O": 0.075, "C": 0.028, "P": 0.019, "D": 0.043, "Q": 0.001, "E": 0.127, "R": 0.060, "F": 0.022, "S": 0.063, "G": 0.020, "T": 0.091, "H": 0.061, "U": 0.028, "I": 0.070, "V": 0.010, "J": 0.002, "W": 0.023, "K": 0.008, "X": 0.001, "L": 0.040, "Y": 0.020, "M": 0.024, "Z": 0.001}