Seattle RB bit on finding the top scoring scrabble words for a set of characters. Quick 20 minute hack with some caching.

scrabble_finder.rb

module Scrabble
  # Official scrabble scores per letter
  LETTER_SCORES = {
    'a' => 1,
    'e' => 1,
    'i' => 1,
    'o' => 1,
    'u' => 1,
    'l' => 1,
    'n' => 1,
    's' => 1,
    't' => 1,
    'r' => 1,

    'd' => 2,
    'g' => 2,

    'b' => 3,
    'c' => 3,
    'm' => 3,
    'p' => 3,

    'f' => 4,
    'h' => 4,
    'v' => 4,
    'w' => 4,
    'y' => 4,

    'k' => 5, 

    'j' => 8,
    'x' => 8,

    'q' => 10,
    'z' => 10
  }

  class << self
    # Retrieves a wordlist, defaulting to the Mac OSX wordlist
    # (a derivative of Webster's 2nd edition), so not technically
    # real scrabble, but enough for demonstration
    # 
    # @note cached
    # 
    # @param path = '/usr/share/dict/words' [String] - Path to dictionary
    #
    # @return [Array[String]] - Cleaned wordlist
    def word_list(path = '/usr/share/dict/words')
      @word_list ||= IO.readlines(path).map { |word| word.strip.downcase }.uniq
    end

    # Cache for the scores of a character combination
    #
    # @return [Hash[String, Array[Array[String, Integer]]
    def score_cache
      @score_cache ||= {}
    end

    # Cache for the words a character set generates
    #
    # @return [Hash[String, Array[String]]] - Possible generated words
    def word_cache
      @word_cache ||= {}
    end

    # Scores a word based on the Scrabble letter scores
    # 
    # @param word [String] - Word to score
    #
    # @return [Integer] - Word score
    def score_word(word)
      word.chars.map { |char| LETTER_SCORES[char] || 0 }.reduce(0, :+)
    end

    # Finds words that can be made from a character set
    # 
    # @note cached
    # 
    # @param characters [Array[String]] - Characters to search over
    #
    # @return [Array[String]] - Words comprised of provided characters
    def words_for_characters(characters)
      word_cache[characters.sort.join] ||= word_list.reject { |word|
        word.size > characters.size || (word.chars - characters).size > 0
      }
    end

    # Finds top scores for a set of characters
    # 
    # @note cached
    # 
    # @param characters [Array[String]] - Characters to search over
    #
    # @return [Array[String, Integer]] - Word Score pairs
    def top_scores_for_characters(characters)
      score_cache[characters.sort.join] ||=
        words_for_characters(characters).map { |word|
          [word, score_word(word)]
        }.sort_by(&:last)
    end

    # Finds the top n scores for a set of characters
    # 
    # @note cached
    # 
    # @param characters [Array[String]] - Characters to search over
    # @param n          [Integer]       - Number of results to fetch
    #
    # @return [Array[String, Integer]] - Top n words
    def top_n_scores_for_characters(characters, n)
      top_scores_for_characters(characters).last(n).reverse
    end
  end
end

Sometimes I do miss the simplicity of ruby syntax. Did you test it out? What words did you find?

I'll write up some RSPEC for it later @mhootman, this was just a quick hack before I went to bed last night. It'll need more than just that for later.

This would probably be even shorter in Prolog... But nicely done for a night of hacking.