# Solution to quiz 83, Short but Unique

#! /usr/bin/env ruby

# 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

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

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 > 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,spec] = repstr if spec > 0
if retval.include?(candidate)
record
else
score = score_compression(s,spec,spec,self)
if score >= record
[score, candidate]
else
record
end
end
}
)
}
retval
end
end

if FILE == \$0
ARGV[1,ARGV.length].compress(ARGV.to_i).each {|s| puts s}
end

END

(END included since my sig isn’t valid ruby)