As if this challenge could be any more Pythonesque in spirit... No prior knowledge of Markov chains or encryption techniques is required.
You are a spy who needs to obtain some crucial information from the British security service M1S. The agents of M1S are well aware that their Wi-Fi signals can be intercepted, their Android/iOS security vulnerabilities exploited etc., so all of them are using Nokia 3310’s to transmit text information which is typed using the T9 auto-completion.
You had previously hacked the phones to be delivered to the intelligence agency and had installed keyloggers under their glorious plastic keyboards, so now you receive sequences of numbers corresponding to the letters they typed, so “the eagle has left the nest alert the agents” becomes
But wait! Some T9 sequences are ambiguous (“6263” could be “name”, “mane” or “oboe”; the more obscure, the more suspicious it gets!), so what do you do? You know that the only entrance examination M1S uses is summarising Marcel Proust’s masterpiece “Remembrance of Things Past” in 15 seconds, so you want to pick the word that comes next after the previous one according to its frequency distribution in the entire chef-d’œuvre of Proust!
Can you crack the code and obtain what could be the original message?
The principle of T9
The T9 auto-completion mechanism can be described as follows. It maps alphabetic characters to numbers as shown on the picture above.
abc -> 2 def -> 3 ghi -> 4 jkl -> 5 mno -> 6 pqrs -> 7 tuv -> 8 wxyz -> 9 <space> -> 0 <other> -> <is deleted>
The T9 decryptor receives a sequence of digits and tries to guess the word that could be typed with those keypresses. It might use a standard frequency table, but we are going one step further and predicting the next word using a Markov chain!
The corpus is this heavily stripped version of Proust’s “Remembrance of Things Past” (
s/['’]s //g and
s/[^a-zA-Z ]//g — begone confusing possessive
's!) originally published on the University of Adelaide website (the text of this work is in the Public Domain in Australia).
The whole text must be analysed as one string, as one long sentence, as one long vector of words (whichever is more convenient for your language), stripped of linebreaks, and split into words at spaces. (I do not supply a single-paragraph file because such might be frowned upon by github tools.)
How do I read the whole text as one string / sentence? An example in R:
p_raw <- read.table("proust.txt", sep="\t") # Because there are no tabs p_vec <- as.character(p_raw$V1) # Conversion to character vector p_str <- paste(p_vec, collapse=" ") # One long string with spaces p_spl <- strsplit(p_str, split=" ")[] # Vector of 1360883 words proust <- p_spl[p_spl!=""] # Remove empty entries — 1360797
Given a sequence of digits as a number, return a possible text string that could be typed using the corresponding T9 keys using a probabilty chain to predict the next word X based on this training text treated as one long sentence.
If X is the first T9-word of the text and there are multiple guesses, pick one at random, otherwise pick the only one possible.
For all subsequent T9-words X(i) preceded by a word already deciphered w(i-1):
- If a T9-word X can be converted into a normal word x in one unique way, do it.
- If there are multiple conversion options available for X, say x1, x2, ..., look up the preceding guessed word w.
- If w is never followed by anything that maps to X in the original work of Proust, pick any of the possible x1, x2, ... at random.
- If w X always corresponds to w x1 in the original and there are no concurrent xi’s that could be mapped into X, pick x1.
- If w X can be converted to w x1, w x2, ... that can be found in the corpus, then count all possible xi’s that follow w and map to X in the corpus and pick xi with probability xi/(x1 + x2 + ...).
Example 2a. If the message is
489 could be
ivy (they occur in the corpus at least once),
7663 can be deciphered as
some (a very probable first word). If
some is never followed by anything that maps to
489 in the corpus, then pick
ivy at random with probability 0.5.
Example 2b. If the message is
2277437 could be
7663 can be deciphered as
some. If Proust always used
some carrier and never
some barrier, then pick
Example 2c. Suppose that you want to decipher the sequence
5363 was predicted as
7663 could be any of these:
some. You count the occurrences of the word following
lend in the sample corpus. Suppose you get something like this (just to illustrate):
T9 Word following lend Occurrences 7663 some 7 7663 pond 2 7663 roof 1
7663 is preceded by
lend, there is
7/(7+2+1)=70% probability that
7663 stands for
pond and 10%
roof. Your algorithm should produce
lend some in 70% cases,
lend pond in 20% cases etc.
You may safely assume that the agents use only a-z letters and spaces (no punctuation marks, no possessive
's, and no numbers).
You may also assume that the agents of M1S never use any words outside the scope of “Remembrance of Things Past” (which is a whopping vocabulary of 29,237 words!).
The T9 fuctionality was implemented in this challenge, so you might have a look at it.
If you need any help, probabilistic chains were gloriously tamed in this, that and the following challenges, but you do not even need to know the principle of such chains: everything is stated in the task.
--Inputs-- 20784250276960369 20784250276960369 84303245304270533808430637802537808430243687 94280343084306289072908608430262780482737 94280343084306289072908608430262780482737 --Possible outputs-- c quick brown fox a stick crown fox the eagle gas left the nest blest vie agents what did the navy pay to the coast guards what did the navy raz un the coast guards
- Standard loopholes apply.
- You do not know the original message, all you get is a sequence of digits and the file proust.txt that you just need to load in the memory / workspace / whatever. There is no need to have anything self-contained; assume
proust.txtis always accessible.
- Your algorithm must be able to produce different outputs with respective probabilities if more than one decryption option is probable according to the corpus (see Example 2c).
You need to stay as discreet as possible, so the shortest code wins!
P.S. The obvious benefit of this probabilistic algorithm is the fact that the probability you will get a true original string for an ambiguous deciphered string tends to one — just wait...
P.P.S. See also Prediction by Partial Matching.