Problem Statement |
| | A transposition cipher is a cipher which rearranges the plaintext characters without changing them.
The secret key for a cipher is the order in which the characters were shuffled.
Your task is to break the following transposition cipher.
To encrypt the message M which is L characters long,
N is chosen as ceil(sqrt(L)),
and the characters of the message are written one-by-one to a N x N grid. The starting cell is chosen randomly,
and on each step we:
-
write the current character of the message to the current cell of the grid,
-
move to the next character and next cell. The process of choosing the next cell is described with the following pseudocode:
for d = 3 .. (maximal distance from the current cell to any cell of the grid)
continue to the next iteration with probability 0.2
build the set of cells which
1) are at distance d from the current cell
2) are not in the same row or same column with the current cell
3) don't have a character written to them yet
if the set is empty continue to the next iteration
choose a random cell from the set
If the described process failed to write all the characters to the grid, it is repeated from scratch.
Finally, to convert the grid to the ciphertext, the characters are read rowwise and written in one line. The cells without characters and the spaces are replaced with '.' characters.
You are given the ciphertext produced by this cipher and the sequence of distances between the cells which were filled on successive steps delta. You must return your guess for the message. The length of your return must be equal to the length of the original message (you can deduce it as delta.length()+1). Your return should contain only characters 'A'-'Z' and '.' instead of a space.
Your score for the test case will be the length of the longest common substring of the actual message and your guess, divided by the length of the actual message. Your overall score will be a sum of scores for individual test cases.
Test cases are generated by first choosing a random line from the source text which is at least 25 characters long (after removing characters which are not 'a'-'z', 'A'-'Z' or spaces and replacing several consecutive spaces with one space).
Message length L is chosen randomly between 25 and the length of the chosen line, and a prefix of length L is extracted from the chosen line to be used as the message. The prefix is then extended to the next space character (or the end of the line) so that the break does not occur in the middle of a word.
After this, the message is encoded as described above, with distances between the current cell and the next cell at each step being stored to delta.
An offline testing tool (along with the corpus) may be downloaded at http://www.topcoder.com/contest/problem/KnightsMoveCipher/offline.html |
| |
Definition |
| | | Class: | KnightsMoveCipher | | Method: | decipher | | Parameters: | String, int[] | | Returns: | String | | Method signature: | String decipher(String ciphertext, int[] delta) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The distance between cells (row1, col1) and (row2, col2) is abs(row1-row2) + abs(col1-col2). |
| - | For more details on the test case generation and cipher implementation see the visualizer source. |
| - | Any kind of invalid return results in a zero score for this test case. |
| - | The memory limit is 1 GB and the time limit is 20 seconds (which includes only time spent in your code). |
| - | The source code size limit is 500KB. |
| - | There are 10 example test cases and 100 full submission test cases. |
| - | A method Statistics.getWords() will return a String[], each element of which is formatted as a word, followed by a space and the number of occurrences of the word in the corpus. |
| - | Each line of the corpus is an abstract from the arXiv e-Print archive (arxiv.org). |
| |
Examples |
| 0) | |
| | |
| 1) | |
| | |
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | |
| 5) | |
| | |
| 6) | |
| | |
| 7) | |
| | |
| 8) | |
| | |
| 9) | |
| | |