JavaScript: subtracting ranges of numbers

Question

I'm trying to write a JS function that has two parameters: include and exclude, each of which is an array of objects {X, Y}, which represents a range of numbers from X to Y, both are included.

The conclusion is the subtraction of all ranges in include with all ranges in exclude.

For instance:

include = [ {1,7}, {9,10}, {12,14} ] exclude = [ {4,5}, {11,20} ] output = [ {1,3}, {6,7}, {9,10} ] 

• {4,5} broke {1,7} into two objects of the range: {1,3} and {6,7}
• {9,10} was not affected
• {12.14} completely removed

Answer 1

You can use the sweep algorithm. For each number, save what it represents (start and end, inclusion and exclusion). Then put the whole number in an array and sort it. Then iteratively remove the elements from the array and perform the corresponding operation.

 include_list = [[1,7]] exclude_list = [[4,5]] (1,start,inclusion),(4,start,exclusion),(5,end,exclusion),(7,end,inclusion) include = 0 exclude = 0 cur_element = (1,start,inclusion) -> include = 1, has_open_range = 1, range_start = 1 // we start a new range starting at 1 cur_element = (4,start,exclusion) -> exclude = 1, has_open_range = 0, result.append ( [1,4] ) // we close the open range and add range to result cur_element = (5,end,exclusion) -> exclude = 0, has_open_range = 1, range_start = 5 // because include was 1 and exclude become 0 we must create a new range starting at 5 cur_element = (7,end,inclusion) -> include = 0, has_open_range = 0, result.append([5,7]) // include became zero so we must close the current open range so we add [5,7] to result 

support include and exclude variables to increase them with the beginning of the corresponding elements and reduce them when receiving the finite elements. According to the value of include and exclude you can determine that you should start a new range, close the open range, or do nothing.

This algorithm works in linear time O (n).

Answer 2

NOTE: include = [ {1,7}, {9,10}, {12,14} ] invalid javascript, so I assumed that you are passing arrays of arrays, namely:

  include = [ [1,7], [9,10], [12,14] ] 

Brute force method (the solution may not be the most eloquent):

 function solve_range(include, exclude) { numbers = []; include.forEach(function (range) { for (i = range[0]; i <= range[1]; i++) { numbers[i] = true; } }); exclude.forEach(function (range) { for (i = range[0]; i <= range[1]; i++) { numbers[i] = false; } }); contiguous_start = null; results = []; for (i = 0; i < numbers.length; i++) { if (numbers[i] === true) { if (contiguous_start == null) { contiguous_start = i; } } else { if (contiguous_start !== null) { results[results.length] = [contiguous_start, i - 1]; } contiguous_start = null; } } return results; } var include = [ [1, 7], [9, 10], [12, 14] ]; var exclude = [ [4, 5], [11, 20] ]; var output = solve_range(include, exclude); 

https://jsfiddle.net/dwyk631d/2/

Answer 3

The rule for integer arithmetic to subtract two sets of X,Y is

 X − Y := {x − y | x ∈ X, y ∈ Y } 

but that’s not what you want as it seems.

You can take ordered sets in your example, which allows you to set any occurrence of x==y as an arbitrary value in a JavaScript array and use it to separate it. But you do not need it.

The set difference {1...7}\{4...5} expands to {1,2,3,4,5,6,7}\{4,5} . As you can easily see, subtraction with the rule of the given arithmetic would leave {1,2,3,0,0,6,7} and with normal subtraction ( \ character) you would get {1,2,3,6,7} .

The established difference {12...14}\{11...20} expands to {12,13,14}\{11,12,13,14,15,16,17,18,19,20} ; given arithm. the difference is {-11,0,0,0, -15, -16, ..., - 20}, but normal addition-subtraction leaves the empty set {} .

Processing operations with an empty set is equivalent to the usual arithmetic {x}-{}={x} and {}-{x} = {-x} for arithmetic rules and {x}\{}={x} , {}\{x}= {} with the usual rules

So, what you should use here, according to your example, are normal typing rules. There is no need to expand the sets; they can be considered dense.

You can use relative differences (you can call them distances).

At {1...7}\{4...5} first start is small, then the second start and the first end are larger than the second end, which led to two different sets.

At {12...14}\{11...20} first start is larger than the second start, and the first end is lower than the second, which led to an empty set.

The third example uses an empty set rule.

Do you need an example fragment?

Answer 4

Here's an answer that works with fractions, and it's not just crude forcing. I added comments to explain how this works. This may seem great, the premise is simple:

• create a method p1_excluding_p2 that takes points p1 and p2 and returns an array of points that exist after executing p1 - p2

• create the points_excluding_p2 method that performs the EXACT same operation as above, but this time allows us to pass an array of points and return an array of points that exist after subtracting p2 from all the points in our array, so now we have (points) - p2

