From: grady@... (Steven Grady)
Date: 2002-02-09T05:45:27+09:00
Subject: Reg: tiny contest: who's faster? (add_a_gram)

> My current solution works correctly with various inputs.
> It might have bugs, but most importantly, it takes forever.

My solution takes under a minute on my machine; the majority is the
building of the word hashes.  Some of the basic techniques are:
* Store the words in the sorted form, rather than sorting them each
time
* Start with the longest words, and stop trying when our chain is
longer than the length of the words we are trying
* Store the words organized by length, so we can iterate starting with
the longest words
* Store the maximum chains for a given set of letters, so we don't
need to recompute it

The code is reasonably short as well.  I suspect it could be optimized
further:
#!/usr/local/bin/ruby

$File = "WORD.LST"
$Lengths = Hash.new
MaxWordLength = 30
(MaxWordLength+1).times {|i| $Lengths[i] = Hash.new}
$MaxChains = Hash.new

num = 0
lines = File.readlines("WORD.LST")
puts "#{lines.length} total words"
$stdout.sync = true
lines.each {|w|
  num += 1
  print "#{num}\r" if (num % 1000 == 0)
  w.chomp!
  $Lengths[w.length][w.split(//).sort.join] = w
}

def getMaxChain(letters)
  return $MaxChains[letters] if $MaxChains[letters]
  length = letters.length
  w = $Lengths[length][letters]
  maxChain = [w]
  letters.length.times {|i|
    chain = [w]
    lessOne = letters.dup
    lessOne[i] = ''
    smaller = $Lengths[length-1][lessOne]
    if smaller
      chain.concat(getMaxChain(lessOne))
      maxChain = chain.dup if chain.length > maxChain.length
    end
  }
  $MaxChains[letters] = maxChain.dup
  maxChain
end

maxChain = []
MaxWordLength.downto(1) {|length|
  puts "Trying words of length #{length}"
  words = $Lengths[length]
  next unless words
  words.each {|letters, word|
    chain = getMaxChain(letters)
    maxChain = chain if chain.length > maxChain.length
  }
  break if maxChain.length > length
}
p maxChain.reverse

--
    Steven
If God had wanted us to be concerned for the plight of the toads, he
would
have made them cute and furry.