Find the Intersection of 2 Sets in Unioned Interval Notation

Question

Find the Intersection of 2 Sets in Unioned Interval Notation

Given two sets of real numbers described as the union of intervals, output a description of the intersection of these two sets as a union of the same type of interval.

The input sets will always consist of unions of intervals such that each interval begins and ends at a different integer (i.e. no interval has measure zero). However, different intervals in the same set may begin or end at the same integer or overlap.

The output set must also be a union of intervals which begin and end at integers, but no interval in the output may overlap any other even at a single integer.

The input may take any form that is suitable for your language of choice, as long as it consists of two lists of pairs of integers.

For example, you may represent the set as:

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

Or as:

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

Or as:

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

Your output representation must be identical to your input representation (except that it is only one list of intervals instead of two).

Examples/Test cases:

Input:

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

Output:

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

In other words, we're intersecting the set that contains all real numbers between -90 and -4 and all real numbers between 4 and 90 with the set that contains all real numbers between -50 and 50. The intersection is the set containing all real numbers between -50 and -4 and all real numbers between 4 and 50. A more visual explanation:

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

---

Input:

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

Output:

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

---

Input:

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

Output:

[-8,0]

Invalid Output (even though it represents the same set):

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

Scoring:

This is code-golf so shortest source in bytes wins, as potentially modified by the following bonus.

Bonus:

-15% if you also support positive and negative infinity as bounds of intervals. You may choose what token(s) represent these numbers. (And yes, infinity is a number in the hyperreals ;P)

Answer 1

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

Answer 2

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

Answer 3

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.