6
\$\begingroup\$

Given a range and a list thereof, while keeping the existing intervals in the list unchanged, split the additional range into sub-intervals and add them to the list, such that all the ranges in the final list are disjoint and contain all numbers present in the input ranges.

The goal is to create an insertInterval(intervals, newInterval) function which returns a new interval list if there are any changes.

Pre-condition: Interval range is sorted smallest to larger [[0, 1], [3, 5]].

Examples: Input and output:

assert.deepEqual(
  insertIntervalSec([[1,5],[10,15],[20,25]], [12,27]),
  [[1,5],[10,15],[15,20],[20,25],[25, 27]]
);

assert.deepEqual(
  insertIntervalSec([[1,5],[10,15],[20,25]], [-3,0]),
  [[-3,0],[1,5],[10,15],[20,25]]
);

assert.deepEqual(
  insertIntervalSec([[1,5],[10,15],[20,25]], [-3,3]),
  [[-3,1],[1,5],[10,15],[20,25]]
);

assert.deepEqual(
  insertIntervalSec([[0,5],[10,15],[20,25]], [15,15]),
  [[0,5],[10,15],[20,25]]
);
assert.deepEqual(
  insertIntervalSec([[0,5],[10,15],[20,25]], [20,21]),
  [[0,5],[10,15],[20,25]]
);
assert.deepEqual(
  insertIntervalSec([[0,5],[10,15],[20,25]], [26,27]),
  [[0,5],[10,15],[20,25],[26, 27]]
);
assert.deepEqual(
  insertIntervalSec([[0,5],[10,15],[20,25]], [25,27]),
  [[0,5],[10,15],[20,25],[25,27]]
);
assert.deepEqual(insertIntervalSec([], [25,27]), [[25,27]]);
assert.deepEqual(insertIntervalSec([[1,1]], [1,1]), [[1,1]]);
assert.deepEqual(insertIntervalSec([[1,1]], [1,3]), [[1, 1], [1, 3]]);
assert.deepEqual(insertIntervalSec([[2,2]], [1,3]), [[1, 2], [2, 2], [2, 3]]);

All programming languages are welcome.

\$\endgroup\$
  • \$\begingroup\$ Should the intervals in the old list be preserved and not concatenated together in the new list? \$\endgroup\$ – Erik the Outgolfer Jan 8 at 21:59
  • 1
    \$\begingroup\$ Intervals in the old list should remain as is, the new inserted ranges should have same end value as the next start value [[1, 2], [2, 5]] \$\endgroup\$ – jurka Jan 8 at 22:02
  • \$\begingroup\$ I'm a bit surprised nobody has mentioned The Sandbox where you can get feedback on your challenges before posting to main. I think this is a good challenge, as soon as I can figure out what it's asking. \$\endgroup\$ – Giuseppe Jan 10 at 21:36
  • \$\begingroup\$ Would it be possible to have a different explanation of the task? I don't understand what "Given a range and a list thereof" even means. A list of a range? What? :) \$\endgroup\$ – Steve Bennett Jan 16 at 3:47
4
\$\begingroup\$

Japt, 44 bytes

rò
íU c ò@Vc øX ©X¥YÃke@V®ròÃc øXîgJõ0ÃcV n

Try it online!

Reworked it, at the cost of 1 byte. Now handles the [[2,2]],[1,3] test case properly.

Explanation:

rò                                           #Turn the second input into a range
íU c                                         #Duplicate each item in that range
     ò@      ©X¥YÃ                           #Split in the middle of the duplicates that:
       Vc øX                                 # Appear in the first input
                  k                          #Remove the segments where:
                   e@       øXÃ              # Every item in the segment is in...
                     V®ròÃc                  # A range from the first input
                               ®    Ã        #For the remaining segments:
                                gJõ0         # Get the first and last items
                                     cV      #Add those pairs to the first input
                                        n    #Sort the whole thing

Worked Example:

Input: [[2,2],[5,7]],[1,8]

Second input as a range: [1,2,3,4,5,6,7,8]

Duplicate each item: [1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8]

Numbers that appear in the first input: [2,5,7]

After splitting: [[1,1,2],[2,3,3,4,4,5],[5,6,6,7],[7,8,8]]

Numbers within the first input's ranges: [2,5,6,7]

Segments using only those numbers:[[5,6,6,7]]

Remaining segments after those are removed: [[1,1,2],[2,3,3,4,4,5],[7,8,8]]

First and last item of each: [[1,2],[2,5],[7,8]]

Merge with the first input: [[1,2],[2,5],[7,8],[2,2],[5,7]]

Sort it: [[1,2],[2,2],[2,5],[5,7],[7,8]]

Which matches the actual output of the code

