Marathon Match 36 - Marathon Match 36

Key Information

Register
Submit
The challenge is finished.

Timezone:Etc/UTC

Registration

Starts

Jun 23, 2008

16:00

Ends

Jun 30, 2008

16:00

Submission

Starts

Jun 23, 2008

16:00

Ends

Jun 30, 2008

16:00

Review

Starts

Jun 30, 2008

16:00

Ends

Jun 30, 2008

16:00

Winners Announced

Jun 30, 2008

16:00

Challenge Overview

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)
    
 

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)
    
"San_Carlos_Seminary.txt oracularly588"
Returns: 
"Article = San_Carlos_Seminary.txt
Key = oracularly588
<a href=http://www.topcoder.com/contest/problem/XORPlusEncryption/San_Carlos_Seminary.txt>Download</a>
"
1)
    
"Vermonster.txt M0rtali7ie5606"
Returns: 
"Article = Vermonster.txt
Key = M0rtali7ie5606
<a href=http://www.topcoder.com/contest/problem/XORPlusEncryption/Vermonster.txt>Download</a>
"
2)
    
"Shep_Messing.txt Ru7henic592"
Returns: 
"Article = Shep_Messing.txt
Key = Ru7henic592
<a href=http://www.topcoder.com/contest/problem/XORPlusEncryption/Shep_Messing.txt>Download</a>
"
3)
    
"Modular_building.txt cornhusk332"
Returns: 
"Article = Modular_building.txt
Key = cornhusk332
<a href=http://www.topcoder.com/contest/problem/XORPlusEncryption/Modular_building.txt>Download</a>
"
4)
    
"Frankenstein%27s_Monster_%28Toho%29.txt Coxcombic854"
Returns: 
"Article = Frankenstein%27s_Monster_%28Toho%29.txt
Key = Coxcombic854
<a href=http://www.topcoder.com/contest/problem/XORPlusEncryption/Frankenstein%27s_Monster_%28Toho%29.txt>Download</a>
"
5)
    
"Out_of_My_Mind_%28Buffy_episode%29.txt Pyxidium689"
Returns: 
"Article = Out_of_My_Mind_%28Buffy_episode%29.txt
Key = Pyxidium689
<a href=http://www.topcoder.com/contest/problem/XORPlusEncryption/Out_of_My_Mind_%28Buffy_episode%29.txt>Download</a>
"
6)
    
"Eurovision_Song_Contest_1973.txt Picom0le834"
Returns: 
"Article = Eurovision_Song_Contest_1973.txt
Key = Picom0le834
<a href=http://www.topcoder.com/contest/problem/XORPlusEncryption/Eurovision_Song_Contest_1973.txt>Download</a>
"
7)
    
"Duamutef.txt dup3r5220"
Returns: 
"Article = Duamutef.txt
Key = dup3r5220
<a href=http://www.topcoder.com/contest/problem/XORPlusEncryption/Duamutef.txt>Download</a>
"
8)
    
"House_of_Savoy.txt ski773ring333"
Returns: 
"Article = House_of_Savoy.txt
Key = ski773ring333
<a href=http://www.topcoder.com/contest/problem/XORPlusEncryption/House_of_Savoy.txt>Download</a>
"

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)2020, TopCoder, Inc. All rights reserved.