JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: NSA Marathon Match Event 1 (Non-US)
Problem: Enigma

Problem Statement

    The enigma machine encodes and decodes messages through a sequence of rotors. Given an input, as typed by the machine's operator, the machine produces an encrypted output.



The Machine

A permutation of the letters A-Z is a one to one mapping from A-Z onto A-Z. For instance, A might map to H, B to G, C to C, and so on with each letter being used exactly once. A rotation of a permutation (in this problem) takes a permutation and increments each of the inputs and outputs. For instance, if A maps to H, B maps to G, and C maps to Z, a rotation of that permutation would map B to I, C to H, and D to A.



A number of permutations can be put together in sequence to obtain a different permutation. For instance, if the first permutation maps A to H and the second maps H to J, then the combination of the two maps A to J.



Each of the rotors in the Enigma machine can be thought of as the 26 rotations of a single permutation, where the current rotation is designated by one of the letters A-Z. The state of the rotors can thus be described by a three letter code. For instance, AHZ indicates that rotor 1 is set to rotation A, rotor 2 to rotation H and rotor 3 to permutation Z.



In addition to the rotors, the machine also contains a reflector which connected pairs of letters together. For instance, it might contains pairs (J,U) and (H,V), etc. The reflector always contains 13 pairs, each of which includes two unique letters.



When a key is pressed on the machine, the permutations from the rotors is applied. For instance the three permutations might map A to H, H to J and then J to Q. Next the reflector changes Q to it's paired letter. For instance (B,Q) might be one of the pairs in the reflector, changing Q to B. Next, the permutations from the three rotors are applied in reverse. Thus, if rotor 3 maps O to B, then it would map B to O in reverse. If rotors 2 and 1 map X to O and N to X, respectively, then these are applied in reverse to get N. Thus, the full sequence is A-H-J-Q-B-O-X-N. After each key press rotor 1 rotates to the next position. For instance, if the machine's rotors started in state AHZ, the first key press would be encoded using this state, and the rotors advance to BHZ. When the first rotor rotated from some letter x to letter x+1, the second rotor would also advance. Thus if x where J, JHZ would advance to KIZ. Similarily, the second rotor would cause the third rotor to advance when it rotated from y to y+1, for some y.



As a final security measure, a fixed permutation is also applied before rotor 1, and the inverse of that permutation is applied after rotor 1 (in reservse at the end). Thus, the full sequence of permutations is FIXED,ROTOR1,ROTOR2,ROTOR3,REFLECTOR,ROTOR3-1,ROTOR2-1,ROTOR1-1,FIXED-1.

Usage

Each day, a different FIXED permutation is chosen according to a secret code book. Additionally, a different set and ordering for the rotors is chosen, along with a different reflector. When the operator wants to transmit a message, he choses a random initial position for the rotors, such as ABC. He then choses another random sequence, say LOL. He then encoded LOL using the initial position ABC, and obtains three letters, like XYZ. He then sent ABC and XYZ to the message recipient. Next, he reset the rotor positions to LOL, encodes the message, and sends the encoded text.



To decode the message, the recipient sets his identically configured machine to the position ABC, and enters XYZ. Because of the way the machine is designed, this would output LOL. The recipient would then reset his machine to that position, and decode the message (which is exactly the same as encoding because, for a given machine configuration if A maps to J then J maps to A).



Problem

Your task is to crack this code. You will be given a number of transmissions, all using the same set of rotors in the same order and the same FIXED permutation and reflector. The messages will be formed by concatenating random English words. For each message, you should return you best guess as to the decoding. (Note that the decoded version will be 6 characters shorter than the encoded version which starts with configuration information.)



In addition to the messages, you will also be given a dictionary, containing the words used in the encoded messages. Finally, you will be given the decoded versions of some of the messages. A String[], decodings will contain one element for each message. These elements will be either "" or the decoded version of the message.

Scoring

Your score for each test case will be the square of the fraction of characters that you decoded correctly (not including those whose answers are given to you). Your overall score will be the sum of your individual scores, times 100.

Dictionary

You will be given a dictionary of words, along with their corresponding frequencies. You can download this dictionary and it will be available to your method as a String[], where each element is formatted as "WORD COUNT".

Test case generation

  1. All values not otherwise specified will be selected uniformly at random.
  2. To generate the FIXED permutation (and only the FIXED permutation), a value X will be chosen uniformly at random between 0 and 20. X of the letters will be chosen at random to be map to themselves (as in A->A). The remaining 26-X letters will be randomly permuted (and in the course of this random permutation may end up mapping to themselves).
  3. The number of messages, N, will be selected as floor(103+3.2*rand()), where rand() is a uniform randomly number in [0,1). Thus, N is in [1000,1584893].
  4. The number of decoded messages given to you, M, will be chosen uniformly in [0,100].
  5. The number of words in each message will be in [10,50].
  6. Each word will be selected at random from the dictionary mentioned above, with probability proportional to its frequency.

Offline Tester

Available at http://www.topcoder.com/contest/problem/Enigma/tester.html.
 

Definition

    
Class:Enigma
Method:decode
Parameters:String[], String[], String[]
Returns:String[]
Method signature:String[] decode(String[] messages, String[] decodings, String[] dictionary)
(be sure your method is public)
    
 

Notes

-Your return should include elements for all the messages, including those whose answers are given to you.
-There are 50 provisional test cases.
 

Constraints

-The memory limit is 1024M.
-The time limit is one minute per test case.
 

Examples

0)
    
seed = 1
1)
    
seed = 2
2)
    
seed = 3
3)
    
seed = 4
4)
    
seed = 5
5)
    
seed = 6
6)
    
seed = 7
7)
    
seed = 8
8)
    
seed = 9
9)
    
seed = 10

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.