Interpret Interval Notation

Question

Interval notation is a way to write complicated range bounds more conveniently and concisely than writing an inequality. The challenge, should you choose to accept it, is to write a program or function that interprets a subset of interval notation. In this subset, intervals are a comma-separated pair of integers delimited by either brackets, parentheses, or both.

The range starts from the first integer ends at the second integer, inclusive if delimited by a bracket or exclusive if by parentheses. Multiple ranges, delimited by U, may be chained together, in which case duplicate elements are removed.

Input is a string in interval notation and output is a list of numbers contained in the specified interval. Only meaningful intervals are valid, so ranges may overlap, but the start will always be less than the end. Zero sized intervals should have an empty output. All integers in the interval must be displayed once and only once, but may be outputted in any particular order.

This is code-golf so the lowest byte count wins.

Other Details

• Invalid inputs are undefined behavior
• a ∪ or ⋃ symbol may be used instead of U
• The U will always be between ranges, never in front or behind
• If your language uses a character other than - to represent negative numbers that may be used instead

Test Cases

[0,5] -> [0,1,2,3,4,5]
(0,5] -> [1,2,3,4,5]
[0,5) -> [0,1,2,3,4]
(0,5) -> [1,2,3,4]
[9,13] -> [9,10,11,12,13]
[-5,-1] -> [-5,-4,-3,-2,-1]
[-5,-1) -> [-5,-4,-3,-2]
(-5,-1] -> [-4,-3,-2,-1]
(-5,-1) -> [-4,-3,-2]
[-3,2] -> [-3,-2,-1,0,1,2]
[-3,2) -> [-3,-2,-1,0,1]
(-3,2] -> [-2,-1,0,1,2]
(-3,2) -> [-2,-1,0,1]
[0,0] -> [0]
(0,0] -> []
[0,0) -> []
(0,0) -> []
[1,2) -> [1]
(1,2) -> []
[-3,0)U(0,3] -> [-3,-2,-1,1,2,3]
[-3,0)U[0,3] -> [-3,-2,-1,0,1,2,3]
[-3,0]U[0,3] -> [-3,-2,-1,0,1,2,3]
[-3,0]U[2,5] -> [-3,-2,-1,0,2,3,4,5]
[1,5]U[2,4] -> [1,2,3,4,5]
[-5,-1]U[-6,-2] -> [-5,-4,-3,-2,-1,-6]
[-5,-1]U[-6,0] -> [-6,-5,-4,-3,-2,-1,0]
[-5,-1]U[-6,-2]U[-7,0] -> [-7,-6,-5,-4,-3,-2,-1,0]
[1,2)U[2,3)U[3,4)U[4,5) -> [1,2,3,4]
[2,1) -> Undefined
U(5,10) -> Undefined
[13,18)U -> Undefined

Answer 1

Python 3, 79 bytes

lambda s:eval('{*range%s}'%s.translate({91:40,40:'(1+',93:'+1)',85:',*range'}))

Try it online!

-6 bytes thanks to ovs
-3 bytes thanks to dingledooper

Answer 2

C++ (gcc), 139 138 134 104 101 100 bytes

Uses C++20 features which aren't enabled by default in GCC, but are standard.

int f(auto&s,auto&o){int x,y;for(char c,d;s>>c>>x>>d>>y>>d;s>>d)for(y-=d<42;y>x-c%2;o.insert(y--));}

Try it online!

Uses streams because I wanted to simulate>>a>>merge>>conflict instead of writing top %percentage printf/scanf calls.

The input is an EOF terminated stream (I could adapt this to accept '\n' termination, though). It doesn't actually check the separator.

The output is stored into a std::set<int> reference. It must be empty when called.

Usage:

std::istringstream input{str};
std::set<int> output;
f(input, output);
// Output now contains the result

Ungolfed:

#include <set> // std::set
#include <iostream> // streams (abstracted with abbreviated templates)

