Skip to content

Instantly share code, notes, and snippets.

@ChrisVilches
Last active October 4, 2017 17:54
Show Gist options
  • Save ChrisVilches/7b41c68431ef167058e8e084e0894432 to your computer and use it in GitHub Desktop.
Save ChrisVilches/7b41c68431ef167058e8e084e0894432 to your computer and use it in GitHub Desktop.
Dos funciones en Ruby, una para comprimir rangos y otra para diferencia de rangos (o conjuntos).
require 'test/unit'
extend Test::Unit::Assertions
# Comprimir rangos
# [1,2,3,7,8,9,10] => [[1,3], [7,10]]
# Diferencia de rangos
# Se tienen dos listas que se restan A - B
# A = [[1, 100], [200, 500]] esto significa que hay dos rangos 1→100 y 200→500
# B = [[50, 70], [150, 300]] representa lo mismo que lo anterior
# A - B = [[1, 50], [70, 100], [300, 500]]
# (Aunque primero es necesario que las listas esten aplanadas [[1,2], [3,4]] => [1,2,3,4])
def compress(list)
def successor?(a, b)
return true if a + 1 == b
return false
end
return [] if list.empty?
return [[list[0], list[0]]] if list.length == 1
a = list[0]
pairs = []
i = 1
while i < list.length do
b = list[i]
if !successor?(list[i-1], b) && b != list[i-1]
pairs << [a, list[i-1]]
a = b
end
if i == list.length - 1
pairs << [a, list.last]
end
i = i + 1
end
return pairs
end
def difference(r, s)
i = 0
j = 0
result = []
set = nil
restriction_open = false
available_open = false
while j <= s.length
while i < r.length
if j < s.length && r[i] > s[j]
break
end
if available_open = (i % 2 == 0)
a = r[i]
b = r[i+1]
n = s[j]
between = (j == s.length) || (a < n && n < b)
set = [s[j+1]] if (restriction_open && between)
set = [r[i]] if !restriction_open
else
if !restriction_open
set << r[i]
result << set if set[0] != set[1]
end
end
i = i + 1
end
if restriction_open = (j % 2 == 0)
if available_open
set << s[j]
result << set if set[0] != set[1]
end
else
set = [s[j]] if available_open
end
j = j + 1
end
return result
end
assert_equal (difference [1, 10, 11, 20], []), [[1, 10], [11, 20]]
assert_equal (difference [1, 10, 11, 20], [8, 12]), [[1, 8], [12, 20]]
assert_equal (difference [1, 100, 200, 500], [50, 70, 150, 300]), [[1, 50], [70, 100], [300, 500]]
assert_equal (difference [1, 100, 900, 1000], [20, 30, 60, 70, 90, 110, 400, 500]), [[1, 20], [30, 60], [70, 90], [900, 1000]]
assert_equal (difference [100, 150, 900, 1000], [20, 30, 60, 70, 90, 110, 400, 500]), [[110, 150], [900, 1000]]
assert_equal (difference [100, 150, 900, 1000], [20, 30]), [[100, 150], [900, 1000]]
assert_equal (difference [100, 150, 900, 1000], [20, 100]), [[100, 150], [900, 1000]]
assert_equal (difference [100, 150, 900, 1000], [20, 1000]), []
assert_equal (difference [100, 150], [20, 100, 110, 200]), [[100, 110]]
assert_equal (difference [100, 150], [110, 140]), [[100, 110], [140, 150]]
assert_equal (difference [1, 1000], [200, 400]), [[1, 200], [400, 1000]]
assert_equal (difference [200, 400], [1, 1000]), []
assert_equal (difference [1, 1000], [10, 20, 50, 100, 200, 400]), [[1, 10], [20, 50], [100, 200], [400, 1000]]
assert_equal (difference [100, 200], [50, 150]), [[150, 200]]
assert_equal (difference [100, 200], [150, 250]), [[100, 150]]
assert_equal (difference [100, 200], [100, 200]), []
assert_equal (difference [100, 200, 300, 400], [100, 200, 300, 400]), []
assert_equal (difference [100, 200, 300, 400], [100, 200, 250, 450]), []
assert_equal (difference [100, 200, 300, 400], [200, 300]), [[100, 200], [300, 400]]
assert_equal (difference [100, 200, 300, 400], [1, 1000]), []
assert_equal (difference [], [1, 1000]), []
assert_equal (difference [1, 2, 3, 4, 5, 6], [1, 1000]), []
assert_equal (difference [1, 2, 3, 4, 5, 6], []), [[1, 2], [3, 4], [5, 6]]
assert_equal (difference [1, 2], []), [[1, 2]]
assert_equal (difference [1, 100, 200, 300, 400, 500], [50, 60]), [[1, 50], [60, 100], [200, 300], [400, 500]]
assert_equal (difference [1, 100, 200, 300, 400, 500], [400, 450]), [[1, 100], [200, 300], [450, 500]]
assert_equal compress([1, 2, 3, 7, 8, 9]), [[1, 3], [7, 9]]
assert_equal compress([1, 2, 7]), [[1, 2], [7, 7]]
assert_equal compress([1, 7, 7, 7]), [[1, 1], [7, 7]]
assert_equal compress([1, 3, 5, 7]), [[1, 1], [3, 3], [5, 5], [7, 7]]
assert_equal compress([1, 2, 3, 4]), [[1, 4]]
assert_equal compress([1]), [[1, 1]]
assert_equal compress([]), []
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment