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 equation 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)

• msh210: Can we assume the various unioned sets in each intersection summand are written in increasing order? In other words (but conversely), is the following input valid? [[[4,90],[-90,-4]],[[-50,50]]]
• quintopia: @msh210 the third example should answer this question. (No. Sort them yourself.)
• quintopia: @nimi you're right. fixed

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

• LegionMammal978: Wow... I just came up with the exact same solution without reading this. +1
• mbomb007: Gotta love Mathematica's auto-unioning Interval.

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

• quintopia: The output should be identical to input. ...so just say that your input needs .0 after each integer also ;)

Answer 3

APL (Dyalog Extended), 37 bytes

×ばつ(⊢/,⊃) ̈{⍵⊂⍨1,1<2-/⍵}⊃∩/∨⍤∊ ̈.../ ̈ ×ばつ⎕

Try it online!

A full program which takes a nested array in STDIN and returns a nested array.

Code fixed by bubbler.

• quintopia: Judging by the TIO, this doesn't satisfy "Your output representation must be identical to your input representation"
• Razetime: The input is an APL nested array, parsed from JSON because I am too lazy to rewrite them.
• Bubbler: I think it is incorrect. Try [[[1,4],[5,8]],[[2,6]]]. Expected output is [[2,4],[5,6]] but yours give [[2,6]]. See for example nimi's answer for a way to handle it correctly.