22
\$\begingroup\$

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 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
\$\endgroup\$
13
  • \$\begingroup\$ Can We assume there are no spaces in the input? \$\endgroup\$ – Command Master Jan 4 at 20:59
  • \$\begingroup\$ Also, can we assume the inputs in the number are integers? \$\endgroup\$ – Command Master Jan 4 at 21:00
  • \$\begingroup\$ @CommandMaster You may assume there are no spaces, and it already says integers in the question. \$\endgroup\$ – Aiden4 Jan 4 at 21:07
  • \$\begingroup\$ Can we use different characters other than ()[]U,? If so, for all of those, or just some? \$\endgroup\$ – caird coinheringaahing Jan 4 at 22:25
  • \$\begingroup\$ @caird coinheringaahing you may use instead of U but the rest should stay. \$\endgroup\$ – Aiden4 Jan 4 at 22:34

18 Answers 18

7
\$\begingroup\$

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

\$\endgroup\$
8
  • \$\begingroup\$ Assigning the string "set(range(" to a variable saves 4 bytes. And set(...) -> {*...} for 2 more. \$\endgroup\$ – ovs Jan 4 at 22:04
  • \$\begingroup\$ @ovs good catch; thanks \$\endgroup\$ – hyper-neutrino Jan 4 at 22:28
  • \$\begingroup\$ A slightly different method for 79 bytes \$\endgroup\$ – dingledooper Jan 5 at 0:56
  • \$\begingroup\$ @dingledooper oh, that's a clever way to translate it. thanks! \$\endgroup\$ – hyper-neutrino Jan 5 at 4:29
  • 1
    \$\begingroup\$ Nevermind; I meant eval('{*range%s}'%input().translate({91:40,40:'(1+',93:'+1)',85:',*range'})) but I realised this wouldn't count as valid because it's not a function anymore and the output isn't being printed anywhere. \$\endgroup\$ – Anakhand Jan 5 at 15:01
7
\$\begingroup\$

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. :)
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Nice solution, well-explained, and with a fantastic sense of humour! I've been appreciating reading your submissions here; keep 'em coming! \$\endgroup\$ – Cody Gray Jan 7 at 0:28
5
\$\begingroup\$

Jelly, 23 bytes

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

Try it online!

Blegh

-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 "r", "(" by "Ḋ" and ")" by "Ṗ"
                 Ø[     -   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.

\$\endgroup\$
2
  • \$\begingroup\$ FQ is a byte shorter than œ|/. \$\endgroup\$ – ovs Jan 4 at 23:32
  • \$\begingroup\$ @ovs It is indeed, nice catch! \$\endgroup\$ – caird coinheringaahing Jan 4 at 23:33
2
\$\begingroup\$

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

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Ruby -nl, 69 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ That footer doesn't seem to be necessary btw \$\endgroup\$ – pxeger Jan 5 at 15:04
  • 1
    \$\begingroup\$ @pxeger Try either (0,0] or [0,0]: with footer, without \$\endgroup\$ – caird coinheringaahing Jan 5 at 17:18
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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 ~.@.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ In which time zone? \$\endgroup\$ – Adám Jan 8 at 1:47
  • \$\begingroup\$ @Adám All right, all right, it's added now :) \$\endgroup\$ – Jonah Jan 8 at 5:17
1
\$\begingroup\$

Charcoal, 46 bytes

FE⪪SU⪪ι,F…⁺IΦ§ι⁰λ№§ι⁰(⁺I⮌Φ⮌§ι¹λ№§ι¹]F¬№υκ⊞υκIυ

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

FE⪪SU⪪ι,

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

F…⁺IΦ§ι⁰λ№§ι⁰(⁺I⮌Φ⮌§ι¹λ№§ι¹]

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.

F¬№υκ⊞υκ

Push any new integers to the predefined empty list.

Iυ

Print all of the collected integers.

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 66 bytes

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

Try it online!

Input a list of characters.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Zsh, 89 84 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Wow! This is awesome! I had no idea the switch statement's regex option could be used like this. Bravo to you! \$\endgroup\$ – Zaelin Goodman Jan 7 at 23:35
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ TIO! Notes:no splatting; I cut a framework to put in a comment. Sorry \$\endgroup\$ – mazzy Jan 7 at 21:37
1
\$\begingroup\$

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)(33-1)

ɩndices one through that

0, prepend zero

⍺+ add start point to all of those

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Unicode), 107 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!).

\$\endgroup\$
4
  • \$\begingroup\$ Do you know ⎕R can do multiple replacements at once? Also: for inspiration. \$\endgroup\$ – Adám Jan 8 at 1:47
  • \$\begingroup\$ @Adám yes, but it gave me an error when I tried that. Thanks for the inspiration. \$\endgroup\$ – Razetime Jan 8 at 3:02
  • \$\begingroup\$ Did you by chance try to combine array and function right-operands? Btw, you don't need those function operands, as you can just inject the value-adjusting APL code. \$\endgroup\$ – Adám Jan 8 at 3:12
  • \$\begingroup\$ @Adám Started doing that a minute ago, will add it in soon \$\endgroup\$ – Razetime Jan 8 at 3:21

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.