// input: An EOF terminated std::basic_istream (e.g. std::istringstream)
// output: stored into a reference to a std::set<int>. Must be empty.
// Golfed code returns int, but doesn't actually return anything
void interpret_interval(std::basic_istream &input, std::set<int> &output)
{
    // Holders for our range
    int start, end;
    // read input
    for (char left, right, tmp /* overwrites left/right in golfed code */;
         // this will return false on EOF (or EOS)
         //       [       -1       ,      4      )
         input >> left >> start >> tmp >> end >> right;
         // discard U, sets EOF bit on end
         input >> tmp)
    {
         // done indirectly in the golfed code
         if (left == '[') // golf check: '(' == 40, '[' == 91, do a modulo 2
             start--; // one extra iteration 
         if (right == ')') // golf check: ')' == 41, ']' == 93, less than 42
             end--; // one less iteration

         // Loop from end to start, inserting all the numbers in the
         // range to output.
         // XXX: std::iota? Doubt it would be smaller due to the include.
         for (; end > start; end--) {
             output.insert(end);
         }
    }
    // output now contains the set of values. Due to it being a std::set, all values
    // are unique. :)
}

Answer 3

Jelly, 23 22 bytes

ṣ”Uµṙ1“(Ḋ)Ṗ,r”yḟØ[V)FQ

Try it online!

-1 byte thanks to ovs

How it works

ṣ”Uµṙ1“(Ḋ)Ṗ,r”yḟØ[V)FQ - Main link. Takes a string S on the left
ṣ”U                    - Split S on "U"
   µ               )   - Over each section R in the split S:
    ṙ1                 -   Rotate by once, shifting the first character to the end
      “(Ḋ)Ṗ,r”         -   Yield "(Ḋ)Ṗ,r"
              y        -   Transliterate; Replace "(" by "Ḋ", ")" by "Ṗ" and "," by "r"
                Ø[     -   Yield "[]"
               ḟ       -   Remove "[]"
                  V    -   Eval as Jelly code
                    F  - Flatten
                     Q - Deduplicate

Why r, Ḋ and Ṗ?

As we only consider each individual range in the transliterate-then-eval stage, we'll just take a look at the four possible examples:

[0,5] -> 0r5
[0,5) -> 0r5Ṗ
(0,5] -> 0r5Ḋ
(0,5) -> 0r5ṖḊ

In Jelly, r in the infix inclusive range command, so 0r5 ⁼ [0,1,2,3,4,5]. Ḋ is dequeue (i.e. remove first element) and Ṗ is pop (remove last element). So r generates the range, then we remove the first and/or last elements if necessary, creating exclusive ranges.

Answer 4

Perl 5 -MList::Util=uniq -FU, 53 bytes

say for uniq map{($a,$b)=/-?\d+/g;$a+/\(/..$b-/\)/}@F

Try it online!

Answer 5

Ruby -nl, 69 bytes

p eval"[*#{gsub /[(),U-\]]/,?(=>'1+',?)=>'-1',?,=>'..',?U=>',*'}]|[]"

Try it online!

Answer 6

Jelly, 22 bytes

ṣ”UµØ(fOị⁾ṖḊvṖḊVr/Ʋ)ẎQ

A monadic Link accepting a list of characters which yields a list of integers.

Try it online! (Footer formats the resulting Jelly list as a Python list.)
Or see the test-suite.

How?

ṣ”UµØ(fOị⁾ṖḊvṖḊVr/Ʋ)ẎQ - Link: list of characters, S
 ”U                    - literal character = 'U'
ṣ                      - split (S) at ('U's)
   µ               )   - for each part, P:
    Ø(                 -   literal list of characters = "()"
      f                -   filter keep (characters of P which are one of "()")
       O               -   to ordinals - i.e. '(' -> 40  and  ')' -> 41
         ⁾ṖḊ           -   literal list of characters "ṖḊ"
        ị              -   index into    ...      -> 'Ḋ'          -> 'Ṗ'
                  Ʋ    -   last four links as a monad, f(P):
             Ṗ         -     pop - i.e. remove ']' or ')' from the right of P)
              Ḋ        -     dequeue - i.e. remove '[' or '(' from the left of P)
               V       -     evaluate as Jelly code - e.g. "-4,2" becomes the list [-4,2]
                 /     -     reduce with:
                r      -       inclusive range            ...and then [-4,-3,-2,-1,0,1,2]
            v          -   evaluate (the string of "ṖḊ" characters)
                           as Jelly code with input (the inclusive range)
                    Ẏ  - tighten (to a single list)
                     Q - de-duplicate

Answer 7

JavaScript (ES6), 104 bytes

Returns a set.

s=>s.replace(/(\[?)(-?\d+),(-?\d+)(]?)/g,(_,a,b,c,d)=>(g=_=>b>c-!d||g(S.add(b++)))(b-=-!a),S=new Set)&&S

