Ruby hangman for Martes, Seite de Mayo

Skip to first unread message


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+=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

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

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

p data.

All we have to do is fill in the blanks.

See you at the meeting,

-- Markus

Reply all
Reply to author
0 new messages