TopCoder problem "MorselikeCode" used in SRM 364 (Division II Level One)



Problem Statement

    

Marge is rather concerned about the hoodlums that her son has been spending time with. Aside from all of the time spent at the arcade, they communicate with each other through encrypted messages. As a concerned parent, Marge wants to discover what the boys are talking about.

Marge knows parts of the boys' code library, given as a String[]. Each element is formatted as "C SEQUENCE" (quotes for clarity), where C is an uppercase letter, SEQUENCE consists of only '-' and '.' characters, and exactly one space separates the two. When writing their message, the boys will replace C with SEQUENCE, separating multiple letters with spaces. So, if O is represented as "---" and S is represented as "...", then the message "SOS" can be encoded as "... --- ...".

Marge has recovered an encoded message that she would like to decode. Unfortunately, she does not have a full copy of the library, so there may be some SEQUENCEs that do not correspond to any entries in the library; if this happens, you are to replace it with a '?' (Marge is a smart mom, and might be able to figure out what the word is with only partial information). You are to return a String containing the decoded message.

 

Definition

    
Class:MorselikeCode
Method:decrypt
Parameters:String[], String
Returns:String
Method signature:String decrypt(String[] library, String message)
(be sure your method is public)
    
 

Constraints

-library will contain between 1 and 50 elements, inclusive.
-Each element of library will contain between 3 and 50 characters, inclusive.
-Each element of library will be formatted as "C SEQUENCE" as described in the problem statement.
-In each element of library, C will be an uppercase letter ('A'-'Z').
-In each element of library, SEQUENCE will consist only of '.' and '-'.
-There will be no duplicate SEQUENCEs in library.
-message will contain between 1 and 50 characters, inclusive.
-Each character of message will be '-', '.', or a space (' ').
-There will be no leading, trailing, or consecutive spaces in message.
 

Examples

0)
    
{"O ---",
 "S ..."}
"... --- ..."
Returns: "SOS"
The example from the problem statement.
1)
    
{"O ---"}
"... --- ..."
Returns: "?O?"
This time we don't have the S, so we replace the three dashes with question marks.
2)
    
{"H -",
 "E .",
 "L --",
 "L ..",
 "O -."}
"- . -- .. -."
Returns: "HELLO"
Note that the clever boys can have multiple ways to encode the same letter.
3)
    
{"H -.-.-.-.-.-.-.-.-.-.",
 "I .-.-.-.-.-.-.-.-.-.-",
 "K -.-.-.-.-.",
 "E .-.-.-.-.-"}
"-.-.-.-.-.-.-.-.-.-. .-.-.-.-.-.-.-.-.-.-"
Returns: "HI"
A long message doesn't always mean a long word.
4)
    
{"O ---",
 "S ...",
 "B -...",
 "T -",
 "R .-.",
 "E .",
 "N -.",
 "X -..-",
 "D -.." }
"-... --- ... - --- -. .-. . -.. ... --- -..-"
Returns: "BOSTONREDSOX"
5)
    
{"B -...",
 "N -.",
 "H ....",
 "O --",
 "Z --..",
 "G ---",
 "I ..",
 "J .---" }
"--- -- -... .- -. .- -. .-"
Returns: "GOB?N?N?"
6)
    
{"A --",
 "B -.",
 "N ...-",
 "I --..",
 "F -.-.-."}
"-. -- -.-.-. -.-.-. --- --.. ...- .-..--."
Returns: "BAFF?IN?"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8152

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10778&pm=8152

Writer:

connect4

Testers:

PabloGilberto , radeye , Olexiy , ivan_metelsky

Problem categories:

Encryption/Compression