1.  Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.  Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- =-=-=

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']

    Are the entries in the array always unique?
Or do we have to be able to handle the array such as:

['users_controller', 'users_controller_test', 'account_controller',  
'account_controller_test',  'bacon', 'users_controller_test']

Also is the unicode ellipsis counted as one or three characters?

-Gautam Dey
On Jun 16, 2006, at 5:33 AM, Ruby Quiz wrote:

Gautam.
------------------------------------------------------------------------
--------------------------------------------------------
#!/usr/bin/env ruby -w
#  Suggestion:  A [QUIZ] in the subject of emails about the problem  
helps everyone
#  on Ruby Talk follow the discussion.  Please reply to the original  
quiz message,
#  if you can.
#
#  -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=-=-=
#
#  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.
#
#  This code is released under the GPL.

require 'Abbrev'
module  GDCompress
   def compress (size)
     usedNameHash = Hash.new
     compressedTitleNames = Array.new
     for tabTitle in self
       newTabTitle = "" # start with empty string.
       if tabTitle.length > size
           caseValue = 0
           loop do
             newTabTitle = tabTitle[0,size-(1+caseValue)] + "…" +  
tabTitle[-caseValue,caseValue]
             #print "\t#{newTabTitle} is the new tabTitleTitle for #
{tabTitle}\n"
             caseValue = caseValue + 3
             break unless usedNameHash[newTabTitle]
           end
       else
         newTabTitle = tabTitle
       end
       usedNameHash[newTabTitle] = tabTitle
       compressedTitleNames[compressedTitleNames.length] = newTabTitle
     end
     compressedTitleNames
   end
end

class Array
   include GDCompress
   extend  GDCompress
end

print ['users_controller', 'users_controller_test',
      'account_controller', 'account_controller_test',
      'bacon'].compress(10)

------------------------------------------------------------------------
---------------------------------------------------

On Jun 16, 2006, at 5:33 AM, Ruby Quiz wrote:

class String
  def compress(total_length, end_length)
    self[0...total_length-end_length] + '...' + self[length-end_length..-1]
  end
end

class Array
  def compress!(max_length)
    max_length = 4 if max_length < 4
        score = Hash.new(0)
        usable_length = max_length - 3
        order = (0..usable_length).sort_by{|len|
[(len-usable_length.to_f/2).abs,len].min}
        to_compress = select {|s| s.length > usable_length}
        to_compress.each {|s| order.map{|l| score[s.compress(usable_length,l)] += 1 } }
        to_compress.each{|s|
          s.replace order.map{|l| s.compress(usable_length,l) }.min{|a,b|
score[a] <=> score[b]}
          score[s] += 100
        }
        self
  end
end

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:

        # Returns the length of the longest common
        # 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:

        $KCODE = "u"          # make jcode happy (silence a warning)
        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:

        $KCODE = "u"
        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.

irb(main):002:0> %w(apple_juice orange_juice grape_juice
                    prune_juice).compress(10)
=> ["apple...", "orange...", "grape...", "prune..."]
irb(main):003:0> %w(orange_juice orange_marmalade orange_flavor
                    orange_pulp).compress(10)
=> ["...juice", "...rmalade", "...flavor", "o...pulp"]

The idea is that stuff common to all or almost-all of the original
strings doesn't really help you when staring at a bunch of tabs.
Abbreviating "orange_juice" as "orange..." makes sense when you have a
bunch of juices, but not when you have a bunch of orange things.

Avoiding previously used abbreviations is done with the bit: