fork(1) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.FileInputStream;
  3. import java.io.InputStreamReader;
  4. import java.util.LinkedHashMap;
  5. import java.util.List;
  6. import java.util.ArrayList;
  7. import java.util.Map;
  8. import java.util.HashMap;
  9. import java.lang.StringBuilder;
  10. import java.io.IOException;
  11.  
  12. class Ideone{
  13.     static Map<Integer, List> sDictionaryMap = new HashMap<Integer, List>();
  14.     static boolean debug = false;
  15.  
  16.     public static void main (String args[]) {
  17.  
  18.         try{
  19.  
  20.            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  21.  
  22.             String input;
  23.             String section = null;
  24.  
  25.             List<String> secretList = new ArrayList<String>();
  26.  
  27.             while((input=br.readLine())!=null){
  28.                 if(input.startsWith("//"))
  29.                 {
  30.                     section = input;
  31.  
  32.                     continue;
  33.                 }
  34.                 else if(section !=null)
  35.                 {
  36.                     if(section.equals("//dict"))
  37.                     {
  38.  
  39.                         List dict = null;
  40.                         if(!sDictionaryMap.containsKey(input.length()))
  41.                         {
  42.                             dict = new ArrayList();
  43.                             sDictionaryMap.put(input.length(), dict);
  44.                         }
  45.                         else
  46.                         {
  47.                             dict = sDictionaryMap.get(input.length());
  48.                         }
  49.                         dict.add(input);
  50.                     }
  51.                     else if (section.equals("//secret"))
  52.                     {
  53.                         secretList.add(input);
  54.                     }
  55.                 }
  56.  
  57.             }
  58.  
  59.             long start = System.currentTimeMillis();
  60.             for(int i=0; i<secretList.size(); i++)
  61.             {
  62.  
  63.                 String secretLine = secretList.get(i);
  64.                 StringBuilder sb = new StringBuilder();
  65.                 sb.append(secretLine + " = ");
  66.                 sb.append(new SubstitutionCiphersDecoder(sDictionaryMap).decode(secretLine, true));
  67.                 System.out.println(sb.toString());
  68.  
  69.                 if(debug)
  70.                     System.out.println();
  71.  
  72.             }
  73.  
  74.             long end = System.currentTimeMillis();
  75.             if(debug)
  76.                 System.out.println("execution time: " + (end - start) +"ms");
  77.  
  78.         }catch(IOException io){
  79.             io.printStackTrace();
  80.         }
  81.    }
  82.  
  83.    public static class SubstitutionCiphersDecoder
  84.    {
  85.        Map<Integer, List> mDictionaryMap = new HashMap<Integer, List>();
  86.        Map<Character, Character> mCharMap = new LinkedHashMap<Character, Character>();
  87.  
  88.        /**
  89.         * Class used to decrypt substitution ciphers used to encrypt words
  90.         * @param dictionary of all the valid wor
  91.         * 02f0196faf9446333baf84c6bef05dd9ds
  92.         */
  93.        public SubstitutionCiphersDecoder(Map<Integer, List> dictionary)
  94.        {
  95.            mDictionaryMap = dictionary;
  96.        }
  97.  
  98.        /**
  99.         * Decode the secret with a specific mapping
  100.         * @param secret the encoded string, can be a word or several words separated by a space
  101.         * @param resetMapping tells if the characters map need to be rebuild from scratch
  102.         * @return the decoded string with all the known char from mapping, keep the unknown ones
  103.         */
  104.        public String decode(String secret, boolean resetMapping)
  105.        {
  106.            if(resetMapping)
  107.                buildCharMap(secret);
  108.            return decode(secret, mCharMap);
  109.        }
  110.  
  111.        /**
  112.         * Decode the secret with a specific mapping
  113.         * @param secret the encoded string, can be a word or several words separated by a space
  114.         * @param mapping the characters mapping to decode the secret with
  115.         * @return the decoded string with all the known char from mapping, keep the unknown ones
  116.         */
  117.        public String decode(String secret, Map<Character, Character> mapping)
  118.        {
  119.            StringBuilder result = new StringBuilder();
  120.            for(int i=0; i<secret.length(); i++)
  121.            {
  122.                result.append(decodeChar(secret.charAt(i), mapping));
  123.            }
  124.  
  125.            return result.toString();
  126.        }
  127.  
  128.        /**
  129.         * Decode a character with a specific mapping
  130.         * @param secretChar the encoded character
  131.         * @param mapping the characters mapping to decode the secret with
  132.         * @return the decoded character if it is known by the mapping, or the original encoded character otherwise
  133.         */
  134.        public Character decodeChar(Character secretChar, Map<Character, Character> mapping)
  135.        {
  136.            Character decodedChar = mapping.get(secretChar);
  137.            return ((decodedChar!=null)?decodedChar:secretChar);
  138.        }
  139.  
  140.        /**
  141.         * Test if the secret can be decoded
  142.         * @param secretWord the encoded string
  143.         * @param mapping the characters mapping to decode the secret with
  144.         * @return true if the decoded string exist in the dictionary, false otherwise
  145.         */
  146.        private boolean canDecode(String secretWord, Map<Character, Character> mapping)
  147.        {
  148.            List potentialMatches = mDictionaryMap.get(secretWord.length());
  149.            return potentialMatches.contains(decode(secretWord, mapping));
  150.        }
  151.  
  152.        /**
  153.         * Build the characterMap, for each word in the secret line, try a brute force attack to reveal the character mapping
  154.         * @param secretLine is the encoded string
  155.         */
  156.        private void buildCharMap(String secretLine)
  157.        {
  158.            //Reset charMap
  159.            mCharMap.clear();
  160.            mCharMap.put(' ', ' ');
  161.  
  162.            String[] split = secretLine.split(" ");
  163.            for(String secretWord:split)
  164.            {
  165.                if(debug)
  166.                    System.out.println("secretWord:"+secretWord);
  167.  
  168.                List<String> potentialMatches = mDictionaryMap.get(secretWord.length());
  169.                for(String potentialMatch : potentialMatches)
  170.                {
  171.  
  172.                    if(debug)
  173.                        System.out.println("fix mapping for potentialMatch:"+potentialMatch);
  174.  
  175.                    Map<Character, Character> fixedCharMapAttempt = new HashMap<Character, Character>(mCharMap);
  176.                    for(int index=0; index<potentialMatch.length(); index++)
  177.                    {
  178.                        //if mapping doesn't not yet exist for the encoded char, or if the character already mapped is not valid for another encountered character
  179.                        if(!fixedCharMapAttempt.containsKey(secretWord.charAt(index)) || !decodeChar(secretWord.charAt(index), fixedCharMapAttempt).equals(potentialMatch.charAt(index)) )
  180.                        {
  181.                            //Same character should not be mapped twice, by two different key.
  182.                            if(!fixedCharMapAttempt.containsValue(potentialMatch.charAt(index)))
  183.                            {
  184.                                fixedCharMapAttempt.put(secretWord.charAt(index), potentialMatch.charAt(index));
  185.  
  186.                                if(debug)
  187.                                    System.out.println("mapping for:" + secretWord.charAt(index) + " is " + potentialMatch.charAt(index) + " decode:"+decode(secretWord, fixedCharMapAttempt)+ " isInDict:"+canDecode(secretWord, fixedCharMapAttempt));
  188.                            }
  189.                         }
  190.  
  191.                    }
  192.  
  193.                    //save the character mapping only if is usefull
  194.                    if(canDecode(secretWord, fixedCharMapAttempt))
  195.                        mCharMap.putAll(fixedCharMapAttempt);
  196.  
  197.                    else if(debug)
  198.                        System.out.println("reverting...");
  199.                }
  200.            }
  201.  
  202.            if(debug)
  203.                System.out.println("buildCharMap:"+mCharMap);
  204.  
  205.        }
  206.    }
  207.  
  208. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
//dict
hello
there
yello
thorns
//secret
12334 51272
12334 514678
stdout
copy 
12334 51272 = hello there
12334 514678 = hello thorns
https://ideone.com/EHHFay
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!