\$\endgroup\$
  • \$\begingroup\$ Nice answer, which is actually pretty similar to mine, so obvious +1 from me. I've also added the test cases [[1,1]], [3,3] and [[2,2]], [1,3] now (and fixed the code for [[1,1]], [3,3] since it was previously failing). \$\endgroup\$ – Kevin Cruijssen Jan 11 at 11:11
  • \$\begingroup\$ Nice answer, working with ranges can be tricky in Japt. I originally thought there was no way to improve on £[XÎXÌ]Ã, but it turns out you can do ®gJõ0Ã to save 2 bytes :-) \$\endgroup\$ – ETHproductions Jan 15 at 21:06
  • \$\begingroup\$ @ETHproductions Nice find, I always forget the other overloads of g \$\endgroup\$ – Kamil Drakari Jan 15 at 21:09
2
\$\begingroup\$

05AB1E, 34 33 30 bytes

ŸεI˜yåiðy)]˜#ʒI€Ÿ˜KgĀ}εнyθ‚}«ê

Created a port of @KamilDrakari's Japt answer, in order to fix the new test case [[2,2]], [1,3] (which golfed 4 bytes at the same time). So make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

Ÿ            # Get the ranged list of the first (implicit) input
             #  i.e. [1,8] → [1,2,3,4,5,6,7,8]
 ε           # Map each number `y` to:
  I˜yåi      #  If the second input flattened contains the current map-number:
             #    i.e. [[2,2],[5,7]] and `y`=2 → 1 (truthy)
       ðy    #   Push a space character, and value `y` again
         )   #   Wrap `y`, space, `y` into a list
 ]           # Close the if-statement and the map
             #  i.e. [1,2,3,4,5,6,7,8] and [[2,2],[5,7]]
             #   → [1,[2," ",2],3,4,[5," ",5],6,[7," ",7],8]
  ˜          # Flatten the list
             #  i.e. [1,[2," ",2],3,4,[5," ",5],6,[7," ",7],8]
             #   → [1,2," ",2,3,4,5," ",5,6,7," ",7,8]
   #         # Split the list on spaces
             #  i.e. [1,2," ",2,3,4,5," ",5,6,7," ",7,8] → [[1,2],[2,3,4,5],[5,6,7],[7,8]]
ʒ       }    # Filter this list of lists by:
 I€Ÿ         #  Push the second input, and create a range of each pair
             #   i.e. [[2,2],[5,7]] → [[2],[5,6,7]]
    ˜        #  Flatten this list of lists
             #   i.e. [[2],[5,6,7]] → [2,5,6,7]
     K       #  Remove these numbers from the current filter-list
             #   i.e. [2,3,4,5] and [2,5,6,7] → [3,4]
             #   i.e. [5,6,7] and [2,5,6,7] → []
      g      #  Take the length of this list
             #   i.e. [3,4] → 2
             #   i.e. [] → 0
       Ā     #  And truthify it (0 remains 0; everything else becomes 1)
             #   i.e. 2 → 1 (truthy)
             #   i.e. 0 → 0 (falsey)
             #  i.e. [[1,2],[2,3,4,5],[5,6,7],[7,8]] and [[2,2],[5,7]]
             #   → [[1,2],[2,3,4,5],[7,8]]
ε    }       # Map each inner list to:
 н           #  Take the first value
             #   i.e. [2,3,4,5] → 2
  yθ         #  And the last value
             #   i.e. [2,3,4,5] → 5
    ‚        #  And pair them together
             #   i.e. 2 and 5 → [2,5]
             #  i.e. [[1,2],[2,3,4,5],[7,8]] → [[1,2],[2,5],[7,8]]
«            # Merge this list of pairs with the second (implicit) input
             #  i.e. [[2,2],[5,7]] and [[1,2],[2,5],[7,8]]
             #   → [[2,2],[5,7],[1,2],[2,5],[7,8]]
 ê           # Sort the list of pairs, and remove any duplicated pairs at the same time
             #  i.e. [[2,2],[5,7],[1,2],[2,5],[7,8]]
             #   → [[1,2],[2,2],[2,5],[5,7],[7,8]]
             # (and output the result implicitly)
\$\endgroup\$
1
\$\begingroup\$

Python 2, 119 118 116 bytes

lambda l,A,B:sum([[[max(A,b),min(c[0],B)],c][max(A,b)>=min(c[0],B):]for(a,b),c in zip([[A,A]]+l,l+[[B,B]])],[])[:-1]

Try it online!


If I/O can be flat lists (of even length):

Python 2, 112 bytes

lambda l,A,B:sum([[a]+[max(A,a),min(B,b)]*(max(A,a)<min(B,b))+[b]for a,b in zip(*[iter([A]+l+[B])]*2)],[])[1:-1]

Try it online!


Python 3, 111 bytes

lambda l,A,B:sum([[a]+[max(A,a),min(B,b)]*(max(A,a)<min(B,b))+[b]for a,b in zip(*[iter([A,*l,B])]*2)],[])[1:-1]

Try it online!

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.