import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.lang.StringBuilder;
import java.io.IOException;
class Ideone{
static Map
<Integer, List
> sDictionaryMap
= new HashMap
<Integer, List
>(); static boolean debug = false;
public static void main
(String args
[]) {
try{
List<String> secretList = new ArrayList<String>();
while((input=br.readLine())!=null){
if(input.startsWith("//"))
{
section = input;
continue;
}
else if(section !=null)
{
if(section.equals("//dict"))
{
if(!sDictionaryMap.containsKey(input.length()))
{
sDictionaryMap.put(input.length(), dict);
}
else
{
dict = sDictionaryMap.get(input.length());
}
dict.add(input);
}
else if (section.equals("//secret"))
{
secretList.add(input);
}
}
}
long start
= System.
currentTimeMillis(); for(int i=0; i<secretList.size(); i++)
{
String secretLine
= secretList.
get(i
); StringBuilder sb = new StringBuilder();
sb.append(secretLine + " = ");
sb.append(new SubstitutionCiphersDecoder(sDictionaryMap).decode(secretLine, true));
System.
out.
println(sb.
toString());
if(debug)
}
long end
= System.
currentTimeMillis(); if(debug)
System.
out.
println("execution time: " + (end
- start
) +"ms");
io.printStackTrace();
}
}
public static class SubstitutionCiphersDecoder
{
/**
* Class used to decrypt substitution ciphers used to encrypt words
* @param dictionary of all the valid wor
* 02f0196faf9446333baf84c6bef05dd9ds
*/
public SubstitutionCiphersDecoder
(Map
<Integer, List
> dictionary
) {
mDictionaryMap = dictionary;
}
/**
* Decode the secret with a specific mapping
* @param secret the encoded string, can be a word or several words separated by a space
* @param resetMapping tells if the characters map need to be rebuild from scratch
* @return the decoded string with all the known char from mapping, keep the unknown ones
*/
{
if(resetMapping)
buildCharMap(secret);
return decode(secret, mCharMap);
}
/**
* Decode the secret with a specific mapping
* @param secret the encoded string, can be a word or several words separated by a space
* @param mapping the characters mapping to decode the secret with
* @return the decoded string with all the known char from mapping, keep the unknown ones
*/
{
StringBuilder result = new StringBuilder();
for(int i=0; i<secret.length(); i++)
{
result.append(decodeChar(secret.charAt(i), mapping));
}
return result.toString();
}
/**
* Decode a character with a specific mapping
* @param secretChar the encoded character
* @param mapping the characters mapping to decode the secret with
* @return the decoded character if it is known by the mapping, or the original encoded character otherwise
*/
{
Character decodedChar
= mapping.
get(secretChar
); return ((decodedChar!=null)?decodedChar:secretChar);
}
/**
* Test if the secret can be decoded
* @param secretWord the encoded string
* @param mapping the characters mapping to decode the secret with
* @return true if the decoded string exist in the dictionary, false otherwise
*/
private boolean canDecode
(String secretWord, Map
<Character, Character
> mapping
) {
List potentialMatches
= mDictionaryMap.
get(secretWord.
length()); return potentialMatches.contains(decode(secretWord, mapping));
}
/**
* Build the characterMap, for each word in the secret line, try a brute force attack to reveal the character mapping
* @param secretLine is the encoded string
*/
private void buildCharMap
(String secretLine
) {
//Reset charMap
mCharMap.clear();
mCharMap.put(' ', ' ');
String[] split
= secretLine.
split(" "); {
if(debug)
System.
out.
println("secretWord:"+secretWord
);
List<String> potentialMatches = mDictionaryMap.get(secretWord.length());
for(String potentialMatch
: potentialMatches
) {
if(debug)
System.
out.
println("fix mapping for potentialMatch:"+potentialMatch
);
Map
<Character, Character
> fixedCharMapAttempt
= new HashMap
<Character, Character
>(mCharMap
); for(int index=0; index<potentialMatch.length(); index++)
{
//if mapping doesn't not yet exist for the encoded char, or if the character already mapped is not valid for another encountered character
if(!fixedCharMapAttempt.containsKey(secretWord.charAt(index)) || !decodeChar(secretWord.charAt(index), fixedCharMapAttempt).equals(potentialMatch.charAt(index)) )
{
//Same character should not be mapped twice, by two different key.
if(!fixedCharMapAttempt.containsValue(potentialMatch.charAt(index)))
{
fixedCharMapAttempt.put(secretWord.charAt(index), potentialMatch.charAt(index));
if(debug)
System.
out.
println("mapping for:" + secretWord.
charAt(index
) + " is " + potentialMatch.
charAt(index
) + " decode:"+decode
(secretWord, fixedCharMapAttempt
)+ " isInDict:"+canDecode
(secretWord, fixedCharMapAttempt
)); }
}
}
//save the character mapping only if is usefull
if(canDecode(secretWord, fixedCharMapAttempt))
mCharMap.putAll(fixedCharMapAttempt);
else if(debug)
System.
out.
println("reverting..."); }
}
if(debug)
System.
out.
println("buildCharMap:"+mCharMap
);
}
}
}