From: Christoph <chr_news@...>
Date: 2002-02-21T02:18:58+09:00
Subject: Re: tiny contest: who's faster? (add_a_gram)

"Tobias Reif" <tobiasreif@pinkjuice.com> wrote in,
....

> Hi;
>
> Better than Superbowl, bigger than the Olympics;
> the Add-A-Gram contest :)

Hm, the Olympics are winding and I got some time on my hand.  I was
always wandering if this particularly idea was at all practical - the algorithm
does not guaranty that you found a longest match but the changes that you
are about as likely as a snowball in hell - There are plenty of variations
of this idea and a C-based implementation would probably be pretty fast.
Anyway,  the ratio of the running times of my scripts (which requires a cvs
version) and Daves addagram  is  ~ 0.7 ...

/Christoph

-----
class String

#   Original ordering - the fact that the larger number are primes probably
#   makes no difference for the smaller it certainly does
#
#    tmp =[2, 5,13,23,53,113,257,569,1249,2749,6089,13441,29683,65537,
#              144719,319567,705643,1558177,3440719,7597757,16777213,
#              37047091,81806611,180643669,398893589,880828517]
#
#    Ordered by hand  - I didn't put a lot of thought into this ...

    tmp =[180643669, 5,13,705643 ,81806611,113,257,569, 37047091,2749,
               6089,13441,29683,65537,7597757,319567, 23 ,1558177,3440719,
               144719,16777213, 1249, 53,  2, 398893589,880828517]

#   This particularly ordering results in two #ab_hash collisions  -
#    "brownish", "forgings"  and  "fogginess", "wishbones"

    PTable = Array.new(65).concat(tmp.dup.concat(Array.new(6).concat(tmp)))

    def ab_hash
        hsh = 0
        each_byte { |byte| hsh+=  PTable[byte] }
        hsh
    end
    def ab_eql?(other)
        unpack("c*").sort.pack("c*") == other.unpack("c*").sort.pack("c*")
    end
end

class LArray < Array
    class NAHash < Hash
        def sol(hsh)
            return [ fetch(hsh) { return nil } ]
        end
        def solution
            length.zero?  ?  nil : [to_a[0][1]]
        end
    end
    class AHash < NAHash
        PTable = String::PTable
        RTable = Array.new(65).concat(('A'..'Z').collect{|i| Regexp.new(i)}.\
                       concat(Array.new(6).concat(('a'..'z').\
                       collect{|i| Regexp.new(i)})))
        # the RTable stuff does not buy you all that much ...
        def sol(hsh)
            wrd = fetch(hsh) {return nil}
            wrd.each_byte do |byte|
                if (res = @prev.sol(hsh- PTable[byte]))  && \
                    # res[0].ab_eql?(wrd.sub(/#{byte.chr}/,''))
                    res[0].ab_eql?(wrd.sub(RTable[byte],''))
                    return res.unshift(wrd)
                end
            end
            delete(hsh)
            return nil
        end
        def initialize(prev)
            @prev = prev
        end
        def solution
            each do |hsh,wrd|
                wrd.each_byte do |byte|
                    if (res = @prev.sol(hsh- PTable[byte]))  && \
                       # res[0].ab_eql?(wrd.sub(/#{byte.chr}/,''))
                        res[0].ab_eql?(wrd.sub(RTable[byte],''))
                        return res.unshift(wrd)
                    end
                end
            end
            return nil
        end
    end
    def initialize(len)
        super(len)
        self[3] = NAHash.new
        for i in 4...len do self[i] = AHash.new(self[i-1]) end
    end
    def solution
        (length-1).downto(0) do |i|
            if res = self[i].solution
                return res
            end
        end
    end
end


table = LArray.new(30)
File.open("word.lst").read.split.each do |wrd|
    table[wrd.length][wrd.ab_hash] = wrd unless wrd.length < 3
end
puts table.solution

=begin
which might result in

underestimations
underestimation
determinations
antimodernist
terminations
nitrosamine
antinomies
nominates
misatone
atonies
tisane
anise
sine
sen
=end
----


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.325 / Virus Database: 182 - Release Date: 2/19/2002