Facebook puzzle

Yesterday night I tried to resolve a facebook puzzle, I found it interesting so here it is after cleaning up the code  a little bit.

Decoding encrypted text with dictionary and some secret inputs

Question Details:
Your task is to decode messages that were encoded with substitution ciphers. In a substitution cipher, all occurrences of a character are replaced by a different character. For example, in a cipher that replaces « a » with « d » and « b » with « e », the message « abb » is encoded as « dee ».

The exact character mappings that are used in the substitution ciphers will not be known to you. However, the dictionary of words that were used will be given. You will be given multiple encoded messages to decode (one per line) and they may use different substitution ciphers. The same substitution cipher is used on all of the words in a particular message.

For each scrambled message in the input, your program should output a line with the input line, followed by the string  » =  » (without the quotes), followed by the decoded message.

NOTE: All inputs are from stdin and output to stdout. The input will be exactly like how it’s given in the problem and your output should exactly match the given example output

Example:

input:
//dict
hello
there
yello
thorns
//secret
12334 51272
12334 514678


output:
12334 51272 = hello there
12334 514678 = hello thorns


Solution:
Download the eclipse solution here : FacebookPuzzle_SecretDecoder.zip or try it out online


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;

public class Solution{
	static Map<Integer, List> sDictionaryMap = new HashMap<Integer, List>();
    static boolean debug = false;

	public static void main (String args[]) {

	    try{

		    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		    String input;
            String section = null;

            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"))
                    {

                        List dict = null;
                        if(!sDictionaryMap.containsKey(input.length()))
                        {
                            dict = new ArrayList();
                            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)
                	System.out.println();

            }

            long end = System.currentTimeMillis();
            if(debug)
            	System.out.println("execution time: " + (end - start) +"ms");

	    }catch(IOException io){
		    io.printStackTrace();
	    }
   }

   public static class SubstitutionCiphersDecoder
   {
	   Map<Integer, List> mDictionaryMap = new HashMap<Integer, List>();
	   Map<Character, Character> mCharMap = new LinkedHashMap<Character, Character>();

	   /**
	    * Class used to decrypt substitution ciphers used to encrypt words
	    * @param dictionary of all the valid words
	    */
	   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
	    */
	   public String decode(String secret, boolean resetMapping)
	   {
		   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
	    */
	   public String decode(String secret, Map<Character, Character> mapping)
	   {
	       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
	    */
	   public Character decodeChar(Character secretChar, Map<Character, Character> mapping)
	   {
	       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(" ");
	       for(String secretWord: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);

	   }
   }

}

About the author Mino

Software engineer holding Masters degree in Computer Science, currently living in France. Passionate about new technology and dance.