The twenty-seven word score club

Like lots of people on facebook, I've been playing scrabulous on facebook. I'm not much of a wordsmith, but I have fun playing people. Justin told me that his goal in life was to span two triple-word scores, to get a 9x word score. So not to be outdone, I wondered what words would be able to give you a 27-word score if you spanned across all three triple-word scores. We would need fifteen lettered words.

Since you can only put down at most seven tiles per turn, there needs to be a word in-between the triple letter scores to help you fill it out. These "bridge words" can't already be on the triple word score already, and they must be between two and six letters long on each side, where the total length of both words has to be greater than eight.

So I wrote a program in a couple hours to find them. I did take into account whether a word was possible to make based on the scrabble tile distribution, as well as taking into account blanks. There's 286 of them thus far in the TWL scrabble dictionary. I didn't find ones that used more than one bridge word on a side. The points aren't completely accurate either.

The first number is the points you'd get, and then the two bridge words. Based simply on the probability of drawing the numbers from a full bag, "irrationalities" is the most likely word. (in reality, this never happens, since you need to draw tile in order to place those words to reach the side.)

459 : irrationalistic : ["ratio", "alist"]

You can score a whopping 459 points with it. The word that has the biggest word score is "coenzymatically"

972 : coenzymatically : ["enzym", "tical"]

Yes. "tical" is a word.

ti·cal –noun, plural
1. a former silver coin and monetary unit of Siam, equal to 100 satang: replaced in 1928 by the baht.

There are quite a number of common words, you wouldn't think, as well as quite a number odd ones. As a note, the point scores aren't exactly accurate. I didn't take into account the double letter scores that might occur if you place a letter one it. But given that the multiplier is 27 here, and I picked the longest bridge words (which usually cover the double letter score), it shouldn't affect it too much. I had held off posting it until I fixed that, but this was sort of a one off amusement and curiosity, rather than anything significant, so I figured I'd just post it. Enjoy!

