Marathon Match 36
|| Problem Statement
| ||You are given a ciphertext which is an output of a known encryption method.
Your task is to decrypt this ciphertext.
The encryption method uses the message M and the key K as an input
and generates the ciphertext C using the following procedure:
The alphabet of the plaintext P and the key K consists of characters 'a'-'z' (codes 1-26), 'A'-'Z' (codes 27-52) and '0'-'9' (codes 53-62). To form the plaintext, all other characters are removed from message M.
Plaintext P is converted to ciphertext C using the following algorithm:
for i = 0 .. P.length
C[i] = P[i] XOR K[i%k];
K[i%k] = ( K[i%k] + P[i] ) mod 64;
k denotes the length of the key K.
You must return your guess for the plaintext.
Your score will be the number of correct letters in your return, divided by the length of the return. If you fail to return a string of the correct length in the allotted time, you will get a 0.
Letter i of return R is considered to be correct if it is the same as letter i of the plaintext P (this includes having the right capitalization).
Your overall score will be a sum of scores for individual test cases.
Each test case will be generated using a random article from Wikipedia as the message, and a random word as the key.
The random page feature on Wikipedia is used to fetch a random page. Only those sections of the page enclosed by <P> tags are used. All non-alphanumeric characters and all tags are then stripped. If the result is less than 2000 bytes (roughly), the page is discarded. The source of the program used to get the content is available for download:
WikiDownload.java. After compiling, run "java WikiDownload <number of pages>".
The key is chosen as a random word of at least 4 characters from the TWL word list. A random number between 0 and 999 is appended to the end of the chosen word. With probability 0.5 the first character is capitalized. Lowercase 'o' is then converted to '0' (zero) with probability 0.5 for each 'o'. Similarly, each lowercase 'l' (ell) is converted to '1' (one), each 'e' to '3', each 's' to '5', and each 't' to '7', all with probability 0.5.
|Method signature:||String getMessage(int cipherText)|
|(be sure your method is public)|
|Sample Call:||val = Words.getWords();|
|-||The memory limit is 1 GB and the time limit is 10 seconds (which includes only time spent in your code).|
|-||There are 9 example test cases and 500 full submission test cases.|
|-||The downloads below have some characters other than 'a'-'z', 'A'-'Z' and '0'-'9'. These are all removed when testing.|
|-||You can access the word list be calling a static method getWords in class Words. This method will return a String with the TWL word list.|
|-||Your code must be under 300K.|
Article = San_Carlos_Seminary.txt
Key = oracularly588
Article = Vermonster.txt
Key = M0rtali7ie5606
Article = Shep_Messing.txt
Key = Ru7henic592
Article = Modular_building.txt
Key = cornhusk332
Article = Frankenstein%27s_Monster_%28Toho%29.txt
Key = Coxcombic854
Article = Out_of_My_Mind_%28Buffy_episode%29.txt
Key = Pyxidium689
Article = Eurovision_Song_Contest_1973.txt
Key = Picom0le834
Article = Duamutef.txt
Key = dup3r5220
Article = House_of_Savoy.txt
Key = ski773ring333
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.