Skip to content

Instantly share code, notes, and snippets.

@LeoShi
Last active August 29, 2015 13:58
Show Gist options
  • Save LeoShi/10001899 to your computer and use it in GitHub Desktop.
Save LeoShi/10001899 to your computer and use it in GitHub Desktop.
Write a program to do addition of intervals to an interval store
class IntervalStore(object):
def __init__(self):
self.store = []
def filter_result(self, flatten_store, low_index, upp_index):
useless_values = filter(lambda value: low_index < flatten_store.index(value) < upp_index, flatten_store)
flatten_store = filter(lambda value: value not in useless_values, flatten_store)
self.store = []
for i, k in zip(flatten_store[0::2], flatten_store[1::2]):
self.store.append([i, k])
def add(self, low, upp):
flatten_store = [number for pair in self.store for number in pair]
low_index, upp_index = self.index_of(low, flatten_store), self.index_of(upp, flatten_store)
if low_index >= 0 and upp_index >= 0:
if low_index % 2 != 0:
low_index -= 1
if upp_index % 2 == 0:
upp_index += 1
elif low_index >= 0 > upp_index:
if low_index % 2 != 0:
low_index -= 1
flatten_store.append(upp)
flatten_store = sorted(flatten_store)
upp_index = self.index_of(upp, flatten_store)
if upp_index % 2 != 0:
upp_index += 1
elif low_index < 0 <= upp_index:
if upp_index % 2 == 0:
upp_index += 1
flatten_store.append(low)
flatten_store = sorted(flatten_store)
low_index = self.index_of(low, flatten_store)
if low_index % 2 != 0:
low_index -= 1
upp_index += 1
else:
flatten_store.append(low)
flatten_store.append(upp)
flatten_store = sorted(flatten_store)
low_index, upp_index = self.index_of(low, flatten_store), self.index_of(upp, flatten_store)
if low_index % 2 != 0:
low_index -= 1
if upp_index % 2 == 0:
upp_index += 1
self.filter_result(flatten_store, low_index, upp_index)
def index_of(self, value, list):
try:
return list.index(value)
except ValueError:
return -1
class IntervalStore
def initialize
@store = []
end
def to_s
"[#{@store.map{ |i| "[#{i.first}, #{i.last}]" }.join(', ')}]"
end
# TODO - implement this method
def add(low, upp)
flatten_store = @store.flatten
low_index, upp_index = flatten_store.index(low), flatten_store.index(upp)
if low_index and upp_index
low_index -=1 if low_index.odd?
upp_index +=1 if upp_index.even?
elsif low_index and !upp_index
low_index -= 1 if low_index.odd?
(flatten_store << upp).sort!
upp_index = flatten_store.index(upp)
upp_index += 1 if upp_index.odd?
elsif !low_index and upp_index
upp_index += 1 if upp_index.even?
(flatten_store << low).sort!
low_index = flatten_store.index(low)
low_index -= 1 if low_index.odd?
upp_index += 1
else
(flatten_store << low << upp).sort!
low_index, upp_index = flatten_store.index(low), flatten_store.index(upp)
low_index -= 1 if low_index.odd?
upp_index += 1 if upp_index.even?
end
filter_result = filter_store(flatten_store, low_index, upp_index)
format_result(filter_result)
end
def format_result(rest)
@store = []
rest.each_slice(2) { |pair_values| @store << pair_values }
@store
end
def filter_store(flatten_store, low_index, upp_index)
flatten_store.clone.delete_if do |value|
flatten_store_index = flatten_store.index(value)
low_index < flatten_store_index and flatten_store_index < upp_index
end
end
end
from unittest import TestCase, main
from interval_store import IntervalStore
class TestIntervalStore(TestCase):
def test_should_not_merge_if_no_intersection(self):
store = IntervalStore()
store.add(1, 2)
store.add(5, 6)
self.assertEqual([[1, 2], [5, 6]], store.store)
def test_should_merge_if_two_number_both_appearance(self):
store = IntervalStore()
store.add(1, 2)
store.add(5, 6)
store.add(7, 8)
store.add(5, 7)
self.assertEqual([[1, 2], [5, 8]], store.store)
def test_should_merge_if_only_low_number_appearance_and_upp_number_is_not_between_any_exist_interval(self):
store = IntervalStore()
store.add(1, 2)
store.add(5, 6)
store.add(1, 4)
self.assertEqual([[1, 4], [5, 6]], store.store)
def test_should_merge_if_only_low_number_appearance_and_upp_number_is_between_any_exist_interval(self):
store = IntervalStore()
store.add(1, 2)
store.add(5, 6)
store.add(1, 4)
store.add(1, 2)
self.assertEqual([[1, 4], [5, 6]], store.store)
def test_should_merge_if_only_upp_number_appearance_and_low_number_is_not_between_any_exist_interval(self):
store = IntervalStore()
store.add(1, 2)
store.add(5, 6)
store.add(1, 4)
store.add(0, 5)
self.assertEqual([[0, 6]], store.store)
def test_should_merge_if_only_upp_number_appearance_and_low_number_is_between_any_exist_interval(self):
store = IntervalStore()
store.add(1, 2)
store.add(5, 6)
store.add(1, 4)
store.add(3, 5)
self.assertEqual([[1, 6]], store.store)
def test_should_merge_if_neither_upp_number_nor_low_number_is_appearance(self):
store = IntervalStore()
store.add(1, 2)
store.add(5, 6)
store.add(1, 4)
store.add(1, 2)
store.add(3, 5)
store.add(0, 7)
self.assertEqual([[0, 7]], store.store)
if __name__ == '__main__':
main()
#ruby-2.0.0-p247
require_relative 'interval_store'
require "test/unit"
# > store = IntervalStore.new
# []
# > store.add(1, 2)
# [[1, 2]]
# > store.add(5, 6)
# [[1, 2], [5, 6]]
# > store.add(1, 4)
# [[1, 4], [5, 6]]
# > store.add(1, 2)
# [[1, 4], [5, 6]]
# > store.add(3, 5)
# [[1, 6]]
# > store.add(0, 7)
# [[0, 7]]
##
class TestIntervalStore < Test::Unit::TestCase
def test_should_not_merge_if_no_intersection
store = IntervalStore.new
store.add(1, 2)
store.add(5, 6)
assert_equal([[1, 2], [5, 6]].to_s, store.to_s)
end
def test_should_merge_if_two_number_both_appearance
store = IntervalStore.new
store.add(1, 2)
store.add(5, 6)
store.add(7, 8)
store.add(5, 7)
assert_equal([[1, 2], [5, 8]].to_s, store.to_s)
end
def test_should_merge_if_only_low_number_appearance_and_upp_number_is_not_between_any_exist_interval
store = IntervalStore.new
store.add(1, 2)
store.add(5, 6)
store.add(1, 4)
assert_equal([[1, 4], [5, 6]].to_s, store.to_s)
end
def test_should_merge_if_only_low_number_appearance_and_upp_number_is_between_any_exist_interval
store = IntervalStore.new
store.add(1, 2)
store.add(5, 6)
store.add(1, 4)
store.add(1, 2)
assert_equal([[1, 4], [5, 6]].to_s, store.to_s)
end
def test_should_merge_if_only_upp_number_appearance_and_low_number_is_not_between_any_exist_interval
store = IntervalStore.new
store.add(1, 2)
store.add(5, 6)
store.add(1, 4)
store.add(0, 5)
assert_equal([[0, 6]].to_s, store.to_s)
end
def test_should_merge_if_only_upp_number_appearance_and_low_number_is_between_any_exist_interval
store = IntervalStore.new
store.add(1, 2)
store.add(5, 6)
store.add(1, 4)
store.add(3, 5)
assert_equal([[1, 6]].to_s, store.to_s)
end
def test_should_merge_if_neither_upp_number_nor_low_number_is_appearance
store = IntervalStore.new
store.add(1, 2)
store.add(5, 6)
store.add(1, 4)
store.add(1, 2)
store.add(3, 5)
store.add(0, 7)
assert_equal([[0, 7]].to_s, store.to_s)
end
end
class IntervalStore
def initialize
@store = []
end
def to_s
"[#{@store.map{ |i| "[#{i.first}, #{i.last}]" }.join(', ')}]"
end
# TODO - implement this method
def add(low, upp)
@store << [low, upp]
@store.sort_by!(&:first)
result = []
@store.each do |interval|
if result.empty?
result << interval
else
last_interval = result.pop
if last_interval.last < interval.first
result << last_interval << interval
else
min_value, max_value = [last_interval.first, interval.first, last_interval.last, interval.last].minmax
result << [min_value, max_value]
end
end
end
@store = result
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment