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

--=-=-=

"Pit Capitain" <pit@capitain.de> writes:

> Hi Dave, your code is fast, but you are cheating (a little bit ;-)
> Here are two word lists that break the algorithm:
> 
> Longest add-a-gram not beginning at 3 or less letters:
> 
>   nitons
>   intones
>   mentions
>   nominates
>   antimonies
>   inseminator
>   terminations
>   antimodernist
>   determinations
>   underestimation
>   underestimations
>   ant
>   ante
>   antre
>   atoner
>   another
>   antihero
>   anorthite
>   anorthites
>   antistrophe
>   attorneyship

I report 'attorneyship' for this sequence (Steven's code reports
'underestimations', but shows a list starting with 'nitons', which is
five characters long. The challenge says to start at 3 characters). Am
I missing something?

> * Should it only work with the given or with any word list?
> * Should it only print the last word or the whole sequence?

The challenge asks for the longest word, not the chain. However,
adding reporting for the whole chain barely affects the run time. I've
attached the new version.

However I do think it should work with any list.

> * Is it allowed to use C extensions or has it to be pure Ruby?

Pure Ruby, I'd say.


Dave




--=-=-=
Content-Disposition: attachment; filename=addagram.rb

@known_failures = {}
@words = {}
words_of_length = []
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[w = word.unpack("c*").sort.pack("c*")] = word

  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, res)
  res << the_word
  return res if the_word.length == 3

  unless @known_failures[the_word]
    word = the_word.dup
    ch = word.slice!(0)
    len = word.length
    (len+1).times do |i|
      return res if @words[word] && test_word(word, res)
      word[i], ch = ch, word[i] if i < len
    end
    @known_failures[the_word] = true
  end
  res.pop
  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|
    res = []
    if test_word(word.unpack("c*").sort.pack("c*"), res)
      puts "Found: #{word} using #{res.map{|r| @words[r]}.join(', ')}"
      exit
    end
  end
end

--=-=-=--