| | 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
- All values not otherwise specified will be selected uniformly at random.
- 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).
- 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].
- The number of decoded messages given to you, M, will be chosen uniformly
in [0,100].
- The number of words in each message will be in [10,50].
- 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.
|