The calendar is gone.
Click here to view posts

Cs forgotten

My memory was never the best. I have never worked on improving my memory because I can figure things out. If I do something enough it becomes second nature. The point is someone I work with was talking about Ternary search trees[1] and I had forgotten what they were. He started to describe what they are used for and how they basically work. I made the comment "it would be an interesting data structure in Ruby" which lead to the comment "Perl implements it with a hash of hashes." After the conversation the name of the tree left my mind and all I had was the perl comment and basic functionality. So I went to Cafe Presse[2] and start writing on a napkin while eating my Steak Frites. (I love those steak frites)

Basic functionally was defined as an interface that told me what words were in a dictionarythat was loaded, this is line for line what I wrote on the napkin

@@top_hash = {}
def create_hash(word)
    current_hash = @@top_hash
    word.strip!
    word.downcase!
    word.split(//).each{|letter|
        current_hash[letter] ||= {}
        current_hash = current_hash[letter]
   }
   current_hash["END"] = true
end
def is_word?(word)
   real_word = false
   word.downcase!
   word.strip!
   current_hash = @@top_hash
   (0...word.size).each{|i|
       current_hash = current_hash[word[i].chr]
       break unless current_hash
       real_word = true if ((i == word.size-1) && current_hash["END"])
   }
   real_word
end
word = "gennosuke"
create_hash(word)
create_hash("ninja")
create_hash("nine")
pp @@top_hash
pp is_word?(word)
pp is_word?("cow")

There was also a drawling of benders head and some flushed out hashes. It turns out this works well enough. Add in some load commands and different accessors and it should work well enough to get anyone started. The last bit of code that I added was an auto-complete part. I wrote this the next day at cafe vita over a double short americano(minus the comments)

#get me to the end of the base then look for tails to add
#there is improvements here if you can have compounded words
def find_other_words(word_base)
    word_base.downcase!
    word_base.strip!
    current_hash = @@top_hash
    (0...word_base.size).each{|i|
        current_hash = current_hash[word_base[i].chr]
        break unless current_hash
    }
    find_tails(current_hash).collect{|tail| word_base+tail}
end
private

#go all the way down the tails stack then build arrays on your way back up
#can be cleaned up
def find_tails(current_hash)
    if current_hash.kind_of?(Hash)
        current_tails = []
        current_hash.each{|key,hash|
            if key != "END"
                find_tails(hash).collect{|tail| current_tails.push(key+tail)}
            else
                current_tails.push("")
            end
            }
        current_tails
    else
        [""]http://www.ddj.com/windows/184410528
    end
end

It was fun. I liked that I didn't type a letter until after the code was written. I also like the implementation I did. The only thing I really knew going in to it was to store the data in a hash collection. After I wrote the code I googled around for ruby digital trie and found some sites[3][4] that made me feel good about how I wrote my code. Maybe this is the line of work I should be in after all.


[2] http://www.cafepresseseattle.com/pages/home.html
[3] http://www.ddj.com/windows/184410528
[4] http://www.rubyquiz.com/quiz103.html

Tags: ruby