Find the Intersection of 2 Sets in Unioned Interval Notation

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

• 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]]] – msh210 Dec 7 '15 at 5:57
• @msh210 the third example should answer this question. (No. Sort them yourself.) – quintopia Dec 7 '15 at 6:12
• @nimi you're right. fixed – quintopia Dec 9 '15 at 19:04

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

• Wow... I just came up with the exact same solution without reading this. +1 – LegionMammal978 Dec 7 '15 at 12:28
• Gotta love Mathematica's auto-unioning Interval. – mbomb007 Dec 9 '15 at 19:16

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

• The output should be identical to input. ...so just say that your input needs .0 after each integer also ;) – quintopia Dec 9 '15 at 19:32
• @quintopia: yes, thanks. – nimi Dec 9 '15 at 19:35

Ruby, 90 bytes

Maps each of the two sets to a flat array, gets the set intersection of those arrays, then slices the result into continuos chunks and maps each chunk into the first and last element. Easy peasy.

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


Usage:

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

• What does your program output for s = [[[1,2],[3,4]], [[1,2],[3,4]]]? (My ruby version doesn't have slice_when, so I cannot test myself) – nimi Dec 9 '15 at 20:54
• @mimi it gives [[1, 4]]. The slice_when method was added somewhere around Ruby 2.2 I think. – daniero Dec 9 '15 at 21:00
• ... but it should be [[1,2],[3,4]] – nimi Dec 9 '15 at 21:01
• The sets are over real numbers, only the interval boundaries are integers, so 2.2 is not in the input s = [[[1,2],[3,4]], [[1,2],[3,4]]], but in your output [[1, 4]]. – nimi Dec 9 '15 at 21:12
• Hmm, you're right. That could've been clearified/emphized a bit for the mathematically challenged such as myself.. – daniero Dec 9 '15 at 21:17