Ruby hangman for Martes, Seite de Mayo

47 views
Skip to first unread message

markus

unread,
May 7, 2013, 1:46:45 AM5/7/13
to pdxruby
The problem: given a list of a thousand or so strings that share a
common prefix (say, filenames from an archive or fully qualified
attribute names from a complex ontology), find the common prefix for the
entire set.

Solution 1: The "obvious" solution, from a procedural programming
perspective at least, would look something like:

ans = data.first
data.each { |s|
i=0
i+=1 while s[i] && s[i] == ans[i]
ans = s[0...i]
}
p ans

Solution 2: A bit of code golfing gets us to the official clever
solution:

p data.inject { |s1,s2| "#{s1}\0#{s2}" =~ /^(.*).*\0\1/m; $1}

It's clever, and a bit shorter, but on my test data, this was about 5%
slower, and the cleverness certainly doesn't make the code any easier to
follow.

Solution 3: What we'd like is a clever solution that had some sort of
tangible benefit...say, an order of magnitude reduction in run-time, and
perhaps makes the intent a little clearer. Fortunately, this isn't too
hard:

p data.
____a___a______a__.
_e___e______.
________i__.
_____________o____.
____

All we have to do is fill in the blanks.

See you at the meeting,

-- Markus

Reply all
Reply to author
Forward
0 new messages