basicCryptanalysis.rb

# Used to find a unique pattern of repeating characters found in a given word
def find_pattern(word)
    pattern = Array.new(word.length, nil)
    for i in (0...word.length)
        next if pattern[i] != nil
        for j in ((i + 1)...word.length)
            pattern[j] = i if word[i] == word[j]
        end
    end
    pattern.slice(1,9999)
end

# Grab all the dictionary entries
@dict = {}
File.open("dictionary.lst", "r") do |f|
    f.each_line do |word|
        word.chomp!.downcase!
        pattern = find_pattern(word)
        if @dict.include?(pattern)
            @dict[pattern] << word
        else
            @dict[pattern] = [word]
        end
    end
end

# Track progress of each word
class Word
    attr_accessor :word, :possibilities
    def initialize(word, dict, solution)
        @word = word
        # Find all words with the matching letter pattern
        @possibilities = dict[find_pattern(word)].dup
        # If there's just one possibility, store the transposed letters
        if @possibilities.length == 1
            (0...word.length).each {|i| solution[word[i].ord - 97] = @possibilities.first[i]}
        end
    end
end

# These spaces get replaced with up to 26 letters
@solution = "                          "

# Go grab all the words, and in the process whittle down possibilities and add to the solution
words = gets.chomp.split.map {|word| Word.new(word, @dict, @solution)}

# Hopefully by this point we have lots of matches, and can round out the rest of the unknowns pretty easily

loop do
    changed_one = false
    # Throw out impossible stuff
    words.each do |w|
        # Don't care about words we've already figured out
        next if w.possibilities.length == 1
        i = 0
        # Check all remaining possibilities
        while i < w.possibilities.length
            possibility = w.possibilities[i]
            break if possibility == nil
            # Character by character
            for j in (0...possibility.length)
                converted = @solution[w.word[j].ord - 97]
                next if converted == " "
                if possibility[j] != converted  # One of the letters doesn't match up?
                    # This is no longer a valid possibility.  Remove it.
                    w.possibilities.delete_at(i)
                    i -= 1
                    changed_one = true
                    break
                end
            end
            i += 1
        end
        if w.possibilities.length == 1
            # Add to the solution stuff
            (0...w.word.length).each {|k| @solution[w.word[k].ord - 97] = w.possibilities.first[k]}
        end
    end
    break if !changed_one
end

puts words.map {|w| w.possibilities.first}.join(" ")