From: pc000@... (PaulC)
Date: 2002-02-09T16:05:51+09:00
Subject: Re: tiny contest: who's faster? (add_a_gram)

Tobias Reif <tobiasreif@pinkjuice.com> wrote in message news:<3C640E0C.8090207@pinkjuice.com>...
> 
> My current solution works correctly with various inputs.
> It might have bugs, but most importantly, it takes forever.
> Short sample input is no problem; but as soon as I feed it
> the 1.5 MB word list from the website, my computer
> is overwhelmed, and starts to smell heated after 2 hours :|
> 

Interestingly I was also looking at this recently & had 
actually put together a solution in ObjC - I did a rough 
Ruby translation and this is able to process the full word 
list in about 8 1/2 minutes on my laptop (see below).

[paulc:tigger] ~/Development/Ruby % wc -l
/Users/paulc/AddAGram/WORD.LST
  173528 /Users/paulc/AddAGram/WORD.LST
[paulc:tigger] ~/Development/Ruby % time ./AddAGram.rb
~/AddAGram/WORD.LST
Building WordList....
Searching....
Done...

(eon,one) + a -> aeon
aeon + s -> aeons
aeons + t -> atones
atones + i -> atonies
atonies + m -> (amniotes,misatone)
(amniotes,misatone) + n -> nominates
nominates + i -> (antimonies,antinomies)
(antimonies,antinomies) + r -> (inseminator,nitrosamine)
(inseminator,nitrosamine) + t -> terminations
terminations + d -> antimodernist
antimodernist + e -> determinations
determinations + i -> intermediations
intermediations + n -> indeterminations

../AddAGram.rb /Users/paulc/AddAGram/WORD.LST  502.59s user 1.45s
system 98% cpu 8:32.56 total

The problem is inherently fairly complex will scale very poorly using
a naive algorithm - the approach used here is to pre-sort the wordlist
into buckets with the same length, within each bucket the words are 
stored in a dictionary with a key formed by sorting the word by 
character - to find candidate AddAGrams we take the start word, add 
'a'..'z', re-sort the result and use this key to index the next
bucket.
Essentially this trades a table scan for 26 indexed probes for each
lookup which is a very big win. In addition we mark nodes as visited
as
we touch them to prune trees which we have already reached.

Thanks to my colleague Jeff Turner for figuring out the concept !

PaulC

========= AddAGram.rb =========
#!/usr/local/bin/ruby

class String
    def sortByChar
        split(//).sort.join
    end
end

class EquivWords
    def initialize(word)
        @sortedWord = word.sortByChar
        @realWords = [word]
        @visited = false
    end
    def addWord(word)
        @realWords << word
    end
    def to_s
        if @realWords.length == 1 then
            @realWords[0]
        else
            "(" + @realWords.join(",") + ")"
        end
    end
    attr_accessor :visited, :realWords, :sortedWord
end

class WordList
    def initialize
        @wordDict = {}
    end
    def addWord(word)
        length = word.length
        sortedword = word.sortByChar
        if (wordsWithLength = @wordDict[length]) == nil then
            wordsWithLength = (@wordDict[length] = {})
        end
        if (res = wordsWithLength[sortedword]) then
            res.addWord(word)
        else
            wordsWithLength[sortedword] = EquivWords.new(word)
        end
        return self
    end
    def hasSortedWord(sortedword)
        begin
            @wordDict[sortedword.length][sortedword]
        rescue NameError
            false
        end
    end
    def hasWord(word)
        return hasSortedWord(word.sortByChar)
    end
    def objsWithLength(length)
        @wordDict[length].values
    end
    def inspect
        values = @wordDict.keys.sort.collect { |k|
"#{k}-#{@wordDict[k].length}" }.join(",")
        return "<#{self.class}:#{sprintf('0x%x',self.id)} [" + values
+ "]>"
    end
end

class Searcher
    def initialize(list)
        @list = list
        @trail = []
        @maxlength = 0
        @longest = nil
    end
    def search(wordObj)
        found = 0
        @trail << wordObj
        ("a".."z").each { |c|
            if (matchObj = @list.hasWord(wordObj.sortedWord+c)) then
                if matchObj.visited == false then
                    search(matchObj)
                end
            end
        }
        wordObj.visited = true
        length = @trail.length
        if length > 0 then
            if length > @maxlength then
                @maxlength = length
                @longest = @trail.clone
            end
            @trail.pop
        end
    end
    def printResult
        @longest.each_with_index { |val,i|
            if (nextobj = @longest[i+1]) then
                nextchrs = nextobj.sortedWord.split(//)
                curchrs = val.sortedWord.split(//)
                curchrs.each { |c|
nextchrs.delete_at(nextchrs.index(c)) }
                print "#{val.to_s} + #{nextchrs[0]} ->
#{nextobj.to_s}\n"
            end
        }
    end
    attr_reader :longest
end

list = WordList.new
print "Building WordList....\n"
ARGF.each { |l| list.addWord(l.chomp.downcase) }
print "Searching....\n"
agSearcher = Searcher.new(list)
list.objsWithLength(3).each { |o| 
    agSearcher.search(o) 
}
print "Done...\n\n"
agSearcher.printResult
print "\n"