Facebook Secret Decoder Programming Exercise

README.txt

Question 1 / 1 (secret decoder)
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 file:
 //dict
 hello
 there
 yello
 thorns
 //secret
 12334 51272
 12334 514678


output:


12334 51272 = hello there
12334 514678 = hello thorns

solution.rb

require 'pp'

def decode(dictionary, messages)
    messages.each do |message|
        line = ''
        words = message.split ' '

        matches = {}
        words.each do |word|
            matches[word] = possible_word_matches(word, dictionary[word.length])
            line << word << ' '
        end

        line << '= '

        possible_sentences(words, matches).compact.each do |match|
            line << match << ' '
        end

        puts line.chomp
    end
end

# Check word by word all possible matches
def possible_word_matches(word, matches)
    possible_words = []

    word_characters = word.split ''

    matches.each do |match|
        possible = true

        assigned_alphabets = {}
        match_characters = match.split ''
        match_characters.each_with_index do |char, i|
            if assigned_alphabets.key? char
                if assigned_alphabets[char] != word_characters[i]
                    possible = false
                    break
                end
            else
                assigned_alphabets[char] = word_characters[i]
            end
        end

        if possible
            possible_words << [match, assigned_alphabets]
        end
    end

    possible_words
end

# Check amongst all the words that the combination is possible
# Expensive exponential recursive search follows
def possible_sentences(words, matches, assigned_alphabets = {})
    result = []
    if words.length == 0
        return []
    end

    word = words[0]
    matches[word].each do |(match, assignment)|
        # try to merge assignment hashes and see if conflicts arise
        conflict = false
        merged = assigned_alphabets.merge(assignment) do |key, oldval, newval|
            if oldval != newval
                conflict = true
                break
            else
                newval
            end
        end

        if conflict
            next
        else
            recursive_result = possible_sentences(words.slice(1..-1), matches, merged)
            if recursive_result.nil?
                next
            else
                result = [match].concat recursive_result
                break
            end
        end
    end

    if result.empty?
        nil
    else
        result
    end
end

def main
    dictionary = {}
    secret = []
    input_stage = 0

    while input = gets do
        input.chomp!
        if input == "//dict"
            input_stage = 0
        elsif input == "//secret"
            input_stage = 1
        elsif input_stage == 0
            length = input.length
            unless dictionary.key? length
                dictionary[length] = []
            end
            dictionary[length] << input
        elsif input_stage == 1
            secret << input
        end
    end

    decode(dictionary, secret)

    0
end

exit main if __FILE__ == $PROGRAM_NAME