anagram.rb

module Anagram
  class Dictionary < Hash
    def initialize(dict_file="/usr/share/dict/american-english")
      words = File.read(dict_file).split(?\n)
      # Try to optimize #is_word? by sorting the hash in the form of {0 => {"A" => ...}, 1 => {"A" => ... "B" => ... }, ... }
      words.group_by(&:length).each do |k,v|
        self[k] = v.group_by(&:chr)
      end
    end

    def is_word?(word)
      (self[word.length][word.chr].include? word) ? true : false
    end
  end
end

$Dictionary = Anagram::Dictionary.new

def anagram(layout, c)
  puts "ping"

  # return if we have an empty map or no characters to use
  return [] if layout.empty? || c.empty?

  # Make sure that we are using an array and not a string
  c = c.chars.to_a if c.is_a? String

  # Copy the character structure, we will be modifying it later
  chars = c.dup

  # First we take get the permutations of the letters
  # of length layout[0], and only keep valid dictionary
  # words
  sets = chars.permutation(layout.first).map {|x| x.inject(:+) }
  sets.keep_if {|x| $Dictionary.is_word? x }

  # Peek at how long the following words will be
  sublayout = layout.drop 1
  
  # If there is no following words, we can
  # return the permutations
  return sets if sublayout.empty?
 
  # Recurse over each result to continue the tree
  sets.map! do |set| 
      # We're modifying the characters even more
      ch = chars.dup
      # Take out the characters we used for this permutation
      set.chars.to_a.each {|x| ch.delete_at (ch.find_index x) }
      # If we used all of the characters, return an empty array
      if ch.empty?
        []
      # Otherwise, recurse the method to get more results
      else
        subsets = anagram(sublayout, ch)
        # If there are results
        unless subsets.empty?
          subsets.map {|x| [set].concat (x.is_a? Array) ? x : [x] }
        # Otherwise return an empty array to optimize the comparing
        # process that occurs later
        else
          []
        end
      end
  end

  # Clobber [["foo","bar"]] sets, this is a bug. I don't know where
  # it originates from yet.
  sets.map! {|x| ((x.size == 1)&&(x.first.is_a? Array)) ? x.first : x } 
  # Only keep sets that match the layout size.
  sets.keep_if {|set| set.size == layout.size }   
end