• create a p1_excluding_all method that accepts the opposite input as above. This time, take one p1 point and many exception points and return an array of points left after subtracting all the exception points. It is actually very easy to create now. We simply start with [p1] and the first exclusion point ( exclusion1 ) and pass it to points_excluding_p2 . We take the array that is returned (which will be p1 - exclusion1 ) and pass it to points_excluding_p2 only this time with exclusion2 . We continue this process until we exclude every exclusion point, and we are left with an array of p1 - (all exclusion points)

• Now that we have the opportunity to execute p1 - (all exclusion points) , it’s just a matter of cyclizing all our points and calling p1_excluding_all , and we are left with an array of each point, subtracting each exception point. We run our results with remove_duplicates if we have any duplicate entries, and what about it.

Code:

 var include = [ [1,7], [9,10], [12,14] ] var exclude = [ [4,5], [11,20] ] /* This method is just a small helper method that takes an array * and returns a new array with duplicates removed */ function remove_duplicates(arr) { var lookup = {}; var results = []; for(var i = 0; i < arr.length; i++) { var el = arr[i]; var key = el.toString(); if(lookup[key]) continue; lookup[key] = 1; results.push(el); } return results; } /* This method takes 2 points p1 and p2 and returns an array of * points with the range of p2 removed, ie p1 = [1,7] * p2 = [4,5] returned = [[1,3],[6,7]] */ function p1_excluding_p2(p1, p2) { if(p1[1] < p2[0]) return [p1]; // line p1 finishes before the exclusion line p2 if(p1[0] > p2[1]) return [p1]; // line p1 starts after exclusion line p1 var lines = []; // calculate p1 before p2 starts var line1 = [ p1[0], Math.min(p1[1], p2[0]-1) ]; if(line1[0] < line1[1]) lines.push(line1); // calculate p1 after p2 ends var line2 = [ p2[1]+1, p1[1] ]; if(line2[0] < line2[1]) lines.push(line2); // these contain the lines we calculated above return lines; } /* this performs the exact same operation as above, only it allows you to pass * multiple points (but still just 1 exclusion point) and returns results * in an identical format as above, ie points = [[1,7],[0,1]] * p2 = [4,5] returned = [[0,1],[1,3],[6,7]] */ function points_excluding_p2(points, p2) { var results = []; for(var i = 0; i < points.length; i++) { var lines = p1_excluding_p2(points[i], p2); results.push.apply(results, lines); // append the array lines to the array results } return results; } /* this method performs the same operation only this time it takes one point * and multiple exclusion points and returns an array of the results. * this is the important method of: given 1 point and many * exclusion points, return the remaining new ranges */ function p1_excluding_all(p1, excluded_pts) { var checking = [p1]; var points_leftover = []; for(var i = 0; i < exclude.length; i++) { checking = points_excluding_p2(checking, exclude[i]); } return remove_duplicates(checking); } /* now that we have a method that we can feed a point and an array of exclusion * points, its just a simple matter of throwing all our points into this * method, then at the end remove duplicate results for good measure */ var results = []; for(var i = 0; i < include.length; i++) { var lines = p1_excluding_all(include[i], exclude); results.push.apply(results, lines); // append the array lines to the array results } results = remove_duplicates(results); console.log(results); 

which returns:

 [[1,3],[6,7],[9,10]] 

Answer 5

Here's a working solution that handles 4 possible overlap scenarios for an exclusion range.

 var include = [{from:1, to: 7},{from: 9, to: 10},{from: 12, to: 14}]; var exclude = [{from:4, to: 5}, {from: 11, to: 20}]; //result: {1,3}, {6,7}, {9,10} var resultList = []; for (var i=0;i<include.length;i++){ var inc = include[i]; var overlap = false; for (var x=0;x<exclude.length;x++ ){ var exc = exclude[x]; //4 scenarios to handle if (exc.from >= inc.from && exc.to <= inc.to){ //include swallows exclude - break in two resultList.push({from: inc.from, to: exc.from - 1}); resultList.push({from: exc.to + 1, to: inc.to}); overlap = true; }else if (exc.from <= inc.from && exc.to >= inc.to){ //exclude swallows include - exclude entire range overlap = true; break; }else if (exc.from <= inc.from && exc.to <= inc.to && exc.to >= inc.from){ //exclusion overlaps on left resultList.push({from: exc.to, to: inc.to}); overlap = true; }else if (exc.from >= inc.from && exc.to >= inc.to && exc.from <= inc.to){ //exclusion overlaps on right resultList.push({from: inc.from, to: exc.from - 1}); overlap = true; } } if (!overlap){ //no exclusion ranges touch the inclusion range resultList.push(inc); } } console.log(resultList); 

Answer 6

Perhaps we can make it somewhat more efficient by combining the marked intervals into one sorted list:

 include = [ {1,7}, {9,10}, {12,14} ] exclude = [ {4,5}, {11,20} ] merged = [ [1,7,0], [4,5,1], [9,10,0], [11,20,1], [12,14,0] ]; 

Then, moving the list and for any excluded interval, update any surrounding gaps.