567 : accountableness : ["count", "lenes"]
648 : accountantships : ["count", "ship"]
486 : administrations : ["minis", "ration"]
648 : ammonifications : ["mon", "cation"]
594 : amorphousnesses : ["morpho", "ness"]
621 : anthropological : ["thro", "logic"]
783 : anthropomorphic : ["thro", "morph"]
594 : antihistaminics : ["his", "aminic"]
540 : antitheoretical : ["tithe", "etic"]
594 : aromatherapists : ["math", "rapist"]
540 : astronautically : ["trona", "tical"]
756 : astrophysically : ["strop", "call"]
675 : astrophysicists : ["strop", "cist"]
540 : atheroscleroses : ["heros", "erose"]
540 : atherosclerosis : ["heros", "eros"]
594 : atherosclerotic : ["heros", "roti"]
540 : authentications : ["then", "cation"]
594 : autoradiographs : ["tora", "graph"]
675 : autoradiography : ["tora", "graph"]
810 : bathymetrically : ["thyme", "call"]
594 : beautifications : ["eau", "cation"]
594 : benightednesses : ["night", "ness"]
675 : blameworthiness : ["lame", "thine"]
540 : brotherlinesses : ["other", "ness"]
486 : businesspersons : ["sines", "person"]
405 : ceaselessnesses : ["easel", "ness"]
729 : chancellorships : ["hance", "ship"]
729 : chemotherapists : ["moth", "rapist"]
810 : cholangiography : ["lang", "graph"]
675 : cholecystitises : ["hole", "titis"]
675 : cholestyramines : ["holes", "amine"]
540 : cholinesterases : ["line", "erase"]
675 : cinematographer : ["nema", "graph"]
729 : cinematographic : ["nema", "graph"]
486 : clandestineness : ["land", "nenes"]
594 : classifications : ["lassi", "cation"]
972 : coenzymatically : ["enzym", "tical"]
648 : comfortableness : ["fort", "lenes"]
567 : commensurations : ["men", "ration"]
594 : commercialistic : ["merc", "alist"]
702 : communistically : ["muni", "tical"]
756 : computerphobias : ["put", "phobia"]
648 : conceivableness : ["once", "lenes"]
567 : concelebrations : ["once", "ration"]
540 : conceptualistic : ["once", "alist"]
540 : conglomerations : ["glom", "ration"]
486 : conglutinations : ["glut", "nation"]
540 : congresspersons : ["res", "person"]
486 : considerateness : ["onside", "ate"]
540 : containerboards : ["tain", "board"]
594 : convertibleness : ["vert", "lenes"]
702 : crashworthiness : ["rash", "thine"]
594 : crotchetinesses : ["rotche", "ness"]
513 : customarinesses : ["stoma", "ness"]
459 : dangerousnesses : ["anger", "ness"]
837 : decarboxylating : ["carbo", "lati"]
810 : decarboxylation : ["carbo", "lati"]
540 : deconcentration : ["once", "ratio"]
540 : deconsecrations : ["cons", "ration"]
621 : dedifferentiate : ["diff", "entia"]
513 : defenestrations : ["fen", "ration"]
513 : delegitimations : ["elegit", "mat"]
567 : delightednesses : ["light", "ness"]
864 : demisemiquavers : ["mise", "quaver"]
810 : denazifications : ["nazi", "cation"]
567 : dialectological : ["alec", "logic"]
486 : diastereoisomer : ["aster", "some"]
648 : dichloroethanes : ["ich", "ethane"]
540 : discontinuances : ["con", "nuance"]
540 : discriminations : ["scrim", "nation"]
486 : disinclinations : ["sin", "nation"]
459 : disintegrations : ["sin", "ration"]
648 : dissatisfactory : ["sati", "factor"]
567 : divertissements : ["vert", "semen"]
675 : dyslogistically : ["slog", "tical"]
567 : eclaircissement : ["lair", "semen"]
486 : educationalists : ["ducat", "alist"]
459 : elaboratenesses : ["labor", "ness"]
459 : emotionlessness : ["motion", "ess"]
756 : encephalographs : ["epha", "graph"]
837 : encephalography : ["epha", "graph"]
675 : enfranchisement : ["franc", "semen"]
621 : epidemiological : ["idem", "logic"]
594 : epistemological : ["piste", "logic"]
540 : epistemologists : ["piste", "gist"]
378 : essentialnesses : ["senti", "ness"]
540 : esterifications : ["rif", "cation"]
594 : eutrophications : ["trop", "cation"]
702 : excrementitious : ["creme", "titi"]
621 : exsanguinations : ["sang", "nation"]
702 : extemporisation : ["tempo", "sati"]
540 : fantastications : ["antas", "cation"]
567 : flibbertigibbet : ["libber", "gib"]
513 : foreordinations : ["ore", "nation"]
567 : fragmentariness : ["ragmen", "rin"]
675 : frightfulnesses : ["right", "ness"]
567 : fundamentalists : ["dame", "alist"]
567 : gentrifications : ["rif", "cation"]
513 : gluconeogeneses : ["cone", "genes"]
513 : gluconeogenesis : ["cone", "genes"]
675 : grotesquenesses : ["rotes", "ness"]
648 : historiographer : ["tori", "graph"]
702 : historiographic : ["tori", "graph"]
432 : houselessnesses : ["ousel", "ness"]
702 : humidifications : ["midi", "cation"]
783 : hypervigilances : ["perv", "lance"]
756 : hypnotherapists : ["not", "rapist"]
567 : identifications : ["dent", "cation"]
459 : illiberalnesses : ["liber", "ness"]
513 : illimitableness : ["limit", "lenes"]
486 : illogicalnesses : ["logic", "ness"]
513 : immaterialities : ["mater", "alit"]
540 : immediatenesses : ["media", "ness"]
459 : inalterableness : ["alter", "lenes"]
459 : inanimatenesses : ["anima", "ness"]
702 : inconsequential : ["cons", "entia"]
567 : inconsiderately : ["cons", "ratel"]
486 : inconsideration : ["cons", "ratio"]
486 : incoordinations : ["coo", "nation"]
567 : incrementalisms : ["creme", "tali"]
513 : incrementalists : ["creme", "alist"]
459 : incuriousnesses : ["curio", "ness"]
567 : indefinableness : ["defi", "lenes"]
486 : indoctrinations : ["doc", "nation"]
540 : indomitableness : ["omit", "lenes"]
648 : inflammableness : ["flam", "lenes"]
513 : instrumentalism : ["strum", "tali"]
459 : instrumentalist : ["strum", "tali"]
540 : instrumentality : ["strum", "tali"]
459 : intolerableness : ["tole", "lenes"]
486 : inviolatenesses : ["viola", "ness"]
459 : irrationalistic : ["ratio", "alist"]
405 : irrationalities : ["ratio", "alit"]
567 : irreconcilables : ["recon", "able"]
729 : kinesthetically : ["nest", "tical"]
648 : lickerishnesses : ["icker", "ness"]
540 : loathsomenesses : ["oaths", "ness"]
621 : magistratically : ["agist", "tical"]
594 : martensitically : ["tens", "tical"]
540 : masterfulnesses : ["aster", "ness"]
621 : mercaptopurines : ["cap", "purine"]
621 : metallographers : ["tall", "raphe"]
702 : methamphetamine : ["eth", "etamin"]
891 : methoxyfluranes : ["ethoxy", "ran"]
729 : methylmercuries : ["ethyl", "curie"]
891 : methylxanthines : ["ethyl", "thine"]
648 : microanalytical : ["roan", "lytic"]
621 : misapplications : ["sap", "cation"]
513 : momentarinesses : ["omenta", "ness"]
486 : monounsaturated : ["nouns", "urate"]
459 : monounsaturates : ["nouns", "urate"]
513 : monumentalities : ["numen", "alit"]
567 : multiplications : ["tip", "cation"]
540 : neurobiological : ["euro", "logic"]
513 : neuroblastomata : ["euro", "stoma"]
783 : neuropsychology : ["euro", "cholo"]
513 : nonbarbiturates : ["barb", "urate"]
486 : nonbelligerents : ["bell", "gerent"]
513 : noncelebrations : ["once", "ration"]
513 : noncooperations : ["coop", "ration"]
594 : nonenforcements : ["one", "cement"]
567 : nonimplications : ["nim", "cation"]
756 : nonphotographic : ["phot", "graph"]
486 : opinionatedness : ["pinion", "ted"]
729 : overextractions : ["ere", "action"]
621 : overmedications : ["med", "cation"]
486 : oversaturations : ["ers", "ration"]
567 : overstimulating : ["verst", "lati"]
540 : overstimulation : ["verst", "lati"]
864 : oxytetracycline : ["tet", "cyclin"]
459 : painterlinesses : ["inter", "ness"]
621 : paragenetically : ["rage", "tical"]
675 : parenthetically : ["rent", "tical"]
648 : parthenocarpies : ["then", "carpi"]
567 : parthenogeneses : ["then", "genes"]
567 : parthenogenesis : ["then", "genes"]
621 : parthenogenetic : ["then", "genet"]
513 : pectinesterases : ["tine", "erase"]
567 : permissibleness : ["miss", "lenes"]
702 : pharmaceuticals : ["harm", "tical"]
729 : pharmacological : ["harm", "logic"]
648 : phenomenalistic : ["nome", "alist"]
675 : photoengravings : ["hot", "raving"]
675 : photoperiodisms : ["tope", "iodism"]
783 : phototelegraphy : ["tote", "graph"]
729 : pithecanthropus : ["theca", "thro"]
648 : planimetrically : ["anime", "call"]
621 : platinocyanides : ["latino", "nide"]
513 : pleasurableness : ["leas", "lenes"]
486 : predestinarians : ["redes", "aria"]
486 : predestinations : ["redes", "nation"]
621 : preestablishing : ["reest", "shin"]
648 : prefabrications : ["ref", "cation"]
594 : preformationist : ["reform", "ion"]
540 : preponderations : ["repo", "ration"]
621 : prepublications : ["rep", "cation"]
513 : presentableness : ["resent", "lenes"]
513 : preterminations : ["rete", "nation"]
594 : prettifications : ["ret", "cation"]
702 : problematically : ["roble", "tical"]
486 : proletarianised : ["role", "anise"]
459 : proletarianises : ["role", "anise"]
675 : proteolytically : ["rote", "tical"]
783 : quantifications : ["anti", "cation"]
729 : rechoreographed : ["chore", "graph"]
621 : recodifications : ["cod", "cation"]
513 : reconcentration : ["once", "ratio"]
513 : reconsecrations : ["cons", "ration"]
486 : reconsideration : ["cons", "ratio"]
459 : redintegrations : ["dint", "ration"]
567 : reductivenesses : ["educt", "ness"]
567 : refrangibleness : ["rang", "lenes"]
513 : regretfulnesses : ["egret", "ness"]
513 : reinvigorations : ["vig", "ration"]
432 : reregistrations : ["egis", "ration"]
567 : respectableness : ["spec", "lenes"]
513 : responsibleness : ["pons", "lenes"]
459 : retroperitoneal : ["trope", "tone"]
540 : retroreflectors : ["ore", "lector"]
594 : rigidifications : ["gid", "cation"]
513 : sacramentalists : ["cram", "alist"]
594 : saponifications : ["apo", "cation"]
810 : saprophytically : ["prop", "tical"]
513 : scintillometers : ["inti", "meter"]
567 : seductivenesses : ["educt", "ness"]
540 : selectivenesses : ["elect", "ness"]
459 : semiterrestrial : ["miter", "stria"]
513 : semitransparent : ["emit", "spare"]
405 : sensationalists : ["sati", "alist"]
459 : sentimentalists : ["time", "alist"]
594 : serviceableness : ["vice", "lenes"]
648 : simplifications : ["imp", "cation"]
594 : slaughterhouses : ["laugh", "house"]
459 : snippersnappers : ["nipper", "napper"]
567 : solidifications : ["lid", "cation"]
594 : solipsistically : ["lips", "tical"]
594 : sophistications : ["phis", "cation"]
540 : spermatogeneses : ["perm", "genes"]
540 : spermatogenesis : ["perm", "genes"]
648 : spinthariscopes : ["pint", "scope"]
567 : sprightlinesses : ["right", "ness"]
540 : stadtholderates : ["tad", "derate"]
864 : straightjackets : ["rai", "jacket"]
540 : stratifications : ["rat", "cation"]
540 : stratovolcanoes : ["rato", "canoe"]
567 : strikebreakings : ["trike", "akin"]
648 : superphenomenon : ["perp", "nomen"]
810 : sympathetically : ["path", "tical"]
351 : tastelessnesses : ["stele", "ness"]
621 : teletypewriters : ["let", "writer"]
567 : thanklessnesses : ["ankle", "ness"]
675 : therapeutically : ["rape", "tical"]
675 : thunderstricken : ["under", "trick"]
432 : toastmistresses : ["oast", "tress"]
432 : traditionalists : ["adit", "alist"]
459 : transaminations : ["ansa", "nation"]
486 : transmigrations : ["ran", "ration"]
621 : trihalomethanes : ["halo", "ethane"]
540 : troubleshooters : ["rouble", "hooter"]
567 : troubleshooting : ["rouble", "hoot"]
513 : troublesomeness : ["rouble", "omen"]
567 : trustworthiness : ["rust", "thine"]
540 : unadulteratedly : ["adult", "rated"]
459 : unalterableness : ["alter", "lenes"]
621 : unanticipatedly : ["antic", "pated"]
513 : unboundednesses : ["bound", "ness"]
729 : unchoreographed : ["chore", "graph"]
459 : uncleanlinesses : ["clean", "ness"]
621 : unclimbableness : ["climb", "lenes"]
702 : uncomplimentary : ["comp", "menta"]
513 : underestimating : ["dere", "matin"]
486 : unearthlinesses : ["earth", "ness"]
702 : unextraordinary : ["extra", "dinar"]
621 : unfavorableness : ["favor", "lenes"]
486 : unguardednesses : ["guard", "ness"]
540 : unrealistically : ["real", "tical"]
513 : unsightlinesses : ["sight", "ness"]
513 : unworldlinesses : ["world", "ness"]
837 : wappenschawings : ["pens", "hawing"]
540 : warrantableness : ["arrant", "lenes"]
486 : westernisations : ["ester", "sati"]
810 : whatchamacallit : ["hatch", "call"]
621 : whippersnappers : ["hipper", "napper"]
621 : wholesomenesses : ["holes", "ness"]
540 : worrisomenesses : ["orris", "ness"]
864 : xeroradiography : ["orad", "graph"]

