“Cheating” at Words With Friends

It’s time to admin something. I cheat at Words With Friends. I only justify it with the fact that I at least wrote the code to help me cheat.

And cheat really isn’t the word for it. Sometimes I just stare at my letter rack for hours and come up with nothing. I wrote the following script just to get my brain going. You have two options with this script. Argument 1 always has to be your letter rack. You can use the “+” sign for the blank tile. Argument 2 is regular expression if you are looking for something specific.

If you have the tile rack aabbccd, you would run words-help aabbccd and get a dump of every combination. If you are looking for words with ba at the beginning of the word, you would run words-help aabbccd ^ba.

This script should work on anything UNIX-like that has a dictionary file at /usr/share/dict/words. You can edit the script as you need.

#!/usr/bin/env ruby

WORDS_FILE = '/usr/share/dict/words'

class Engine

  def initialize(file)
    @file = file

    read_dictionary
  end

  def go(letters, regex = nil) 
    @letters = letters.split ''
    @regex = Regexp.new(regex) unless regex.nil?
    @words = []

    # Find the words
    letter_combinations do |letter_combination|
      letter_combination.permutation.to_a.each do |letter_array|
        word = letter_array.join('')
        if @dictionary.key?(word)
          if @regex.nil?
            @words << word
          else
            @words << word if @regex.match(word)
          end
        end
      end
    end

    # Clean up
    @words.sort.uniq
  end

  private

  def letter_combinations
    max = (2 ** @letters.count) - 1
    1.upto(max) do |i|
      word = []
      mask = sprintf("%0#{@letters.count}b", i).split('')
      mask.each_with_index do |bit, i|
        word << @letters[i] if bit == '1'
      end

      # Substitute wild cards
      idx = word.index '+'
      if idx.nil?
        yield word
      else
        ('a'..'z').each do |l|
          word[idx] = l
          yield word
        end
      end
    end
  end

  def read_dictionary
    # Build the dictionary
    @dictionary = {}

    # Read the words
    File.open(@file, 'r') do |file|
      file.each_line do |line|
        line.strip!

        # Skip proper nouns
        next if line =~ /[A-Z]/

        # Skip 1 letter words
        next if line.length == 1

        # Add the word to the dictionary
        @dictionary[line] = 1
      end
    end
  end

end

if ARGV.length < 1 || ARGV.length > 2
  $stderr.puts "Letters are required"
  exit
end

e = Engine.new WORDS_FILE
e.go(ARGV[0], ARGV[1]).each { |word| puts word }

This script is brute force, so the more letters you set as Argument 1, the longer it will take to run. You’ve been warned.

“Cheating” at Words With Friends

Visualizing Problem 15 of Project Euler

I’ve been working through Project Euler as a coding / math exercise. Problem 15 asks to find the amount of paths that exist between the top-left and bottom-right points of a 20×20 grid, without backtracking. I decided to visualize it, because just running a command line program and waiting can be boring.

Of course, this problem is silly to brute force, but by watching the visualization and working on a pad of paper, I came up with a much faster solution to solving the problem.

The code is available on github. It’s Ruby and Tk. Some Ruby installs don’t compile with Tk, so if the script doesn’t load the tk requirement, Google around for the solution.

Also note, this is a quick hack. It leaks memory, it’s buggy, it might eat your processor and will run for a very long time.

Visualizing Problem 15 of Project Euler