Znajdź punkt przecięcia 2 zestawów w notacji Unioned Interval

Biorąc pod uwagę dwa zestawy liczb rzeczywistych opisanych jako suma przedziałów, wypisz opis przecięcia tych dwóch zbiorów jako sumę tego samego rodzaju przedziału.

Zestawy wejściowe zawsze będą się składały ze związków przedziałów, tak że każdy przedział zaczyna się i kończy na innej liczbie całkowitej (tzn. Żaden przedział nie ma miary zero). Jednak różne interwały w tym samym zestawie mogą rozpoczynać się lub kończyć przy tej samej liczbie całkowitej lub nakładać się.

Zbiór wyjściowy musi być również sumą przedziałów, które zaczynają się i kończą na liczbach całkowitych, ale żaden interwał na wyjściu nie może nakładać się na siebie, nawet na jednej liczbie całkowitej.

Dane wejściowe mogą mieć dowolną formę odpowiednią dla wybranego języka, pod warunkiem, że składają się z dwóch list par liczb całkowitych.

Na przykład możesz reprezentować zestaw jako:

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

Lub jako:

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

Lub jako:

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

Reprezentacja wyjściowa musi być identyczna z reprezentacją wejściową (z tym wyjątkiem, że jest to tylko jedna lista przedziałów zamiast dwóch).

Przykłady / przypadki testowe:

Wejście:

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

Wynik:

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

Innymi słowy, przecinamy zbiór zawierający wszystkie liczby rzeczywiste od -90 do -4 i wszystkie liczby rzeczywiste od 4 do 90 z zestawem, który zawiera wszystkie liczby rzeczywiste od -50 do 50. Przecięcie jest zbiorem zawierającym wszystkie liczby rzeczywiste od -50 do -4 i wszystkie liczby rzeczywiste od 4 do 50. Bardziej wizualne wyjaśnienie:

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

Wejście:

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

Wynik:

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

Wejście:

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

Wynik:

[-8,0]

Nieprawidłowy wynik (mimo że reprezentuje ten sam zestaw):

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

Punktacja:

To jest golf golfowy, więc wygrywa najkrótsze źródło w bajtach, potencjalnie zmodyfikowane przez następujący bonus.

Premia:

-15%, jeśli popierasz również dodatnią i ujemną nieskończoność jako granice przedziałów. Możesz wybrać, które tokeny reprezentują te liczby. (I tak, nieskończoność jest liczbą w hiperreałach; P)

Mathematica, 41 bajtów - 15% = 34,85

Mathematica ma wbudowaną funkcję przecinania interwałów.

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

Przykład:

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

Out[1]= {{-50, -4}, {4, Infinity}}

Haskell, 145 bajtów

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=[]

Przykład użycia: [(-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)].

Jak to działa:

                 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 

Kładę się „pół” -values x.5na liście, bo trzeba odróżnić (1,2),(3,4)od (1,4). Bez nich x.5oba staną się [1,2,3,4], ale z x.5pierwszym stanie się [1,1.5,2,3,3.5,4](którego brakuje 2.5) i drugim [1,1.5,2,2.5,3,3.5,4].

Rubinowy, 90 bajtów

Odwzorowuje każdy z dwóch zestawów na płaską tablicę, pobiera zestaw przecięcia tych tablic, a następnie kroi wynik na ciągłe fragmenty i odwzorowuje każdy fragment na pierwszy i ostatni element. Bułka z masłem.

->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}

Stosowanie:

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]]