Nine letter word riddle

It's not too common that I get forwards nowadays. With the advent of social news, all the stupid links have migrated there. But on occasion, I'll get one from the older crowd. This one was a riddle with a movie of the answer attached.

What common English word is 9 letters long, and each time you remove a letter from it, it still remains an English word... from 9 letters all the way down to a single remaining letter?

It was only one answer, however, which it gave as "startling". I ended up wondering if there were more than one, so I wanted to see how fast I could write something to give me the answer. It'd be good practice, since most web programming is design and architectural hard, rather than algorithms hard. Besides, it's been a while since I wrote a recursive function.

Embarrasingly, it took 2.5-3 hours. I thought I'd be able to knock it out in one. I had some problems first removing a single letter from a word. Ever since I came to Ruby, I hardly ever deal with indicies, so finding those methods took a bit of time. Then, the recursion is always a bit of a mind bender when you don't do it often.

I also spent some time looking up what were considered one letter words, but then found out that there's a whole dictionary of one letter words. So I only considered "i" and "a" as valid one letter words. I also threw out all contractions.

See if you can write shorter/faster/better code. It's certainly a better workout than fizzbuzz. Seeing how it took me a bit, and I didn't clean up the code, I set the bar pretty low to beat. There were other things that would optimize it. I didn't throw out shorter words to check in the dictionary if I already checked them in a longer word--ie. I just ran down the list of dictionary words. Try it out yourself, in whatever language. (This sounds like a good beginning problem to write in Arc.) Go ahead. I'll wait.


Got it?


Here's the list I came up with along with their chains. You'll notice that it's actually a tree that branches.

cleansers
[["cleanses", ["cleanse", ["cleans", ["clean", ["clan", ["can", ["an", ["a"]]]], ["lean", ["lea", ["la", ["a"]]]]], ["clans", ["clan", ["can", ["an", ["a"]]]], ["cans", ["can", ["an", ["a"]]]]], ["leans", ["lean", ["lea", ["la", ["a"]]]], ["leas", ["lea", ["la", ["a"]]]]]]]], ["cleanser", ["cleanse", ["cleans", ["clean", ["clan", ["can", ["an", ["a"]]]], ["lean", ["lea", ["la", ["a"]]]]], ["clans", ["clan", ["can", ["an", ["a"]]]], ["cans", ["can", ["an", ["a"]]]]], ["leans", ["lean", ["lea", ["la", ["a"]]]], ["leas", ["lea", ["la", ["a"]]]]]]]]]

discusses
[["discuses", ["discuss", ["discus", ["discs", ["disc", ["dis", ["is", ["i"]]]], ["diss", ["dis", ["is", ["i"]]]]]]]]]

drownings
[["drowning", ["downing", ["owning", ["owing", ["wing", ["win", ["in", ["i"]]]]]]]]]

