# Short But Unique (#83)

**URL:** <https://www.ruby-forum.com/t/short-but-unique-83/63591>\
**Category:** Ruby\
**Created:** [June 16, 2006, 2:34pm UTC](https://www.ruby-forum.com/t/short-but-unique-83/63591 "2006-06-16T14:34:49Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [June 16, 2006, 2:34pm UTC](https://www.ruby-forum.com/t/short-but-unique-83/63591/1 "2006-06-16T14:34:49Z")

</div>

The three rules of Ruby Q.:

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 Q. by submitting ideas as often as you can:

[http://www.rubyquiz.com/](http://www.rubyquiz.com/)

1. Enjoy!

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

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

by Ryan W.

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.

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [June 17, 2006, 10:18pm UTC](https://www.ruby-forum.com/t/short-but-unique-83/63591/2 "2006-06-17T22:18:43Z")

</div>

Two things:

```
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 D.

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [June 18, 2006, 6:43pm UTC](https://www.ruby-forum.com/t/short-but-unique-83/63591/3 "2006-06-18T18:43:51Z")

</div>

On Jun 17, 2006, at 3:15 PM, Gautam D. wrote:

> Two things:
> 
> Are the entries in the array always unique?

Let’s assume they are, sure.

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

One, in my opinion.

James Edward G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [June 20, 2006, 10:22am UTC](https://www.ruby-forum.com/t/short-but-unique-83/63591/4 "2006-06-20T10:22:17Z")

</div>

My entry is simple, and not very complicated. At first I was thinking  
of make it much more complicated and using the abbrev to get human  
readable entries for and abbreviated version  
of the title. But that seemed to complicated things more then help.  
So, I just went for a simple algorithm. My solution basically  
consistest of taking a simple truncation of the file name, then if  
that is already taken, going to the end and shifting the ellipsis to  
the left while reveling more of the last word, till a the title does  
not match anymore. There is a very large possibility of getting an  
infinite loop. And I have not tested it on many strings. Also,  
another flaw is that if two string are identical but smaller then the  
value sent to the function, it will return both string untouched.  
Since it does not touch any string smaller or equal to the length  
passed to it.

## Gautam.

* * *

#!/usr/bin/env ruby -w

# Suggestion: A [QUIZ] in the subject of emails about the problem

helps everyone

# on Ruby T. follow the discussion. Please reply to the original

quiz message,

# if you can.

# 

# -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

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

# 

# by Ryan W.

# 

# 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)

* * *

* * *

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [June 20, 2006, 5:40pm UTC](https://www.ruby-forum.com/t/short-but-unique-83/63591/5 "2006-06-20T17:40:30Z")

</div>

Here is my solution.  
It tries to generate unambiguous abbrevations, if those don’t exist,  
it uses the least ambiguous one and always avoids using the same  
abbrevation twice.  
There’s also a readability thing built in, strings with many  
characters at the beginning or having the characters split equally  
over the beginning and ending parts are considered the most readable.

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

if **FILE** ==$0  
p [‘users\_controller’, ‘users\_controller\_test’,‘account\_controller’,  
‘account\_controller\_test’,‘bacon’].compress!(10)  
p Array.new(10){‘abcdefghijklmnopqrstuvwxyz’}.compress!(12)  
p [‘aaaaaazbbbbb’,‘aaaaaaybbbbb’].compress!(9)  
end