Try it online!

Commented

s =>                           // s = input sequence
s.replace(                     // match in s all occurrences of:
  /(\[?)(-?\d+),(-?\d+)(]?)/g, //   (\[?)   an optional opening bracket (a)
                               //   (-?\d+) a number preceded by an optional '-' (b)
                               //   ,       a comma
                               //   (-?\d+) another number in the same format (c)
                               //   (]?)    an optional closing bracket (d)
  (_, a, b, c, d) => (         //
    g = _ =>                   //   g is a recursive function ignoring its input
      b > c - !d ||            //     abort if b is greater than c, or greater than
                               //     c - 1 if d is not defined
        g(S.add(b++))          //     otherwise: add b to S, increment b and do a
                               //     recursive call
  )(b -= -!a),                 //   initial call to g; increment b if a is not defined
  S = new Set                  //   initialize S to a set
) && S                         // end of replace(); return S

Answer 8

J, 60 bytes

[:~.@;'U'<@([:({:+[:i.0>.-/)(']('={:,{.)+3 1".@;@{;:);._1@,]

Try it online!

• 'U' ...;._1@, ] - Prepend 'U', to the input ] and cut it using the first character ;._1, ie U, as a delimiter, applying the verb defined by ... to each piece. Now we'll breakdown what's in ...:

• First we turn it into boxed words ;:, so for example '(_5,2]' becomes:

  ┌─┬──┬─┬─┬─┐
  │(│_5│,│2│]│
  └─┴──┴─┴─┴─┘
  

  and we take elements from indexes 3 and 1 3 1 ... { (the numbers) and unbox and convert then to ints ".@;@. We take them in reverse order, right endpoint first, because it ends up saving bytes in a later step.

• ('](' = {: , {.) + This adds an adjustment to each of the numbers, based on endpoint type. {:,{. returns the last and first character, and ](= does an element-wise comparison, which will return 1 when equal, 0 otherwise. Thus the original input's right endpoint is incremented when it is ], and its left endpoint is incremented when it's ).

• ({: + [: i. 0 >. -/) The adjusted, reversed endpoints are now passed to this phrase, which sticks a minus sign between them -/, and takes the maximum of that result and 0 0 >. (this is to account for the (0,0) case, which would otherwise return _1). We then generate the integers up to, but not including, that result i. and add the original input's adjusted left endpoint {: to all of them. We now have the correct range of numbers for a single range.

• <@ And we box that up, to avoid fill when pieces of unioned input of different lengths are combined.

• [: ~.@; Finally we unbox the combined result to get a single list ; and dedup it ~.@.

Answer 9

Charcoal, 46 bytes

ＦＥ⪪ＳU⪪ι,Ｆ…⁺ＩΦ§ι⁰λ№§ι⁰(⁺Ｉ⮌Φ⮌§ι¹λ№§ι¹]Ｆ¬№υκ⊞υκＩυ

Try it online! Link is to verbose version of code. Uses U as the union operator. Explanation:

ＦＥ⪪ＳU⪪ι,

Split the input on U and then split each part on , and loop over each pair of parts.

Ｆ…⁺ＩΦ§ι⁰λ№§ι⁰(⁺Ｉ⮌Φ⮌§ι¹λ№§ι¹]

Form a range from the integer in the first part (excluding the first character) and the integer in the second part (excluding the last character), except increment the first integer if the first part contains a ( and increment the second integer if the second part contains a ], and loop over the range.

Ｆ¬№υκ⊞υκ

Push any new integers to the predefined empty list.

Ｉυ

Print all of the collected integers.

Answer 10

Wolfram Language (Mathematica), 66 bytes

ToExpression[(#/.{"["->"Range[","("->"Range[1+",")"->"-1]"})<>""]&

Try it online!

Input a list of characters.

Answer 11

R, 148 bytes

function(s)unique(unlist(lapply(parse(t=chartr("[],","():",gsub(",(-?\\d))",",(\\1-1))",gsub("\\((-?\\d)","((1+\\1)",el(strsplit(s,"U")))))),eval)))

Try it online!

If there's a shorter way, I can't seem to think of it.

Answer 12

Zsh, ⁸⁹ 84 bytes

for i (${(s"U")1}){seq $[${${i%,*}#?}+1-#i&1] $[${${i#*,}%?}-!(##$i[-1]&4)]}|sort -u

Try it online!

Answer 13

PowerShell for Windows, 133 114 bytes

$(switch -r($args){'\('{$l++}','{$l+=+$n}'\)'{$n-=1}'\)|]'{$l..$n*($l-le$n)
$l=0}\D{$n=''}'\d|-'{$n+=$_}})|sort -u

Try it online!

Less golfed:

$numbers = switch -Regex ($args){
    '\('    {$left++}
    ','     {$left+=+$num}
    '\)'    {$num-=1}
    '\)|]'  {$left..$num*($left -le $num);$left=0}
    '\D'    {$num=''}
    '\d|-'  {$num+=$_}
}
$numbers|sort -u

Answer 14

PowerShell, 137 133 bytes

-4 bytes thanks to Mazzy, who has an even cooler PS solution to this challenge!

$r="'|% rep* '"
"'('+('$args$r(','[1+$r)','-1]$r]','))$r[','(($r,' '),($r`U' ',')+',0)'"|iex|iex|%{$l,$n=$_;$l..$n*($n-ge$l)}|sort -u

Try it online!

Answer 15

QuadR, 40 bytes

Uses ∪ and ¯ instead of U and -

⍎⍵
\[
\(
,
\)
]
(
(1↓
{⍺+0,⍳0⌈⍵-⍺}
-1)
)

Try it online or try them all!

Execute (⍎) it (⍵) after simple transliteration to APL:

In	Out	Explanation
[	(	Open group
(	(1↓	Open group but with first element (the start) removed
,	{⍺+0,⍳0⌈⍵-⍺}	Anonymous infix lambda to compute range (see below)
)	-1)	Close group but subtract one from the end
]	)	Close group

The "try them all" link also replaces \n with APL's statement separator ⋄, and runs in Document mode.

The infix range lambda {⍺+0,⍳0⌈⍵-⍺}

{…} "dfn"; left and right arguments are ⍺ and ⍵:

 ⍵-⍺ difference

 0⌈ maximum of zero and that; nulls negative differences like [3,3) → (3…3-1)

 ⍳ ɩndices one through that

 0, prepend zero

 ⍺+ add start point to all of those

Answer 16

Haskell, 194 180 bytes

import Data.List
a=init
l=drop 1
t""=[]
t c=nub$i v++t(l n)where(v,n)=span(/='U')c
i('(':c)=l$i('[':c)
i c|last c==')'=a$i$a c++"]"|1<2=f$span(/=',')c
f(_:o,_:w)=[read$o..read$a w]

Try it online!

Answer 17

05AB1E, 28 bytes

'U¡ε¦¨',¡ŸÙy„()©Ã®"¦¨"‡.V}˜ê

Try it online or verify all test cases.

Explanation:

'U¡              '# Split the (implicit) input-string on "U"
   ε              # Map over each interval:
    ¦¨            #  Remove the first and last characters (the "[]()")
      ',¡        '#  Split on ","
         Ÿ        #  Transform that pair of integers into a ranged list
          Ù       #  And uniquify it
                  #  (if a==b in [a,b], it will result in pair [a,a] instead of [a])
    y             #  Push the interval-string we're mapping over again
     „()          #  Push string "()"
        ©         #  Store it in variable `®` (without popping)
         Ã        #  Keep only the "()" in the interval-string (if any)
     ®            #  Push "()" from variable `®` again
      "¦¨"        #  Push "¦¨"
          ‡       #  Transliterate "(" to "¦" and ")" to "¨"
           .V     #  Evaluate and execute it as 05AB1E code:
                  #   `¦`: Remove the first value from the list
                  #   `¨`: Remove the last value from the list
   }˜             # After the map: flatten the list of lists
     ê            # And sort and uniquify the values
                  # (after which the result is output implicitly)

Answer 18

APL (Dyalog Unicode), ¹⁰⁷ 62 bytes

⍎'\]' '\[' ',' '\(' '\)'⎕R')' '(' '{⍺+⍳0⌈1+⍵-⍺}' '(1↓' '-1)'⊢⎕

Try it online!

Does a huge regex replacement and then executes the string.

uses ∪ and ¯ for input.

Uses ⎕IO←0 (0-indexing)

-45 bytes by stealing a ton from Adám's QuadR answer(It has a well-written explanation, go upvote it!).