Найти пересечение 2 множеств в объединенной нотации

10

Найти пересечение 2 множеств в объединенной нотации

Учитывая два набора действительных чисел, описанных как объединение интервалов, выведите описание пересечения этих двух наборов как объединение интервалов одного типа.

Входные наборы всегда будут состоять из объединений интервалов, так что каждый интервал начинается и заканчивается с другим целым числом (т. Е. Ни один интервал не имеет меры ноль). Однако разные интервалы в одном и том же наборе могут начинаться или заканчиваться в одном и том же целом числе или совпадать.

Выходной набор также должен представлять собой объединение интервалов, которые начинаются и заканчиваются на целые числа, но ни один интервал в выходных данных не может перекрывать любые другие, даже в одном целом числе.

Ввод может принимать любую форму, которая подходит для вашего языка по вашему выбору, если он состоит из двух списков пар целых чисел.

Например, вы можете представить набор уравнениекак:

[-10,-4]u[1,5]u[19,20]

Или как:

[[-10,-4],[1,5],[19,20]]

Или как:

[-10,-4;1,5;19,20]

Ваше выходное представление должно быть идентично вашему входному представлению (за исключением того, что это только один список интервалов вместо двух).

Примеры / Тестовые случаи:

Входные данные:

[[[-90,-4],[4,90]],[[-50,50]]]

Вывод:

[[-50,-4],[4,50]]

Другими словами, мы пересекаем множество, которое содержит все действительные числа от -90 до -4 и все действительные числа от 4 до 90 с множеством, которое содержит все действительные числа от -50 до 50. Пересечение - это множество, содержащее все действительные числа от -50 до -4 и все действительные числа от 4 до 50. Более наглядное объяснение:

-90~~~~~-4  4~~~~~90   intersected with
    -50~~~~~~~~50        yields:
    -50~-4  4~~50

Входные данные:

"[-2,0]u[2,4]u[6,8]
[-1,1]u[3,5]u[5,9]"

Вывод:

"[-1,0]u[3,4]u[6,8]"

Входные данные:

[-9,-8;-8,0;-7,-6;-5,-4]
[-7,-5;-1,0;-8,-1]

Вывод:

[-8,0]

Неверный вывод (даже если он представляет один и тот же набор):

[-8,0;-7,-5;-5,0]

Подсчет очков:

Это поэтому выигрывает самый короткий источник в байтах, который может быть изменен следующим бонусом.

Бонус:

-15%, если вы также поддерживаете положительную и отрицательную бесконечность в качестве границ интервалов. Вы можете выбрать, какие токены представляют эти числа. (И да, бесконечность - это число в гиперреалах; P)

quintopia
источник
Можем ли мы предположить, что различные объединенные множества в каждом слагаемом пересечения записываются в порядке возрастания? Другими словами (но наоборот), допустим ли следующий ввод? [[[4,90],[-90,-4]],[[-50,50]]]
msh210
2
@ msh210 третий пример должен ответить на этот вопрос. (Нет. Сортируйте их сами.)
Quintopia
@nimi ты прав. исправлено
Quintopia

Ответы:

3

Mathematica, 41 байт - 15% = 34,85

Mathematica имеет встроенную функцию для пересечения интервалов.

List@@IntervalIntersection@@Interval@@@#&

Пример:

In[1]:= List@@IntervalIntersection@@Interval@@@#&[{{{-90, -4}, {4, Infinity}}, {{-50,Infinity}}}]

Out[1]= {{-50, -4}, {4, Infinity}}
alephalpha
источник
2
Вау ... Я просто придумал точно такое же решение, не читая этого. +1
LegionMammal978
Должен любить авто-объединение Mathematica Interval.
mbomb007
3

Haskell, 145 байт

import Data.List
q(a,b)=[a,a+0.5..b]
p@(a,b)%(h:t)|h==b+0.5=(a,h)%t|1<2=p:(h,h)%t
p%_=[p]
a#b|h:t<-nub$sort$intersect(q=<<a)$q=<<b=(h,h)%t|1<2=[]

Пример использования: [(-2.0,0.0),(2.0,4.0),(5.0,6.0),(6.0,8.0)] # [(-1.0,1.0),(3.0,5.0),(5.0,9.0)]-> [(-1.0,0.0),(3.0,4.0),(5.0,8.0)].

Как это работает:

                 q=<<a            -- turn each pair in the 1st input list into
                                  -- lists with halves in between (e.g. (1,4) ->
                                  -- [1,1.5,2,2.5,3,3.5,4]) and concatenate them
                                  -- to a single list
                      q=<<b       -- same for the second input list
    nub$sort$intersect            -- sort the intersection of those lists
                                  -- and remove duplicates
h:t<-                             -- call the first element h and the rest t
                       (h,h)%t    -- start rebuilding the intervals
                          |1<2=[] -- if there's no first element h, one of the
                                  -- input lists is empty, so the output is also
                                  -- empty


p@(a,b)%(h:t)                     -- an interval p = (a,b), build from a list (h:t)
             =(a,h)%t             -- becomes (a,h)
      |h==b+1                     --   if h equals b+0.5
                    p:(h,h)%t     -- or is put in the output list, followed by
                                  --       a new interval starting with (h,h)
      |1<2                        --   otherwise
p%_=[p]                           -- base case of the interval rebuilding function 

Я ставлю «половинку» -значение x.5в списке, потому что мне нужно отличать (1,2),(3,4)от (1,4). Внешне x.5оба стали бы [1,2,3,4], но с x.5первым становится [1,1.5,2,3,3.5,4](чего не хватает 2.5) и вторым [1,1.5,2,2.5,3,3.5,4].

Ними
источник
Вывод должен быть идентичным вводу. ... так что просто скажите, что ваш ввод требует .0 после каждого целого числа;)
quintopia
@quintopia: да, спасибо.
Nimi
2

Рубин, 90 байт

Сопоставляет каждый из двух наборов с плоским массивом, получает пересечение наборов этих массивов, затем разбивает результат на непрерывные куски и отображает каждый кусочек в первый и последний элемент. Очень просто.

->s{a,b=s.map{|y|y.flat_map{|f,l|[*f..l]}.sort}
(a&b).slice_when{|a,b|b-a>1}.map &:minmax}

Применение:

f=->s{a,b=s.map{|y|y.flat_map{|f,l|[*f..l]}.sort}
(a&b).slice_when{|a,b|b-a>1}.map &:minmax}

s = [[[-90,-4],[4,90]], [[-50,50]]]
p f[s] # => [[-50, -4], [4, 50]]

s = [[[-2,0],[2,4],[6,8]], [[-1,1],[3,5],[5,9]]]
p f[s] # => [[-1, 0], [3, 4], [6, 8]]

s = [[[-9,-8],[-8,0],[-7,-6],[-5,-4]],[[-7,-5],[-1,0],[-8,-1]]]
p f[s] # => [[-8, 0]]
daniero
источник
Для чего выводится ваша программа s = [[[1,2],[3,4]], [[1,2],[3,4]]]? (У моей рубиновой версии нет slice_when, поэтому я не могу проверить себя)
nimi
@ Мими это дает [[1, 4]]. slice_whenМетод был добавлен где - то около 2,2 Рубина я думаю.
Даниеро
... но это должно быть [[1,2], [3,4]]
Ним
Наборы находятся над действительными числами, только границы интервалов являются целыми числами, поэтому 2.2не на входе s = [[[1,2],[3,4]], [[1,2],[3,4]]], а на выходе [[1, 4]].
Ними
Хм, ты прав. Это могло бы быть немного прояснено / подчеркнуто для таких математически оспариваемых, как я ...
Даниеро