Find the Intersection of 2 Sets in Unioned Interval Notation
Mathematica, 41 bytes - 15% = 34.85
Mathematica has a built-in function for interval intersection.
List@@IntervalIntersection@@Interval@@@#&
Example:
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=[]
Usage example: [(-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)]
.
How it works:
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
I'm putting the "half"-values x.5
in the list, because I need to distinguish (1,2),(3,4)
from (1,4)
. Without x.5
, both would become [1,2,3,4]
, but with x.5
the 1st becomes [1,1.5,2,3,3.5,4]
(which lacks 2.5
) and the second [1,1.5,2,2.5,3,3.5,4]
.
APL (Dyalog Extended), 37 bytes
.5×(⊢/,⊃)¨{⍵⊂⍨1,1<2-/⍵}⊃∩/∨⍤∊¨…/¨¨2×⎕
Try it online!
A full program which takes a nested array in STDIN and returns a nested array.
Code fixed by bubbler.