ZOJ Problem Set - 4039
Your friend has just sent you a piece of message encrypted by an Enigma Machine! As a programmer, you decided to decrypt the message yourself. You searched the Internet and found the following information:
The Enigma Machine consists of three main components: the plugboard, 3 rotors and the reflector.Plugboard
You can regard the plugboard as a physical connection inside the machine. Suppose we have the plugboard setting "A-B, C-D", everytime we input A, we get B, and vice versa (input B, get A).
So under the "A-B, C-D" setting, if the input is a string "ABCDEFG", we'll get "BADCEFG".Rotor
Every rotor has two attributes, the internal Ring Setting and the external Message Key. Both of them are a character in the English alphabet.
If a character is fed into a rotor, the following four steps will happen in order:
Note that the above steps only applys when the character is inputted from the left. If the character is inputted from the right, we should look up $c_2$ in the "output" row of the rotor table, and get $c_3$ from the "input" row.
There are 5 types of rotors in total. Their rotor tables are shown below:
For example, assume rotor I's Message Key is A, Ring Setting is B. We have $\Delta$ = A - B = -1. When character A is input from the left, it has to add delta first (becomes Z), look up the table (becomes J), subtract delta (becomes K). Thus the output is K.Rotation of Rotor
Before processing a new character, the right-most rotor will rotate first, which means the Message Key will change to the next character in the alphabet (for example, from B to C, or from X to Y). Note that if the current Message Key is Z, it will change back to A. The Ring Setting is constant during the whole process.
But the rotate of the rotor is not this simple! When the rotor's Message Key reaches some specific character, it will make the next rotor (the rotor to its left) rotate as well!
For instance, let's assume we have rotors III, II and I arranged from left to right, with the current Message Key of rotor I being Q and current Message Key of rotor II being A. Before processing a new character, the Message Key of rotor I will turn to R. Then it triggers rotor II to rotate, so the Message Key of rotor II changes from A to B.Double Stepping
Another tricky point in the Enigma machine is the double stepping. It is a special mechnical structure in Enigma machine.
Double stepping only happens on the middle rotor. When the middle rotor is at its the "triggering" point, even if it is not triggered by the previous rotor (the rotor on its right), it will rotate itself, and then trigger the next rotor (the rotor on its left).
For instance, let's assume we have rotors III, II and I arranged from left to right, with the current Message Key of rotor III to be A, current Message Key of rotor II to be D, and current Message Key of rotor I to be Q.
Before processing a character, the right-most rotor (rotor I) rotates, so its Message Key becomes R. As "Q -> R" is the "triggering" point of rotor I, it triggers the rotation of rotor II as well, making the Message Key of rotor II to become E. The character is now processed.
Before processing the next character, the right-most rotor (rotor I) rotates, so its Message Key becomes S. But note that the middle rotor (rotor II) is at its "triggering" point! So rotor II also rotates, changing its Message Key from E to F, and triggers the rotation of rotor III, making its Message Key from A to B. The character is now processed.Reflector
The reflector is simple. It just maps the character from the first row of the following table to the second row:
The decryption of the message is done one character at the time. To decrypt a character $c$, do the following steps:
After reading the above information, you decided to write a program to imitate the decryption process of the Enigma Machine.
There are multiple test cases. The first line of the input contains an integer $T$ (about 100), indicating the number of test cases. For each test case:
The first line is a string $s$ ($|s| \le 1000$) consisting of uppercase English characters, indicating the message you need to decrypt.
The second line is a permutation of the uppercase English characters ABC...Z, indicating the setting of the plugboard. The $i$-th character $c_i$ means that if you input the $i$-th character in the alphabet, you will get $c_i$ as the output. It's guaranteed that the setting is legal.
The third line contains three integers (not seperated by a space) ranging from 1 to 5, indicating the type of three rotors from left to right.
The fourth line contains two strings $r$ and $m$ both of length 3, where $r$ indicates the Ring Settings of the rotors, and $m$ indicates the initial Message Keys of the rotors.
For each test case output one line, the decrypted message.
3 JLEERJGZFBUMQL BADCEFGHIJKLMNOPQRSTUVWXYZ 321 BAD ZDO WERFNSDDMUJASYZWQT VTLDKFYHPJECONMIQRSBUAWXGZ 514 ZLR SLJ WKODEZOQJORBSGBATETZGWVJYVPSUMREBWLZIWJRLMJVJHQNTTBUNEFPIJMLYBXBPFYSUDDRLSIQAIXKATFKZGUKSLAERH VTLDKFYHPJECONMIQRSBUAWXGZ 233 ZOJ JUN
ZOJMONTHLYJUNE GOODLUCKANDHAVEFUN THISISAVERYVERYLOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOONGMESSAGE
Author: FAN, Haoran; WENG, Caizhi
Source: ZOJ Monthly, June 2018