Finden Sie den Schnittpunkt von 2 Sätzen in der Unioned Interval Notation

Wenn zwei Sätze von reellen Zahlen gegeben sind, die als Vereinigung von Intervallen beschrieben werden, geben Sie eine Beschreibung des Schnittpunkts dieser beiden Sätze als Vereinigung desselben Intervalltyps aus.

Die Eingabesätze bestehen immer aus Intervallverbindungen, sodass jedes Intervall mit einer anderen Ganzzahl beginnt und endet (dh kein Intervall hat das Maß Null). Unterschiedliche Intervalle in derselben Menge können jedoch mit derselben Ganzzahl oder Überlappung beginnen oder enden.

Der Ausgabesatz muss auch eine Vereinigung von Intervallen sein, die bei ganzen Zahlen beginnen und enden, aber selbst bei einer einzelnen ganzen Zahl darf sich kein Intervall in der Ausgabe mit einem anderen überschneiden .

Die Eingabe kann eine beliebige Form annehmen, die für die Sprache Ihrer Wahl geeignet ist, sofern sie aus zwei Listen von Ganzzahlpaaren besteht.

Beispielsweise können Sie die Menge wie folgt darstellen :

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

Oder als:

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

Oder als:

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

Ihre Ausgabedarstellung muss mit Ihrer Eingabedarstellung identisch sein (außer dass es sich nur um eine Liste von Intervallen anstelle von zwei handelt).

Beispiele / Testfälle:

Eingang:

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

Ausgabe:

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

Mit anderen Worten, wir schneiden die Menge, die alle reellen Zahlen zwischen -90 und -4 und alle reellen Zahlen zwischen 4 und 90 enthält, mit der Menge, die alle reellen Zahlen zwischen -50 und 50 enthält. Die Schnittmenge ist die Menge, die alle enthält reelle Zahlen zwischen -50 und -4 und alle reellen Zahlen zwischen 4 und 50. Eine visuellere Erklärung:

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

Eingang:

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

Ausgabe:

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

Eingang:

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

Ausgabe:

[-8,0]

Ungültige Ausgabe (obwohl sie dieselbe Menge darstellt):

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

Wertung:

Dies ist Code-Golf, so dass die kürzeste Quelle in Bytes gewinnt, was möglicherweise durch den folgenden Bonus geändert wird.

Bonus:

-15%, wenn Sie auch positive und negative Unendlichkeit als Intervallgrenzen unterstützen. Sie können auswählen, welche Token diese Zahlen darstellen. (Und ja, Unendlichkeit ist eine Zahl in den Hyperreals; P)

Mathematica, 41 Bytes - 15% = 34,85

Mathematica verfügt über eine integrierte Funktion für Intervallschnittpunkte.

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

Beispiel:

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

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

Haskell, 145 Bytes

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

Anwendungsbeispiel: [(-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)].

Wie es funktioniert:

                 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 

Ich setze die „halben“ -Werten x.5in der Liste, weil ich unterscheiden muß (1,2),(3,4)aus (1,4). Ohne x.5würden beide werden [1,2,3,4], aber mit x.5dem 1. wird [1,1.5,2,3,3.5,4](was fehlt 2.5) und dem zweiten [1,1.5,2,2.5,3,3.5,4].

Ruby, 90 Bytes

Ordnet jede der beiden Mengen einem flachen Array zu, ermittelt den Schnittpunkt dieser Arrays, schneidet das Ergebnis in fortlaufende Blöcke und ordnet jeden Block dem ersten und letzten Element zu. Kinderleicht.

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

Verwendungszweck:

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