by Ryan Williams
I use Eclipse (with RadRails!) I have a bunch of files open in tabs. Once enough files are open, Eclipse starts to truncate the names so that everything fits. It truncates them from the right, which means that pretty soon I'm left unable to tell which tab is "users_controller.rb" and which is "users_controller_test.rb", because they're both truncated to "users_control...".
The quiz would be to develop an abbrev-like module that shortens a set of strings so that they are all within a specified length, and all unique. You shorten the strings by replacing a sequence of characters with an ellipsis character [U+2026]. If you want it to be ascii-only, use three periods instead, but keep in mind that then you can only replace blocks of four or more characters.
It might look like this in operation:
['users_controller', 'users_controller_test', 'account_controller', 'account_controller_test', 'bacon'].compress(10) => ['users_c...', 'use...test', 'account...', 'acc...test', 'bacon']
There's a lot of leeway to vary the algorithm for selecting which characters to crop, so extra points go to schemes that yield more readable results.
Quiz Summary
This is a pretty real world problem many applications struggle with. I dare say it's hard to get right, which is probably why so many applications don't even try. We had a few adventurous solvers though and they got some workable results. Let's look into Daniel Martin's solution.
I felt Daniel got some great output, by favoring the word boundaries of the terms to shorten. Here's a sample of the code being run on the quiz problem set:
users...er
use...test
account...
acc...test
bacon
Notice how the compression favors keeping word intact, when possible. That seems to give fairly good results overall.
Alright, let's see how Daniel does it:
# substring of "a" and "b"
def string_similarity(a, b)
retval = 0
(0 ... b.length).each { |offset|
len = 0
(0 ... b.length - offset).each { |aind|
if (a[aind] and b[aind+offset] == a[aind])
len += 1
retval = len if retval < len
else
len = 0
end
}
}
(1 ... a.length).each { |offset|
len = 0
(0 ... a.length - offset).each { |bind|
if (b[bind] and a[bind+offset] == b[bind])
len += 1
retval = len if retval < len
else
len = 0
end
}
}
retval
end
# ...
The comment above this method tells you exactly what it does, which is to return the numerical length of the longest common substring for the parameters. It works by walking each possible substring of b and checking that the string occurs in a somewhere. It then reverses and repeats the process because one string might be longer than the other. The highest count seen overall is returned.
Daniel mentioned that he has been out of Ruby for a bit and his Ruby might be a little rusty. The above code works just fine, of course, but we can shorten it up a bit, if we want to. Here's another way to write the above:
require "jcode" # for String#each_char
require "enumerator" # for Enumerable#each_cons
def string_similarity(str1, str2)
long, short = [str1, str2].sort_by { |str| str.length }
long.length.downto(0) do |len|
long.enum_for(:each_char).each_cons(len) do |substr|
return substr.length if short.include? substr.join
end
end
return 0
end
Again, this works the same. I try all possible substrings of the longer string, from longest to shortest, for inclusion in the shorter string. Since the code works with the longest strings first, we can return the first answer we find. I'm not saying either method is better, but hopefully you can figure out how they work, between the two of them.
Let's get back to Daniel's code:
def score_compression(target, start, len, alltargets)
score = target.length - len
score += 3 if len == 0
score += 3 if (target[start,1] =~ %r(_|\W) or
target[start-1,2] =~ %r([a-z0-9][A-Z]))
score += 3 if (target[start+len-1,1] =~ %r(_|\W) or
target[start+len-1,2] =~ %r([a-z0-9][A-Z]))
prebit = target[0,start]
postbit = target[start+len,target.length]
scoreminus = 0
alltargets.each{|s|
scoreminus += string_similarity(s,prebit)
scoreminus += string_similarity(s,postbit)
}
score - (1.0 / alltargets.length) * scoreminus
end
# ...
The above code just rates a possible replacement. The target variable holds the original string, start and len mark the area to be replaced with the repeat string, and alltargets holds the other strings that need compressing.
The most interesting part starts on the third line of the method, where a couple of checks are used to score substitutions at word boundaries higher. Note that the checks include punctuation boundaries and changes in case as a boundary. This, in my opinion, is the source of the quite readable end result.
Note that the last section of that method compares the pieces of the string that will be left after the replacement with other strings in the result set using the substring count method we examined earlier. This code is there to prevent two strings from being compressed to the same representation (though I doubt this weighted scoring system is perfect).
Finally, here's the method that does the actual work:
class Array
def compress(n, repstr = '...')
retval = []
self.each { |s|
short_specs =
(s.length - n + repstr.length ..
s.length - n + repstr.length + 2).inject([]) { |sp,l|
sp + (0 .. s.length - l).map {|st| [st,l]}
}.select { |a| a[1] > repstr.length}
if (s.length <= n) then short_specs.unshift([0,0]) end
retval.push(
short_specs.inject([-999,""]) { |record, spec|
candidate = s.dup
candidate[spec[0],spec[1]] = repstr if spec[1] > 0
if retval.include?(candidate)
record
else
score = score_compression(s,spec[0],spec[1],self)
if score >= record[0]
[score, candidate]
else
record
end
end
}[1]
)
}
retval
end
end
# ...
This code was a little tricky for me to break down, so let me see if I can explain it in manageable chunks. This method works over each string in the Array, building a compressed replacement for each one as it goes. To build those replacements it first constructs an Array of indices and lengths where it could replace content with the replacement string. It then scores each of those replacements and selects the highest candidate as the result.
Here's how one might invoke the above:
if __FILE__ == $0
ARGV[1,ARGV.length].compress(ARGV[0].to_i).each {|s| puts s}
end
Now, since Unicode has been such a hot topic lately, let's see how this code handles using a real ellipsis character. If I change the above code to:
if __FILE__ == $0
puts ARGV[1..-1].compress(ARGV[0].to_i, "…")
end
and run the code again, here's the new output:
users…er
use…test
account…
acc…test
bacon
Oops, I asked for 10 characters but got less than that. The reason is that the code we just examined is counting the byte length of our replacement string, in this bit of code right here:
class Array
def compress(n, repstr = '...')
retval = []
self.each { |s|
short_specs =
(s.length - n + repstr.length ..
s.length - n + repstr.length + 2).inject([]) { |sp,l|
sp + (0 .. s.length - l).map {|st| [st,l]}
}.select { |a| a[1] > repstr.length}
# ...
As a fix, I'm going to set the $KCODE variable for Unicode support, load the jcode library for its helper methods, and change all those repstr.length calls to repstr.jlength. Here's a look at those changes:
require "jcode"
# ...
class Array
def compress(n, repstr = '...')
retval = []
self.each { |s|
short_specs =
(s.length - n + repstr.jlength ..
s.length - n + repstr.jlength + 2).inject([]) { |sp,l|
sp + (0 .. s.length - l).map {|st| [st,l]}
}.select { |a| a[1] > repstr.jlength}
# ...
Does that fix us up? Let's see:
users…ller
users…test
account…er
account…st
bacon
Bingo. Now we get the extra characters from using the shorter string. Don't let people tell you Ruby can't handle Unicode today.
My thanks to all who gave this quiz a shot. I expect you all to email your solutions as patches all the applications out there that botch the display of tabs like this.
Tomorrow we have an easy problem for those working through Learn to Program...
