JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 36
Problem: XORPlusEncryption

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:
  1. 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.
  2. 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.



 

Definition

    
Class:XORPlusEncryption
Method:getMessage
Parameters:int[]
Returns:String
Method signature:String getMessage(int[] cipherText)
(be sure your method is public)
 

Available Libraries

    
Class:Words
Method:getWords
Parameters:
Returns:String[]
Sample Call:val = Words.getWords();
    
 

Notes

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

Examples

0)
    
Article = San_Carlos_Seminary.txt
Key = oracularly588
Download
1)
    
Article = Vermonster.txt
Key = M0rtali7ie5606
Download
2)
    
Article = Shep_Messing.txt
Key = Ru7henic592
Download
3)
    
Article = Modular_building.txt
Key = cornhusk332
Download
4)
    
Article = Frankenstein%27s_Monster_%28Toho%29.txt
Key = Coxcombic854
Download
5)
    
Article = Out_of_My_Mind_%28Buffy_episode%29.txt
Key = Pyxidium689
Download
6)
    
Article = Eurovision_Song_Contest_1973.txt
Key = Picom0le834
Download
7)
    
Article = Duamutef.txt
Key = dup3r5220
Download
8)
    
Article = House_of_Savoy.txt
Key = ski773ring333
Download

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.