class Array
# does a kind of ZIP compression for integer arrays
# examples:
# [0,1,2,3].compress! => [[0, 4]]
# [1,2,3,8,9,10,11].compress! => [[1, 3], [8, 4]]
# [1,3,5].compress! => [1, 3, 5]
# [1,3,5,6].compress! => [1, 3, [5, 2]]
def compress!
compact!
return [] if empty?
uniq!
sort!
output = []
start = shift
cnt = 1
each do |item|
if item == start + cnt
cnt += 1
else
output << (cnt > 1 ? [start, cnt] : start)
cnt = 1
start = item
end
end
output << (cnt > 1 ? [start, cnt] : start)
self.replace output
end
end
Refactorings
No refactoring yet !
sargon
April 15, 2009, April 15, 2009 16:57, permalink
No rating.
Login to rate!
Interesting. I have just recoded it in Haskell. I have not so much practice in ruby, but
I would try to define a function that count the interval for you, maybe recursively.
Alec Leitner
April 15, 2009, April 15, 2009 23:31, permalink
No rating.
Login to rate!
found a shorter solution, still not perfect (and hard to read).
class Array
def compress!
compact!
return [] if empty?
uniq!
sort!
output = [[self[0],1]]
self[1..-1].each do |x|
x > output[-1].sum ? output << [x,1] : output[-1][1] += 1
end
output.map! {|x| x[1] == 1 ? x[0] : x}
self.replace output
end
end
Alec Leitner
April 15, 2009, April 15, 2009 23:36, permalink
No rating.
Login to rate!
cleaned it up a bit... any additional suggestions?
class Array
def compress!
compact!
return [] if empty?
uniq!
sort!
out = [[shift,1]]
each { |n| n > out[-1].sum ? out << [n,1] : out[-1][1] += 1 }
out.map! {|n| n[1] == 1 ? n[0] : n}
replace out
end
end
Alec Leitner
April 15, 2009, April 15, 2009 23:52, permalink
No rating.
Login to rate!
and here's the non-destructive version (no difference in speed):
class Array
def compress
sorted = compact.uniq.sort
return [] if sorted.empty?
out = [[sorted.shift,1]]
sorted.each { |n| n > out[-1].sum ? out << [n,1] : out[-1][1] += 1 }
out.map { |n| n[1] == 1 ? n[0] : n }
end
end
I've written a small method that compresses an array of integers, and I'm sure it can be optimized. As it's a rather unusual problem, here's the reason for it: for displaying a timeline in a small internal project management app I query the DB for each day a project was worked on, starting with 0. E.g. a project is being worked on for 8 days in a row, then 2 days pause, then 3 more days, I'd have the following array: [0,1,2,3,4,5,6,7,10,11,12]. I now compress this array to AJAX-update a graph with the data, and I get: [[0,8], [10,3]]. To keep the data shorter, I return a single value instead of an array if it's only been one day in a row, aka the following is possible too: [1,3,5,6].compress => [1, 3, [5, 2]]
PS: by the way, I don't really care if the original array is replaced or not, I just chose to use the destructive bang versions to keep the code shorter.