TopCoder problem "DecodeMoveToFront" used in TCCC '03 Semifinals 4 (Division I Level Two)

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:
  1. State = "ZYXWVUTSRQPON MLKJIHGFEDCBA". 'T' is in position 6, output 'G'.
  2. State = "TZYXWVUSRQPON MLKJIHGFEDCBA". 'P' is in position 10, output 'K'.
  3. State = "PTZYXWVUSRQON MLKJIHGFEDCBA". 'C' is in position 24, output 'Y'.
  4. State = "CPTZYXWVUSRQON MLKJIHGFEDBA". 'D' is in position 24, output 'Y'.
  5. 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.



Parameters:String[], String[]
Method signature:String findKey(String[] plaintexts, String[] ciphertexts)
(be sure your method is public)


-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.


Returns: "------T-R-P------------DC--"
The example above, but the characters that were not used could have been anywhere in the initial permutation.
Returns: "ERROR"
A and B cannot both be in position 23 of the key.
Returns: "ERROR"
The second 'L' should be encoded as an 'A'.
Returns: "FOUR SCEANDVYGTH-----------"
Returns: "ERROR"
The 'I' cannot be encoded as 'A' because 'H' is guaranteed to be in that position.

Problem url:

Problem stats url:




zoidal , lbackstrom , brett1479

Problem categories: