Gabe: Find the word that has the most sub-words. Words that can be made out of the same letters.

subwords.rb

# Gabe: Find the word that has the most sub-words. Words that can
# be made out of the same letters.

def chars(str)
  str.split('')
end

class Node
  attr_reader :letter, :leaf, :yes, :no

  def initialize(words, letter=A)
    @letter = letter
    if letter == Z
      @leaf = words
    elsif words.empty?
      @leaf = []
    else
      has_letter = []
      i = words.size - 1
      while i >= 0
        word = words[i]
        if word.include?(letter)
          has_letter << words.delete_at(i)
        end
        i -= 1
      end
      @yes = Node.new(has_letter, letter.succ)
      @no = Node.new(words, letter.succ)
      @leaf = nil
    end
  end

  private

  A = 'a'
  Z = 'z'
end

def can_be_made?(letters, word)
  return false if letters.size < word.size
  word = word.split('')
  letters.each_char do |letter|
    if i = word.index(letter)
      word.delete_at(i)
    end
  end
  word.empty?
end

def possible_words(letters, node)
  if node.leaf
    # No criteria to decide. Consider these words.
    node.leaf
  else
    # Consider node.letter...
    if letters.include?(node.letter) # we have this letter!
      # It could be in the yes or no branch (not all letters must be used)
      possible_words(letters, node.yes) + possible_words(letters, node.no)
    else # we don't have this letter :(
      # We can't make words with a letter we don't have.
      possible_words(letters, node.no)
    end
  end
end

def sub_words(word)
  possible_words(word, $index).select{|subword| can_be_made?(word, subword) }
end

def load_all_words
  File.read('words_for_problem__updated_June__11_.txt').each_line.to_a.map(&:strip).select{|word| word.size > 0 }
end

if $0 == __FILE__
  index_path = 'word_index'
  if !File.exist?(index_path)
    File.open(index_path, 'w') do |f|
      words = load_all_words
      $stdout.print 'Building word index...'
      $stdout.flush
      $index = Node.new(words)
      $stdout.puts 'done'
      f << Marshal.dump($index)
    end
  else
    $stdout.print 'Loading word index...'
    $stdout.flush
    File.open(index_path) do |f|
      $index = Marshal.load(f)
    end
    $stdout.puts 'done'
  end

  all_words = load_all_words
  all_words.delete_if{|word| word.size < 7 }
  #all_words = all_words[0,1000]
  all_words = all_words
  procs = []
  all_words.each_slice(all_words.size / 5) do |words|
    read, write = IO.pipe
    sub_process_words = all_words.shift
    pid = fork do
      words.map!{|word|
        print word[0,1]
        [word, sub_words(word)]
      }
      result = words.sort_by{|w,subs| -subs.size }.first
      write.print result.first
      read.close
    end
    write.close
    procs << [read, pid]
  end

  results = []
  procs.each do |read, pid|
    Process.wait(pid)
    results << read.read
  end
  p results
end

__END__
words = ["australopithecines", "encephalomyocarditises", "neuropharmacologists", "phenylthiocarbamides", "ultracontemporaries"]
words.map!{|word|
  print word[0,1]
  [word, sub_words(word)]
}
result = words.sort_by{|w,subs| -subs.size }.first