Finds words that can be spelled using a given set of letters. (aka. Scrabble assistant. :D)

fastwords.rb

require 'pp'

class Word < Hash

  attr_accessor :original

  def initialize(word)
    @original = word
    h = super(0)
    word.chars.each { |c| h[c] += 1 }
    h
  end

  def include?(other)
    other.each { |c,n| return false if (self[c] - n) < 0 }
    true
  end

  def -(other)
    t = dup
    other.each { |c,n| t[c] -= n }
    t
  end

  def empty?
    values.reduce(:+) == 0
  end

  def size
    @original.size
  end

  def to_s
    original
  end

end


class Solver
  def initialize
    @letters   = Word.new "yyyyyyyyytttsssssrrrppplllhgc"
    @words     = open("/usr/share/dict/words").readlines.map{|w| Word.new w.strip.downcase }
    @grouped   = @words.group_by(&:size)
    @template  = [3,5,5,6,5,5]
    @solutions = []
  end

  def search(template, letters_left, solution_so_far=[])
    #puts "solution so far: #{solution_so_far.join(" ")}"
    words = @grouped[template.first]

    for word in words

      if letters_left.include? word
        new_template = template[1..-1]

        if new_template.empty?
          solution = solution_so_far + [word]
          puts "solution: #{solution.join(" ")}"
          @solutions << solution
        else
          search new_template, letters_left - word, solution_so_far + [word]
        end
      end

    end
  end


  def solve
    @solutions.clear
    search(@template, @letters)
    @solutions
  end

end

solutions = Solver.new.solve

puts "Solutions:"
pp solutions.map { |sentence| sentence.join(" ") }
puts

puts "Unique solutions:"
pp solutions.map {|s| s.map(&:to_s).sort }.uniq.map { |s| s.join(" ") }
puts

Unique solutions:
["crypt gypsy pry shyly slyly trysts",
"crypts gypsy pry shyly slyly tryst",
"crypt gypsy shy slyly spryly tryst",
"crypt gypsy shyly sly spryly tryst",
"gypsy psych slyly spryly try tryst"]