DecodeMoveToFront

TCCC '03 Semifinals 4 · 2003-04-04 · by vorthys

TCCC '03 Semifinals 4 · 2003-04-04 · by vorthys · Encryption/Compression

Show categories

Class Name: DecodeMoveToFront

Return Type: String

Method Name: findKey

Arg Types: (vector<string>, vector<string>)

Problem Statement

Consider a simple encryption algorithm based on the move-to-front heuristic. Both the unencrypted (plaintext) and encrypted (ciphertext) messages are Strings composed of uppercase letters ('A'-'Z') and spaces (' '). The encryption algorithm maintains a state which is a permutation of the 27 possible characters. The key used to encrypt and decrypt messages is the initial permutation.

Encryption processes the plaintext from left to right, outputting one character of the ciphertext for each character of the plaintext. At each position of the plaintext, the encryption algorithm performs the following steps:

Find the (zero-based) position of the plaintext character in the current permutation.
If the position is 0-25, output 'A'-'Z', respectively. If the position is 26, output a space.
Move the plaintext character to the front of the permutation (ie, delete it from its current position in the permutation and re-insert it at the front).

For example, starting with a key "ZYXWVUTSRQPON MLKJIHGFEDCBA" and a plaintext "TPCDR" (all quotes for clarity only), encryption would proceed as follows:

State = "ZYXWVUTSRQPON MLKJIHGFEDCBA". 'T' is in position 6, output 'G'.
State = "TZYXWVUSRQPON MLKJIHGFEDCBA". 'P' is in position 10, output 'K'.
State = "PTZYXWVUSRQON MLKJIHGFEDCBA". 'C' is in position 24, output 'Y'.
State = "CPTZYXWVUSRQON MLKJIHGFEDBA". 'D' is in position 24, output 'Y'.
State = "DCPTZYXWVUSRQON MLKJIHGFEBA". 'R' is in position 11, output 'L'.

The final ciphertext is "GKYYL". (The final state is "RDCPTZYXWVUSQON MLKJIHGFEBA", but that is discarded by the algorithm.)

You will be given both the plaintexts and the ciphertexts of several messages, where the i-th ciphertext is believed to be the encrypted form of the i-th plaintext, and all the messages are believed to have been encrypted using the same key. Your task is to recover and return that key (as a String). If the messages do not contain enough information to fully determine the key, the output of your method should summarize the set of possible keys by placing a '-' character at any position of the permutation that has not been narrowed down to a single possible character. If no key exists that could have been used to encrypt all the messages, output "ERROR".

Notice that, when encrypting multiple messages, the state is not carried over from one message to the next, but rather is re-initialized for each message.

Constraints

plaintexts and ciphertexts contain the same number of elements (between 1 and 20, inclusive).
Element i of plaintexts has the same length as element i of ciphertexts (between 1 and 50 characters, inclusive).
Elements of plaintexts and ciphertexts contain uppercase letters ('A'-'Z') and spaces only.

Examples

{"TPCDR"}
{"GKYYL"}
Returns: "------T-R-P------------DC--"

The example above, but the characters that were not used could have been anywhere in the initial permutation.

{"A","B"}
{"X","X"}
Returns: "ERROR"

A and B cannot both be in position 23 of the key.

{"A","A"}
{"X","Y"}
Returns: "ERROR"

{"ABA"}
{"XYX"}
Returns: "ERROR"

{"ABCDEFGHIJKL NOPQRSTUVWXYZ"}
{"ABCDEFGHIJKLMNOPQRSTUVWXYZ"}
Returns: "ABCDEFGHIJKL NOPQRSTUVWXYZM"

When 26 characters have been used, the other is known by process of elimination.

{"HELLO"}
{"HOWDY"}
Returns: "ERROR"

The second 'L' should be encoded as an 'A'.

11)

{"HI"}
{"AA"}
Returns: "ERROR"

The 'I' cannot be encoded as 'A' because 'H' is guaranteed to be in that position.

Submissions are judged against all 51 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DecodeMoveToFront with a public method string findKey(vector<string> plaintexts, vector<string> ciphertexts) · 51 test cases · 2 s / 256 MB per case