blacksmith gunpowdery

5x5.rb

#!/usr/bin/ruby
# (c) 2007 stephan.com
# A program to impress Grace
# Finds five words of five letters using all unique letters

Goodwords = []
CompareMatrix = {}

# returns true if any letters are shared between two strings
def has_common_letters?(a, b)
  return (a.split(//) & b.split(//)).length>0  
end

# sentence is an array of the words so far
def construct_sentence(sentence)
#  puts sentence.join(" ") if sentence.length > 3
  if sentence.length > 4
    puts sentence.join(" ")
    return # stop recursion
  end
  
  if sentence.length==0
    # if this is the top recursion level, start with each word
    Goodwords.each do |word|
      construct_sentence([word])
    end
  else
    # Merge the allowed words from all existing words
    okwords = CompareMatrix[sentence[0]]
    sentence[1..-1].each { |word| okwords = okwords & CompareMatrix[word]  }
    
    # for each mutually allowed word, recurse another level
    okwords.each do |word|
      construct_sentence(sentence + [word])      
    end    
  end
end

# open the system dictionary and find all five letter words whose letters are unique
dictionary = File::open("/usr/share/dict/words")
while word = dictionary.gets
  # get rid of end of line and upper case
  word.strip!.downcase!
  # First, eliminate all words with more or less letters
  next unless word.length == 5
  
  # now, remove all words whose letters are not themselves unique
  bad = false
  word.strip.split(//).each_with_index do | letter, pos |
    if word.index(letter, pos+1) != nil
      bad = true
      break
    end
  end

  Goodwords << word unless bad 
end

# Goodwords now contains all possible usable words
# Turns out to be 6,345 words total
puts "Found "+Goodwords.length.to_s+" suitable words"

# My first attempt simply recursively tried out all combinations.
# This is a large number = 6345! / 6340!, or around 10 quintillion
# Instead, I precompute for each word a list of words that have no common characters
puts "Building compare table at "+Time.now.to_s
last = "-"
Goodwords.each_with_index do | firstword, pos |
  # give some feedback while building this thing
  if firstword[0]!=last
    last = firstword[0]
    putc last
    STDOUT.flush
  end

  CompareMatrix[firstword] = []
  Goodwords[pos+1..-1].each do | secondword |    
    CompareMatrix[firstword] << secondword unless has_common_letters? firstword,secondword
  end
end
puts "\nFinished compare table at "+Time.now.to_s

construct_sentence([])