From: Dave Thomas <Dave@...>
Date: 2002-02-09T08:19:20+09:00
Subject: Re: Reg: tiny contest: who's faster? (add_a_gram)

grady@xcf.berkeley.edu (Steven Grady) writes:

> My solution takes under a minute on my machine; the majority is the
> building of the word hashes.  Some of the basic techniques are:

I'm not sure if we're necessarily going for speed, but the following
runs about three times faster on my box. The time taken reading in
seems to swamp the other times. 1.7 runs it about 5% faster, which is
surprising: I thought the GC mods would make a bigger difference.

Regards

Dave


     @known_failures = {}
     words_of_length = []
     @words     = {}
     max_length = 0

     # Build
     # 1. a hash of all mapped words, where a mapping is
     #    all the characters in the word sorted into
     #    alphabetical order. Anagrams will map to the
     #    same value
     #
     # 2. An array or arrays, giving us a list of all
     #    the words of a given length (for lengths over 11,
     #    because we know the solution has >11 characters)

     File.open("word.lst").read.split.each do |word|
       @words[word.unpack("c*").sort.pack("c*")] = 1

       len = word.length
       if len > 11
         unless words_of_length[len]
           words_of_length[len] = []
           max_length = len if len > max_length
         end
         words_of_length[len] << word
       end
     end

     # permute the word.length combinations of word.length-1 letters
     # in the word where the permutations are sorted. For any
     # permutations that are known words, call ourselves recursively
     # until we either fail to find a word of find a word of length
     # three

     def test_word(the_word)
       unless @known_failures[the_word]
         word = the_word.dup
         ch = word.slice!(0)
         len = word.length
         (len+1).times do |i|
           return true if @words[word] && (len == 3 || test_word(word))
           word[i], ch = ch, word[i] if i < len
         end
         @known_failures[the_word] = true
       end
       false
     end

     # Now go through the words, starting at the longest.
     max_length.downto(3) do |l|
       puts "Length #{l}"
       (words_of_length[l] || []).each do |word|
         if test_word(word.unpack("c*").sort.pack("c*"))
           puts "Found: #{word}"
           exit
         end
       end
     end