paintings
[["painting", ["paining", ["pining", ["piing", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

piercings
[["piercing", ["piecing", ["pieing", ["piing", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

prickling
[["pickling", ["picking", ["piking", ["piing", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]], ["pricking", ["picking", ["piking", ["piing", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

restarted
[["restated", ["restate", ["estate", ["state", ["sate", ["sat", ["at", ["a"]]], ["ate", ["at", ["a"]]]]]]]]]

scrapping
[["crapping", ["rapping", ["raping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

sparkling
[["sparking", ["sparing", ["spring", ["sprig", ["prig", ["pig", ["pi", ["i"]]]]]]]]]

splatters
[["platters", ["platter", ["latter", ["later", ["late", ["ate", ["at", ["a"]]]]]]]], ["splatter", ["platter", ["latter", ["later", ["late", ["ate", ["at", ["a"]]]]]]]]]

splitting
[["slitting", ["sitting", ["siting", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]]], ["spitting", ["spiting", ["siting", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]], ["sitting", ["siting", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]]]]

stampeded
[["stampede", ["stamped", ["tamped", ["tamed", ["tame", ["tam", ["am", ["a"]]]]]]]]]

stampedes
[["stampede", ["stamped", ["tamped", ["tamed", ["tame", ["tam", ["am", ["a"]]]]]]]]]

startling
[["starling", ["staring", ["string", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]]], ["starting", ["staring", ["string", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]], ["stating", ["sating", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]]]]

starvings
[["starving", ["staring", ["string", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]]]]

strapping
[["trapping", ["tapping", ["taping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]], ["rapping", ["raping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

stringers
[["stingers", ["stinger", ["singer", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]]]], ["singers", ["singer", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]]], ["singes", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]], ["sings", ["sing", ["sin", ["in", ["i"]]]], ["sins", ["sin", ["in", ["i"]]], ["sis", ["is", ["i"]]], ["ins", ["in", ["i"]], ["is", ["i"]]]]]]]], ["stringer", ["stinger", ["singer", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]]]]]]

stringier
[["stingier", ["stinger", ["singer", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]]]]], ["stringer", ["stinger", ["singer", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]]]]]]

trampling
[["tramping", ["tamping", ["taping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]], ["amping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

trappings
[["trapping", ["tapping", ["taping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]], ["rapping", ["raping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

whittlers
[["whittler", ["whitter", ["whiter", ["white", ["whit", ["wit", ["it", ["i"]]], ["hit", ["hi", ["i"]], ["it", ["i"]]]], ["wite", ["wit", ["it", ["i"]]]]]]]]]

wrappings
[["wrapping", ["rapping", ["raping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]


And here's my code:

#!/usr/bin/ruby

class Array
  def one_less
    total = [self[1..-1]]
    self.each_with_index do |e, i|
      total << self.values_at(0..i, (i+2)..-1)
    end
    return total[0..-2]
  end
end

def sub_words(word)
  result = word.split("").one_less.map { |word_array| word_array.join }.uniq
  result == [""] ? [] : result
end

def find_sub_word_chain(word)
  return nil unless @@dict.include?(word)
  return [word] if word.length == 1 && @@dict.include?(word)
  valid_sub_words = sub_words(word).reject { |w| !@@dict.include?(w) }
  word_chain = valid_sub_words.map do |sub_word|
    chain = find_sub_word_chain(sub_word)
    if chain.nil?
      nil
    else
      if sub_word.length == 1
        chain
      else
        (chain << sub_word).reverse
      end
    end
  end.compact
  word_chain.empty? ? nil : word_chain
end

@@dict = {}
ARGV[0] ||= "/etc/dictionaries-common/words"
words = File.readlines(ARGV[0]).map { |w| w.chomp }
words.each do |word|
  if word.length == 1
    next unless ["a", "i"].include?(word)
  end
  @@dict[word] = word
end

words.reject { |e| e.length != 9 }.reject { |word| word =~ /'/ }.map do |word|
  chain = find_sub_word_chain(word)
  next if chain.nil?
  puts word
  puts chain.inspect
  puts
end

Testing MIME response types

I feel like I might have covered this before, but I was looking for a way to test respond_to. I had found this post on how to test it, but after looking at it for a while, I found myself rewriting it. Mainly, I took out parts that convert the Mime types, and inserted Rail's own Mime type objects. You can use it like this:

request_mime(:fbml) do 
  get :list
  assert_response_mime(:fbml)
end

request_mime("text/xml") do 
  get :list
  assert_response_mime("text/xml")
end

Just include it in your test_helper.rb file in test/

class Test::Unit::TestCase
  include Threecglabs::MimeTestHelpers
end

Here's "mime_test_helpers.rb". Just throw it in lib/

module Threecglabs
  module MimeTestHelpers

    def self.included(mod)
      mod.class_eval do
        include MimeRequest
        include MimeAssertions
      end
    end

    module MimeRequest
      # changes the mime type of the request within the block
      #
      #   request_mime(:fbml) do 
      #     get :list
      #     assert_response_mime(:fbml)
      #   end
      def request_mime(mime_type_name_or_extension)
        if mime_type_name_or_extension.kind_of?(String)
          mime_type = Mime::Type.lookup(mime_type_name_or_extension)
        elsif mime_type_name_or_extension.kind_of?(Symbol)
          mime_type = Mime::Type.lookup_by_extension(mime_type_name_or_extension.to_s)
        else
          raise ArgumentError.new("mime type must be string or symbol")
        end
        old_mime_type = @request.accepts
        @request.accept = mime_type.to_s
        yield
        @request.accept = old_mime_type
      end      
    end

    # These are assertions to test respond_to, whether they return a specific mime type
    # as a response to a request
    module MimeAssertions

      # Helps out with response testing, by letting to assert that the most recently-made 
      # request responded with a particular MIME extension, like :html, :fbml, :xml, etc.
      def assert_response_mime(expected_mime_type_ext)
        expected_mime_type = Mime::Type.lookup_by_extension(expected_mime_type_ext.to_s)

        # Mime::Type.parse doesn't parse accept parameters correctly, therefore
        # we account for having multiple types in the accept
        response_mime_types = @response.headers['type'].split(/,\s*/).map do |accept_type|
          mime_type_name = accept_type.split(/;\s*/).first
          Mime::Type.parse(mime_type_name)
        end
        assert_block("Responded with #{response_mime_types.map(&:to_s).inspect} when expecting #{expected_mime_type}") {
          response_mime_types.any? { |response_mime_type| expected_mime_type == response_mime_type }
        }
      end

    end
  end
end

Snippet!

MIME responder filter for Rails

I didn't think I had to do this, but I ended up writing a filter that acts like a switch statement for different MIME types. Let me explain. Normally, in Rails, you can respond to different requests for different content with something like this:

class PostController < ActionController::Base
  def list
    @posts = Post.find(:all)
    respond_to do |format|
      format.html
      format.fbml
      format.xml { render :xml => @people.to_xml }
    end
  end
end

When you have something like this, the browser (or whatever client) can ask for different MIME types. Here, we can return html to a browser, xml to maybe a data importer, and fbml to facebook.

I spent last week integrating Mobtropolis with facebook. Mobtropolis doesn't require a facebook account to use it, so like other websites, it has its own authentication mechanism, something like:

class PostController < ActionController::Base
  before_filter :website_authenticate_filter, :except => [:index, :list]
end

When I started using facebooker library, it already came with an authentication before_filter. That means we have two authentication filters, one native, and one for facebook. Mobtropolis users don't have to be in facebook to use it, and facebookers don't have to sign up again in mobtropolis to use it.

However, since before_filters are executed in succession, it leads to a case where the facebook authentication would be called if html was requested, and vice versa. The alternative was to take apart both authentication filters, and create a monolithic filter to handle the two different cases. Instead, I did this:

class PostController < ActionController::Base
   before_respond_to_filter :except => [ :index, :list ] do |format|
    format.html :website_authentication_filter
    format.fbml :facebook_authentication_filter
  end
end

That way, I didn't have to mix together the guts of each authentication filter, and it solved the problem of the wrong authentication filter being run. You can also use it like:

class PostController < ActionController::Base
  before_responds_to_filter :only => :home do |format|
    format.html do |controller|
      return if controller.logged_in?
      controller.send(:redirect_to, :controller => :home)
    end
    format.fbml :ensure_application_is_installed_by_facebook_user
  end   
end

By the way, I tried to alter the filter_chain as a request came in. Filter chains are copied and passed around the filters, so you can't write a filter that alters the filter chain. So don't waste your time crawling around in the guts of Rails to do this like I did. It's just as well, as that'd be a nightmare to maintain.

It does have some weaknesses though. You can only assign the filters to the same set of :except and :only options in the filters.

It ended up the code for this sort of magic was fairly easy. I'm not sure if there's an easier way to do what I wanted, but I'll see if Rails core people would find it useful (or not). In the meanwhile, for those of you Rubyists that have written plugins before that want to play with it. As with the usual mumbo jumbo, it's provided as is, I'm not maintaining it, and do whatever you want with it:

module Threecglabs
  module Filters

    # MimeResponderFilter 
    module MimeResponderFilter

      def self.included(mod)
        mod.extend(ClassMethods)
      end
  
      # Filters can respond to different mime types, so that you can use 
      # different filters depending on which mime type is being requested
      #
      #   before_responds_to_filter :except => [:login, :signup, :forgot, :invite_request, :profile] do |format|
      #     format.html :authentication_filter
      #     format.fbml :ensure_application_is_installed_by_facebook_user
      #   end
      #
      # This way, one can take the appropriate actions in setting up authentication 
      # from different mime types, and still separate the implemenation of the different
      # kinds of implementations
      #
      # The formats also take blocks, like regular filters
      #
      #   before_responds_to_filter :only => :home do |format|
      #     format.html do |controller|
      #       return if controller.logged_in?
      #       controller.send(:redirect_to, :controller => :home)
      #     end
      #     format.fbml :ensure_application_is_installed_by_facebook_user
      #   end
      #
      # NOTE: an :all format defaults to :html, therefore, a format.html is required
      module ClassMethods        
        def before_respond_to_filter(options = {}, &block)
          before_filter MimeResponderFilter.new(&block), options
        end
        
        private
        # This is a call that implements a MIME responder filter
        class MimeResponderFilter#:nodoc:
          attr_reader :filters
          
          def initialize(&block)
            @filters = {}
            block.call(self)
          end
          
          def filter(controller)
            filter = @filters[controller.request.format.to_sym] || @filters[:html]            
            if filter.kind_of?(Proc)
              filter.call(controller)
            else
              controller.send!(filter)
            end
          end
          
          # implements the "format.#{mime_type}" part of the filter
          def method_missing(mime_type, method_name = nil, &block)
            if block_given?
              @filters[mime_type.to_sym] = block
            else
              @filters[mime_type.to_sym] = method_name.to_sym
            end
          end
        end
      end

    end
  end
end

Snippet!

DRYing up your views with a TableBuilder

In the last two months, when I was adding more features to mobtropolis, I found it painful to try and lay things out all over again from scratch. As a result, it sucked to see ugly layouts on the new pages juxtaposed with all the styling I had done before. It wasn't until a week ago that I said to myself, "Stop the madness!" and started refactoring my views--something I never thought of doing much of until now. When you don't, the barrage of angle brackets blows out of proportion and it starts to look pretty damn fugly with complex views.

What I should be able to do is take common mini-layouts in my views and make them available as helpers so that I can think in terms of bigger chunks to piece together pages, rather than in divs and spans. In addition, it makes your interface more consistent for your users.

Some good resources were presentations from the 2007 RailsConf, like V is for Vexing and Keeping your views DRY. While a lot of view DRYing talks about form builders, I didn't see any on table builders, so I decided to take a stab at it. Personally, I don't like to overuse tables for layouts. But as certain elements in my page layouts have been repeated, I refactored them into first helpers, and then when I did more than one, I extracted it out into a simple table builder. This is how you'd use it:

For example, I have a mini-layout where I show simple stats:


Here's how I used a simple table builder to display the above:

<% score_card do |sc| -%>
  <% sc.placard("Votes", "", num_voters, "") -%>
  <% sc.placard("Sceneshots", "", num_sceneshots, "")-%>
  <% sc.placard("Participants", "", num_participants, "") -%>
  <% sc.placard("Challenges","", num_challenges, "") -%>
<%  end -%>

And I find that I started using the same sort of thing in other places, like in a user's profile:

<% score_card do |sc| -%>
  <% sc.placard("Submitted Scenes", "", num_scenes, "") -%>
  <% sc.placard("Submitted Sceneshots", "", num_sceneshots, "") -%>
<% end -%>

I cut out some details so you can see that it's just a block that gets passed a ScoreCard object, from which you call placard to add another score to the score_card. It sure beats writing <table> and <td> over and over again.

To declare the helper, we create a helper with the structure of the table inside the declaration of a ScoreCard object. We have a ScoreCard object to hold the contents of the placards. When they're called in the block above in the template, they get stored in the ScoreCard object, and not written out to erb immediately. That way, we can place them wherever in the table we please, by making the call to card.display(:placards):

module ScorecardHelper
 def score_card(html_options = {}, &block)
    options = { :class => :scorecard, :width => "100%" }.merge(html_options)
    ScoreCard.new(block) do |xm, card|
      xm.table(options) do
        xm.tr(:valign => :top) do
          xm << card.display(:placards)
        end
      end
    end
  end
end

So then what's ScoreCard look like? Pretty simple. It has a call to each cell that can be filled in the mini-layout. It's kinda analogous to how form_for passes in a form object, on which you can call text_field, etc.

require 'lib/table_builder'

# Used to create a scorecard helper
class ScoreCard < TableBuilder
  cells :placards

  # a placard is placed into scorecards
  def placard(text, text_id, score, widget)
    xm = Builder::XmlMarkup.new
    @placards[:html] += xm.td do
      xm.span(:style => "font-size: 1.2em") { xm << "#{text}" }
      xm.em(:id => text_id, :class => "primary_number") { xm << "#{score}" }
      xm << "#{widget}"
    end
  end

end

Notice that there's a call to cells() to initialize the type of cell, and a method of the same name that builds the html for that cell. If you have other types of cells, you simply put it in the list of cells, and then create a method for it that is called in the template. By convention, you'd stick the html of the cell contents in "@#{name_of_cell}"[:html], and if you wanted, pass in the html_options, and stick it in "@#{name_of_cell}"[:options]. Then, you can access those in the helper wherever you want.

Let's try another one. I have a mini_layout with a picture, and some caption underneath it, like a polaroid.

<% polaroid_card do |p_card| -%>
  <% p_card.picture do -%>
    <%= sceneshot_for scene -%>
  <% end -%>
  <% p_card.caption do -%>
    <%= pluralize(scene.num_of_sceneshots, "sceneshot") %>
  <% end -%>
<% end -%>

The associated helper and PolaroidCard object are pretty simple:

module PolaroidCardHelper
  # a polaroid card is used to show a picture with a caption below it.
  def polaroid_card(html_options = {}, &block)
    options = { :class => :polaroidcard, :style => "display: inline;" }
    PolaroidCard.new(block) do |xm, card|
      xm.table(options) do 
        xm.tr { xm.td(card.html_options(:picture)) {
            xm << card.display(:picture)
          }}
        xm.tr { xm.td(card.html_options(:caption).merge(:class => "caption")) {
            xm << card.display(:caption)
          }}
      end
    end
  end
end

require 'lib/table_builder'

class PolaroidCard < TableBuilder
  cells :picture, :caption

  def picture(html_options = {}, &block)
    @picture[:html] = capture(&block)
    @picture[:options] = html_options
  end

  def caption(html_options = {}, &block)
    @caption[:html] = capture(&block)
    @caption[:options] = html_options
  end
end

I've tried to pull all the plumbing out into TableBuilder (dropped it into lib/), and only leave the flexibility of creating the table structure in the helper, and the format of the cell in the object. It ends up TableBuilder isn't too complex either. It uses some metaprogramming to create some instance variables. I know it pollutes the object instance variable namespace, but I wanted to be able to say @caption[:html], rather than @cells[:caption][:html].

class TableBuilder < ActionView::Base
  class << self
    # used in the child class declaration to name and initialize cells
    def cells(*names)
      define_method(:initialize_cells) do 
        @cell_names = names.map { |n| "@#{n}".to_sym }
        @cell_names.each do |name| 
          if instance_variable_defined?(name)
            raise Exception.new("name clash with ActionView::Base instance variables") 
          end
          instance_variable_set(name, { :html => "", :options => {} })
        end
      end
    end
  end

  def initialize(decor_block, &table_block)
    super
    initialize_cells
    decor_block.call(self)
    html = table_block.call(Builder::XmlMarkup.new, self)
    concat(html, decor_block.binding)    
  end

  def display(cell_name)
    instance_variable_get("@#{cell_name}")[:html]
  end

  def html_options(cell_name)
    instance_variable_get("@#{cell_name}")[:options]
  end

end

I've found have these helpers cleans up my views significantly, though I have to admit, it's not exactly easiest to use yet. In addition, I'm not exactly thrilled about having TableBuilder inherit from ActionView::Base, but it was the only way I could figure out to get the call to concat() to work. In any case, the point is to show you that refactoring your views into helpers is a good idea, and even something like a table builder goes a long way, even if you don't do it the way I did it. Lemme know if this helps or hinders you. snippet!

A simple distributed crawler in Ruby

A week ago, I took a break from Mobtropolis, and...of all things ended up writing a simple distributed crawler in Ruby. I hesitated posting it at first, since crawlers are conceptually pretty simple. But eh, what the heck.

This was just an exercise to do some DRb and Hpricot, so don't use this for your production work, whatever it may be. An actual crawler is far more robust than what I wrote. And don't keep it running hammering at stuff, since it'll get you banned.

First, this is how you use it:

WebCrawler.start("http://en.wikipedia.org/") do |doc|
  puts "#{doc.search("title").inner_html}"
end

And that's it. It returns documents in an XPath traversable form, courtesy of Hpricot.

A web crawler is a program that simply downloads pages, takes notes of what links there are on that page, and puts those links on its queue of links to crawl. Then it takes the next link off its queue and downloads that page and does the same thing. Rise and Repeat.

First, we create a class method named start that creates an instance of a webcrawler and then starts it. Of course, we could have done without this helper method, but it makes it easier to call.

module Crawler
  class WebCrawler
    class << self
      def start(url)
        crawler = WebCrawler.new
        crawler.start(url) do |doc|
          yield doc
        end
        return crawler
      end
    end
end

So next, we define the initialization method.

module Crawler
  class WebCrawler
    def initialize
      puts "Starting WebCrawler..."
      begin
        DRb.start_service "druby://localhost:9999"
        puts "Initializing first crawler"
        puts "Starting RingServer..."
        Rinda::RingServer.new(Rinda::TupleSpace.new)
        
        puts "Starting URL work queue"
        @work_provider = Rinda::RingProvider.new(:urls_to_crawl, Rinda::TupleSpace.new, "Queue of URLs to crawl")
        @work_provider.provide
        
        puts "Starting URL visited tuple"
        @visited_provider = Rinda::RingProvider.new(:urls_status, Hash.new, "Tuplespace of URLs visited")
        @visited_provider.provide
      rescue Errno::EADDRINUSE => e
        puts "Initialize other crawlers"
        DRb.start_service
      end
      puts "Looking for RingServer..."
      @ring_server = Rinda::RingFinger.primary
      
      @urls_to_crawl = @ring_server.read([:name, :urls_to_crawl, nil, nil])[2]
      @urls_status = @ring_server.read([:name, :urls_status, nil, nil])[2]
      @delay = 1
    end
  end
end

This bears a little explaining. The first webcrawler you start will create a DRb server if it doesn't already exist and do the setup. Then, every subsequent webcrawler it'll connect to the server and start picking URLs off the work queue.

So when you start a DRb server, you call start_server with a URI, then you start a RingServer. What a RingServer provides is a way from subsequent clients to find services provided by the server or other clients.

Next, we register a URL work queue and a URLs visited hash as services. The URL work queue is a TupleSpace. If you haven't heard of TupleSpace, the easiest way to think of it is as like a bulletin board. Clients post items on there, and other clients can take them out. This is what we'll use as a work queue of URLs to crawl.

The URLs visited is a Hash so we can check which URLs we've already visited. Ideally, we'd use the URL work queue, but DRb seems to only provide blocking calls for reading/taking from the TupleSpace. That doesn't make sense, but I couldn't find a call that day. Lemme know if I'm wrong.

module Crawler
  class WebCrawler
    def start(start_url)
      @urls_to_crawl.write([:url, URI(start_url)])
      crawl do |doc|
        yield doc
      end
    end

    private

    def crawl
      loop do
        url = @urls_to_crawl.take([:url, nil])[1]
        @urls_status[url.to_s] = true
        
        doc = download_resource(url) do |file|
          Hpricot(file)
        end or next
        yield doc

        time_begin = Time.now
        add_new_urls(extract_urls(doc, url))
        puts "Elapsed: #{Time.now - time_begin}"
      end
    end
  end
end

Here is the guts of the crawler. It loops forever taking a url off the work queue using take(). It looks for a pattern in the TupleSpace, and finds the first one that matches. Then, we mark it as 'visited' in @urls_status. Then, we download the resource at the url and use Hpricot to parse it into a document then yield it. If we can't download it for whatever reason, then we grab the next URL. Lastly, extract all the urls in the document and add it to the work queue TupleSpace. Then we do it again.

The private methods download_resource(), extract_urls(), and add_new_urls() are merely details, and I won't go over it. But if you want to check it out, you can download the entire file. There are weaknesses to it that I haven't solved, of course. If the first client goes down, everyone goes down. Also, there's no central place to put the processing done by the clients. But like lazy textbook writers, I'll say I'll leave that as an exercise for the readers. snippet!

---

webcrawler.rb

State change observer for ActiveRecord

When I started writing some code recently, I noticed that my controllers were getting fat. There was much to do, but there was a bunch of stuff in there that didn't have anything to do with actually carrying out the action--things like sending notifications. ActiveRecord already has observers to take action on certain callbacks. However, what I needed was to take actions on certain state transitions. Not seeing any immediate solutions in the Rails API, I decided to test myself and try writing one. I was bored too. So while I'm not sure if it was worth the time writing it, it certainly was kinda interesting. Here's what I came up with:

Just as a contrived example, let's say we are modeling the transmission of a car. It has three modes: "park", "reverse", "drive". We want to send a notification when a user tries to change it from "reverse" to "drive", but not when he tries to change it from "park" to "drive". If it didn't matter, and we just wanted to send notifications when the state changed to drive, we'd just use the observers that came with ActiveRecord. But since we do care where the state transition came from, here's what I came up with:

class CreateCarTransmission < ActiveRecord::Migration
  def self.up
    create_table :car_transmission do |t|
      t.column :engine_id, :integer, :null => false
      t.column :mode, :string, :null => false, :default => "park"
    end
  end

  def self.down
    drop_table :car_transmission
  end
end

class CarTransmission < ActiveRecord::Base
  include StateTransition::Observable
  state_observable CarTransmissionNotifier, :state_name => :mode
end

So then for my notifier I have:

class CarTransmissionNotifier < StateTransition::Observer
  def mode_from_drive_to_reverse(transmission)
    # send out mail and flash lights about how this is bad.
  end
end

And that's it. Whenever in the controller, I change the state from "reverse" to "drive", lights will flash and emails will be sent out condemning the action, and my controllers stay small and lean.

class CarController < ApplicationController
  def dismantle
    @car = Car.find(params[:id])
    @car.update_attribute :mode, "reverse"
    @car.update_attribute :mode, "drive"
  end
end

So where's the magic? It took a bit of digging around. There were two major things I had to do. I had to insert observers during initialization and I had to override setting of attributes to include an update to notify observers.

ActiveRecord doesn't exactly allow you to override the constructor. I don't think I tried too hard to mess around with it. Looking on the web, I happened upon has_many :through again, where he has some good tips that helped me through Rail's rough edges. While I didn't exactly follow his advice, I did find out about the call back, :after_initialize. It must be something new, because I don't see it in the 2nd edition of the Rails book, and the current official API doesn't list it. Other Rails API manuals seem to be more comprehensive, like RailsBrain and Rails Manual.

Then overridding attributes has always been a bit of a mystery. I found a listing of the attribute update semantics, which was helpful to figure out what I was looking for, but it was false, in that you can't use the first one (article.attributes[:attr_name]=value) to set an attribute. Looking in the Rails code for 1.2.3, it shows that attributes is a read_only hash. But it's right that you should override the second one (article.attr_name=value), since update_attribute() and update_attributes() depends on it.

Again, it ends up that the function I was looking for wasn't found in the official API as a method, other than a short mention in the description of ActiveRecord under Overriding Attributes, which makes it harder to find. Ends up that we can use write_attribute().

So that's pretty much it. Using some standard meta-programming like how plugins do it, you wrap it up, and it's pretty simple:

require 'observer'

module StateTransition
  module Observable
    class StateNameNotFoundError < RuntimeError
      def message
        "option :state_name needs to be set to the name of an attribute"
      end
    end

    def self.included(mod)
      mod.extend(ClassMethods)
    end

    module ClassMethods

      def state_observable(observer_class, options)
        raise StateNameNotFoundError.new if options[:state_name].nil?
        state_name = options[:state_name].to_s
        
        include Object::Observable

        define_method(:after_initialize) do 
          add_observer(observer_class.new)
        end

        define_method("#{state_name}=") do |new_state|
          old_state = read_attribute(state_name)
          if old_state != new_state
            write_attribute(state_name, new_state) # TODO yield the update method
            changed
            notify_observers(self, state_name, old_state, new_state)
          end
        end
      end

    end
    
  end

  class Observer
    def update(observable, state_name, old_state, new_state)
      send("#{state_name}_from_#{old_state}_to_#{new_state}", observable)
    rescue NoMethodError => e
      # ignore any methods not found here
    end  
  end

end

I had a difficult time figuring out how to define methods for an instance of a class. The only thing I came up with was to use define_method, or to include a module with instance methods in them. instance_eval() didn't work. The meta programming for ruby gets rather confusing when you're doing it inside a method--it seems hard to keep track of which context you're in.

So if you can make a use of this, great. If you think it's worth moving it into a plugin, let me know that too. If you know of a better way, by all means, let me know. tip!

Using ensure in yielding methods

I never really ever find too many occasion to use 'ensure'. It's a Ruby keyword that you can use for blocks of code that ensures, no matter what happens, exceptions or not, the code will be run when the block is finished. And then a quickie that I found in the rails core:

  def silence_warnings
    old_verbose, $VERBOSE = $VERBOSE, nil
    yield
  ensure
    $VERBOSE = old_verbose
  end

It does something simple, just silences the warnings for a particular block of code. On first glance, I would have just written it without the 'ensure'. However, that won't work for yielded blocks that call return or if exceptions are thrown in it, I think. This way, no matter what happens in the block, it will always restore the state that it changed.

Avoiding the SUDO police with Capistrano

When deploying on a shared host, often times, you won't be able to sudo anything. I was originally thinking that I had to override the cleanup task in cappy, but a quick look in google found: Avoiding the SUDO police with Capistrano. You can simply "set :use_sudo, false" in your deploy.rb. Tip!

Capistrano tasks for BackgrounDRb — Bryan’s Bytes

Capistrano tasks for BackgrounDRb — Bryan’s Bytes

Here's a good little snippet I found for running BackgroundRb through Capistrano. Not much commentary from me, other than hurray~ I had wondered about why it wasn't working. I didn't know nohup existed as a command--I've always used the trailing '&'. Goes to show you that a little background goes a long way.

Ruby Snippet: Caching object attributes

Here's another little snippet. I'm not sure if I'm extracting out boiler plate code prematurely, but it seems right.

A good general rule of thumb for refactoring is that one should always call an object for its value, rather than storing object values in temporary variables when you're using the object. Generally, you can get away with setting the value of an object to a temporary variable, and then using that temporary variables for subsequent calculations

# c = Collection.new((0..500).to_a)
collection_sum = c.sum
collection_sum * 3 + 2 # some calculation with the sum
if collection_sum == 4 # some comparison with the sum.
  # do something else
end

You're essentially caching the value outside of the object, 'c'. This is good if 'sum' is an expensive call. However, if the code segment gets large, this method tends to get confusing, especially if you stored it in temporary variables at different times, etc. (Also a good rule of thumb is that your scope should never be bigger than about 10-20 lines) It's better to refer to the value directly from the object.

# c = Collection.new((0..500).to_a)
c.sum * 3 + 2 # some calculation with the sum
if c.sum == 4 # some comparison with the sum.
  # do something else
end

This is not applicable to functional programming languages, since all variables are consts within a scope. But for object-orientated imperative languages, this generally makes for less messy code.

However, performance is a problem, if you have to calculate the sum each time you needed it. An easy solution would be to cache the value. An example would be summing the values across some collection. Normally, that wouldn't be a problem, except if you had hundreds thousand entries. If nothing was added to the collection, the sum would stay the same. If something was added, mark the collection to need updating, and then the next time sum() is called, update the value.

You'd need both a variable to keep track of whether the attribute needed updating, and another variable to hold the result. If you only had one attribute, that'd be ok. If you have more than one, it starts to get a little bit messy. This is where meta programming comes in. I wrote a piece of code that did the bookkeeping of caching attributes for you. You'd use it like:

class Collection
  include AttributeCache

  def initialize
    @array = []
    cache :sum, :initial => 0
  end

  def add(x)
    outdate_sum
    @array << x
  end

  def sum
    cached_sum { @array.inject {|t, e| t += e} }
  end
  
end

The code is simple. In the initialization method, there is a call to cache an attribute, sum. And then in the other methods, you'd mark where the sum would be outdated, and in the actual call to sum, you'd specify what to do to update the sum.

module AttributeCache

  def metaclass; class << self; self; end; end
  
  def cache(attr_name, options)
    instance_variable_set "@#{attr_name}", options[:initial]
    instance_variable_set "@#{:sum}_outdated", true

    metaclass.instance_eval do 
      define_method("outdate_#{attr_name}") do
        instance_variable_set "@#{attr_name}_outdated", true
      end
    end
    
    metaclass.class_eval %Q{
      def cached_#{attr_name}(&block)
        if @#{attr_name}_outdated
          @#{attr_name}_outdated = false
          @#{attr_name} = block.call
        end
        return @#{attr_name}
      end
    }

  end
  
end

The biggest hurdle was to figure out how to define a method that accepted a block with meta programming. The best I came up with was to use class_eval. If you have better suggestions, let me know. tip!

Defaults and Guards

I was watching the javascript lecture, and it mentioned guards and defaults in javascript, and I realized that it was the same in Ruby, and was something that I've been looking for. I had already known about defaults. If you were coming from a C or Java background, you probably would write it in ruby as:

if !a.nil?
  b = a
else
  b = 0
end

If you were more versed in other more dynamically typed languages, you'd rather write it in ruby as:

b = a || 0

It seems a bit obtuse, but I think this structure is invoked so often in my experience, that the shorthand is actually quite welcome. And it's not too bad once you know what it is.

In Erlang (and I think Haskell), there are guards for a function. Guards are basically a condition that must exist before the function is run. If you were coming from a C or Java background, you'd probabily write it in ruby as:

if !a.nil?
  b = a.some_method()
end

But really, it can be written as:

b = a && a.some_method

or, like

b = a.some_method unless a.nil?

I think the latter is more readable, but there would be no default if 'a' didn't exist. With the bitwise operators, you can chain it:

b = (a.respond_to?(:gsub) && a.gsub(/h/, '')) || "default!"

Now, that's starting to be hard to read. It has a guard for a, so that it doesn't raise an error when it tries to run gsub() if a is nil, and if it is nil, it will return the default. With this kind of thing, you'd want to be judicious and careful when using it. It's definitely easy to go crazy with this sort of thing. Remember, the goal is ease of readability, cuz you only ever write a line once, but you read it lots of times.

Ruby Quiz #122 Solution: Checking Credit Cards using meta-programming

So this is the first time I actually did a RubyQuiz for real. I spent probably 3 or 4 hours on it. Not too shabby. And, I got to do a little bit of meta-programming! It's basic meta-programming, but I liked the solution. Brief intro to the quiz:

Before a credit card is submitted to a financial institution, it generally makes sense to run some simple reality checks on the number. The numbers are a good length and it's common to make minor transcription errors when the card is not scanned directly.

The first check people often do is to validate that the card matches a known pattern from one of the accepted card providers. Some of these patterns are:

      +============+=============+===============+
     | Card Type  | Begins With | Number Length |
     +============+=============+===============+
     | AMEX       | 34 or 37    | 15            |
     +------------+-------------+---------------+
     | Discover   | 6011        | 16            |
     +------------+-------------+---------------+
     | MasterCard | 51-55       | 16            |
     +------------+-------------+---------------+
     | Visa       | 4           | 13 or 16      |
     +------------+-------------+---------------+ 

There's more rules for each credit card at wikipedia. So normally, how would you do this with OO design? First thing that came to mind was creating a general CreditCard base class, and use polymorphism to implement the rule for each type of card, which is a subclass of CreditCard (i.e. Mastercard extends CreditCard). The problem with this, I've always found is that there's a proliferation of classes when you do something like this. People have solved this problem with other patterns, such as Factories, to build families of classes.

But that's a lot of structure that I didn't want to write for a little RubyQuiz. So I opted for case statements at first:

def type(cc_num)
  case cc_num
  when /^6011.*/
    return :discover if cc_num.length == 15
  when /^5[1-5].*/
    return :mastercard if cc_num.length == 16
  ...other card rules...blah blah blah
  end
  return :unknown
end

But as we all learned from having to maintain a proprietary server program written in C nested 11 or 12 layers deep all in one main file, case statements suck and don't scale (guess who had to do that?). So what's a better solution? I'd like to think I came up with a nice one.

With dynamic programming languages, I find that a lot of the problems that design patterns solve simply go away. And with meta-programming, it can be a much more flexible tool to solve design problems, rather than with design patterns. In a way, I created a very very tiny domain specific language for checking credit card type and validity. All you need to do to use it is define the rules in the table above in your class which subclasses credit card checker:

require 'credit_card_checker'

class MyCreditCardChecker < CreditCardChecker
  credit_card(:amex) { |cc| (cc =~ /^34.*/ or cc =~ /^37.*/) and (cc.length == 15) }
  credit_card(:discover) { |cc| (cc =~ /^6011.*/) and (cc.length == 16) }
  credit_card(:mastercard) { |cc| cc =~ /^5[1-5].*/ and (cc.length == 16) }
  credit_card(:visa) { |cc| (cc =~ /^4.*/) and (cc.length == 13 or cc.length == 16) }
end

CCnum = "4408041234567893"
cccheck = MyCreditCardChecker.new
puts cccheck.type(CCnum) # => :visa 
puts cccheck.valid?(CCnum) # => true

Neat! So this way, you can have any type of credit card checker you want, in any combination. And if suddenly there was a proliferation of new credit card companies, you can add them pretty easily. How is this done? Well, let me show you:

require 'enumerator'

class CreditCardChecker
  def self.metaclass; class << self; self; end; end

  class << self
    attr_reader :cards

    def credit_card(card_name, &rules)
      @cards ||= []
      @cards << card_name

      metaclass.instance_eval do 
        define_method("#{card_name}?") do |cc_num|
          return rules.call(cc_num) ? true : false
        end
      end
    end

  end

  def cctype(cc_num)
    self.class.cards.each do |card_name|
      return card_name if self.class.send("#{card_name}?", normalize(cc_num))
    end
    return :unknown
  end
  
  def valid?(cc_num)
    rev_num = []
    normalize(cc_num).split('').reverse.each_slice(2) do |pair|
      rev_num << pair.first.to_i << pair.last.to_i * 2
    end
    rev_num = rev_num.to_s.split('')
    sum = rev_num.inject(0) { |t, digit| t += digit.to_i }
    (sum % 10) == 0 ? true : false
  end
  
  private
  def normalize(cc_num)
    cc_num.gsub(/\s+/, '')
  end
end

If you don't know much about meta-programming yet, you might want to try _why's take on seeing metaclasses clearly along with Idiomatic Dynamic Ruby. Don't worry if it takes a while...I was stumped for a while also.

Anyway, the magic is in the method credit_card. Notice it's between "class << self" and "end", which means that this method is defined in the singleton class of the class CreditCardChecker. But you can just think of it as a class method. Same thing with the method metaclass(), it is a class function that returns the singleton class of the caller.

Now, the thing is, this isn't very exciting in itself. However, notice that credit_card() is executed in the subclass MyCreditChecker. This means that when inside credit_card(), metaclass returns NOT the singleton class of CreditCardChecker, but the singleton class of MyCreditCardChecker! Then when we proceed to do an instance_eval() and a define_method(), we are defining a new method in the singleton class of the subclass MyCreditChecker. Inside the method, it will call the block that evaluates the rule given for that card. If true, it returns true and false if false. The only reason I did it that way, is so in case the block returns an object, it'll return true instead of the object.

Therefore, to any instance of MyCreditChecker, it will look like there's a class method with the name of the credit card. So if you did:

require 'credit_card_checker'

class MyCreditCardChecker < CreditCardChecker
  credit_card(:amex) { |cc| (cc =~ /^34.*/ or cc =~ /^37.*/) and (cc.length == 15) }
end

MyCreditCardChecker.amex?(cc_num) would be a valid method that checks if the credit card number is an American Express Card. And what cctype() method does is that it cycles through all the known credit cards and returns the first one that's valid. The rest is standard fare, so I won't go through it.

And oh, btw, each_slice() and each_cons() got moved to the standard library, so you have to include enumerator in order to use it--even though the official ruby docs say that it's still in the Enumerables class in the language.

Reconnecting to database server in Rails

I've had more posts up my sleeve, though I haven't had time to actually polish them up. I should make my blog posts go back to its roots, where I just said anything as a first draft. That way, you'll get more stuff. So as usual, I happened across my travels through Rails-land and saw something that I don't think gets seen too often...since I couldn't find it on the first page of Google. It was an error like this:

>> user = Account.find(1)
ActiveRecord::StatementInvalid: Mysql::Error: MySQL server has gone away: 
SELECT * FROM accounts WHERE (accounts.id = 1) from /usr/lib/ruby/gems/1.8/gems/activerecord-1.15.0/lib/active_record/
connection_adapters/abstract_adapter.rb:128:in `log'
...blah blah blah...

Since connections are expensive (in terms of time) to make, web frameworks, and anyone making raw connections to the database, will use the same connection for multiple SQL queries, and close the connection when you're done.

Usually you won't see this in Rails, because it does a pretty good job of maintaining the connection, either per session, or per user action in the controller. However, when you have a background process running using something like BackgrounDrb, if there is no activity between the background worker and the database for a couple hours, the database is going to close the connection, and the worker will still think the connection is valid. In other words, ActiveRecord::Base.connected? will return true.

Here is also where I found a use for 'else' in blocks as mentioned by Jamis Buck. When the connection goes out cold, we can't really tell that its' because it's been sitting there too long. It will raise an ActiveRecord::StatementInvalid, which is the same thing raised when you have a bug during development. As a simple fix, I just wanted something to try reconnecting to the database once, just in case it was only because the connection was cold.

class SomeBackgroundWorkerClass
def initialize
  @already_retried = false
end

def some_database_operation
  begin
    Account.find(1)
    # or some other database operations here...
  rescue ActiveRecord::StatementInvalid
    ActiveRecord::Base.connection.reconnect!
    unless @already_retried
      @already_retried = true
      retry 
    end
    raise
  else
    @already_retried = false
  end
end
end

So, that way, as long as it succeeds every other time, it'll keep on going. Tip!

Code quickie: How to interlace two arrays in ruby

Hrm, I'm not sure whether it's worth posting or not, but I was looking for a way to interlace two arrays in ruby. This is what I came up with originally, and it worked fine for a bit:

class Array
  def interlace(other_array)
    interlaced_array = []
    self.each_with_index { |x,i| interlaced_array << x << other_array[i]}
    return interlaced_array
  end
end

This code has the problem that on arrays of different sizes, it'll either leave off the longer array's remaining elements or insert nils for the shorter array. This isn't a good default behavior. What we'd like is for the longer array, whichever one it is, to get its remaining elements tacked on the end of the interlaced array after the elements in the shorter array have run out.

I decided to do it recursively. I haven't written anything recursive since that post on Erlang.

class Array
  # interlaces an array with another array.  It dovetails the two arrays together.
  # 
  #   [1,2,3,4,5,6].interlace([7,8,9]) # => [1, 7, 2, 8, 3, 9, 4, 5, 6]
  #   
  #   [1,2,3].interlace([1,2,3,4,5]) # => [1, 1, 2, 2, 3, 3, 4, 5]
  def interlace(other_array)
    return other_array if self.empty? 
    return [self[0]] + other_array.interlace(self[1..-1])
  end
end

Great, now it works on different sized arrays! What you'll notice is that unlike most recursions, this one "switch places" with the other array on every recursion with the call, other_array.interlace(self[1..-1]). It's the first time I've seen a recursion like this. It certainly simplifies the code immensely, since you don't have to check for which array is bigger or smaller. Note, however, that this only works because the method is public. The technique doesn't work for private recursion helpers.

While you don't get to use recursion all that often, I find that its solution is often pretty elegant compared to iteration. I think that it will be useful when we start to use more data structures that are more fractal in nature. Currently, we have lists and trees. Hrm, there might be some possibilities here. For now, we'll keep this short, and if I come up with anything on this front, I'll let ya'll know! Tip!

A simple isometric engine

For a day or two, I've been messing around with Canvas for firefox. I've managed to code up a very simple isometric engine in about 2 days, provided the canvas tutorial. The hardest part was really just making sure it rendered correctly from back to front. But other than that, everything seemed pretty straightforward.

One thing I'll have to say though, is that this was my first foray into javascript, and it's been more flexible than I had remembered back in 1996. Most people don't take advantage of javascript's language features, since most scripts are fairly short. However, javascript supports object orientated programming, but using a prototype based object instantiation. This means that there is no such thing as classes, but all subsequent objects are created by cloning existing objects. The new objects are then extended to fit the need of the programmer. The following mirrors how you would create a 'class'.

function IsoEngine(canvas_id) {
this.canvas = document.getElementById(canvas_id);
if (this.canvas == null) { return; };
this.ctx = this.canvas.getContext('2d');
var objects = new Array();

this.add_to_scene = function(object) {
objects.push(object);
};

this.clear = function() {
this.ctx.clearRect(0,0, this.canvas.width, this.canvas.height);
}

this.draw = function() {
for (var i = 0; i < objects.length; i++) {
objects[i].draw();
}
};

As you can see, it's all using functions, and it makes for weird looking syntax for those of us coming from a class-based OOP. What was also a pleasant surprise was that javascript supported higher order programming. This means that functions can take other functions as arguments, and if I'm not mistaken, this makes closures possible. It's hell of a lot better than passing function pointers around in C. The syntax for that always left me confused.