Cartesian literal notation

Question

Introduction

In computer science, a literal is a notation for representing a fixed value in source code. Almost all programming languages have notations for atomic values, some also have notations for elements of enumerated types and compound values. Wikipedia

For example 1 usually represent an integer value, "Hello" a string, [9,5,11] an array and 1..9 a range.

The range notation is special because we have just two values in the literal but the actual value includes all elements in between.
We can say that a range expands to an array or a list of values. So the expansion of the range 1..9 is [1,2,3,4,5,6,7,8,9].

In this challenge you are given a Cartesian literal as input and you have to output its expansion.

Notation format rules

• consider only non negative integers values.

• this notation could work for products of any degree but in this challenge you have to handle only products of two sets, so we get a list of pairs.

• we can have one or more groups of products. Every group is terminated by the / symbol and generates its own list which is then concatenated to the others groups.

• each group has 2 sets: A and B and they are separated by the : symbol.

• each set is composed of ranges and/or atomic values separated by ,.
  Ranges are in the form start-end for example 0-10.

  Values must be sorted without overlaps, for example 1-5,5,4 can not appear.

• every group contains non empty sets.

Example

The literal 1-2,5:10-12/0:1-3/ is composed of two groups.

The first group (1-2,5:10-12) has the sets:

A=[1,2,5]  
B=[10,11,12]

and generates the product

[1,10],[1,11],[1,12],[2,10],[2,11],[2,12],[5,10],[5,11],[5,12]

the second group generates [0,1],[0,2],[0,3] which is appended to the first so the output is:

[[1,10],[1,11],[1,12],[2,10],[2,11],[2,12],[5,10],[5,11],[5,12],[0,1],[0,2],[0,3]]

Test cases

"0:0/" -> [[0,0]]
"1-3:2/" -> [[1,2],[2,2],[3,2]]
"4:5-6/" -> [[4,5],[4,6]]
"9,10,11:9-11/" -> [[9,9],[9,10],[9,11],[10,9],[10,10],[10,11],[11,9],[11,10],[11,11]]
"100:0-1,2,3-4/1:2/" -> [[100,0],[100,1],[100,2],[100,3],[100,4],[1,2]]
"1:2/3:4/5:6/7:8/9:10/" -> [[1,2],[3,4],[5,6],[7,8],[9,10]]
"11-13:2/" -> [[11,2],[12,2],[13,2]]

Rules

• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.
• You can assume the input will always be a valid literal, you don't have to handle invalid literals.

Answer 1

05AB1E, 25 bytes

¯I¤¡¨vy':¡ε',¡ε'-¡Ÿ}˜}`â«

Pretty straight-forward approach.

Try it online or verify all test cases.

Explanation:

¯                    # Start with an empty list []
 I                   # Push the input-string
  ¤                  # Push its last character (without popping): "/"
   ¡                 # Split it on "/"
    ¨                # Remove the trailing empty string
     vy              # Foreach over the parts:
       ':¡          '#  Split the part on ":"
          ε          #  Map over each smaller part:
           ',¡      '#   Split it on ","
              ε      #   Inner map yet again:
               '-¡  '#    Split on "-"
                  Ÿ  #    Convert this pair (or single integer) to a ranged list
              }˜     #   After the inner-most map: flatten
          }`         #  After the outer map: pop and push the lists separated to
                     #  the stack
            â        #  Create pairs of the two lists with the cartesian product
             «       #  Merge this list of pairs to the result-list
                     # (after the loop, the result is output implicitly)

Answer 2

Jelly, 25 23 bytes

ṣṪṣ”:ṣ”,⁾-ry$€VFƲ€ŒpƊ€Ẏ

Try it online!

-2 bytes from reading Kevin Cruijssen's answer.

ṣṪṣ”:ṣ”,⁾-ry$€VFƲ€ŒpƊ€Ẏ
ṣ                       Split on
 Ṫ                        last character, removing it from the string
                    Ɗ€  For each:
  ṣ”:                     Split on ":"
                Ʋ€        For each:
     ṣ”,                    Split on ","
            $€              For each:
           y                  Replace
        ⁾-r                     "-" with "r"
              V             Evaluate as Jelly programs (r = range)
               F            Flatten
                  Œp      Cartesian product
                      Ẏ Tighten (shallow flatten)

Answer 3

Ruby, 98 87 bytes

p`dd`.gsub(/\d+-/,'*\00..').split(?/).flat_map{|x|eval"[%s].product([%s])"%x.split(?:)}

Try it online!

Explanation

 `dd`.gsub(/\d+-/,'*\00..')               # input and replace "number-" with "*number-0..", ruby syntax for ranges
.split(?/).flat_map                       # split on "/" and map block, then concat
{|x|eval"[%s].product([%s])"%x.split(?:)} # string interpolate and eval
p                                         # print

Answer 4

Ruby, 131 118 110 bytes

->s{eval"[#{s.gsub(/(\d+)-/,'*\1..').gsub(/([^\/:]+)/,'[\1]').gsub(/:([^\/:]+)/,'.product(\1)').tr ?/,?+}[]]"}

Try it online!

I tried to parse the expression and apply the single operations, but the shortest solution is to just convert the string into a Ruby expression, and evaluate it.

Answer 5

Python 3, 188 bytes

from itertools import*
f=lambda s:[q for x in s.split("/")[:-1]for q in product(*([w for z in y.split(",")for w in range(*map(eval,(z+"-"+z+"+1").split("-")[-2:]))]for y in x.split(":")))]

Try it online!

Uses a lot of nested list comprehensions. The hardest parts are the ranges. (z+"-"+z+"+1").split("-")[-2:] converts a range of form "a-b" to ["a","b+1"] and a single integer "a" to ["a","a+1"]. These are then evaluated and fed directly to range.

Answer 6

Vyxal, 36 27 bytes

ṫ/ƛ\:/ƛ⌐ƛ\-/k≈•⌊÷ṡ;f;÷Ẋ;f2ẇ

Try it Online!

-9 thanks to Kevin

With colour:

Explained

ṫ/ƛ\:/ƛ⌐ƛ\-/k≈•⌊÷ṡ;f;÷Ẋ;f2ẇ
ṫ/                           # Split the input string on its last character ("/") - returns groups
  ƛ                          # To each group G:
   \:/                       #   Split G on ":" - returns sets
      ƛ                      #   To each set S:
       ⌐                     #     Split S on commas - returns values
        ƛ                    #     To each value V:
         \-/                 #       Split V on "-" - returns items in range
            kť              #       Mold that to the shape of [0, 1] - honestly idk what this does, but it works and it's genius. (it seems to make it so that each list is of length 2, even if it's a single item list)
              ⌊÷ṡ            #       Generate an inclusive range between the two numbers
                 ;           #     End map over each V
                  f          #     and flatten that - returns a flat list of all numbers to cartesian product
                   ;         #   End map over each S
                    ÷Ẋ       #   Cartesian product of the sets
                      ;      # End map over each G
                       f2ẇ   # flatten and place back into pairs

Answer 7

Zsh, 96 bytes

for x (${(s:/:)${1//(#m)<->-<->/\{${MATCH/-/..}\}}})eval print -l \{${x/:/,z\},\{z,}\}|grep -v z

Attempt This Online!

Zsh seems like it was made for this challenge!

not.

---

Explanation:

• ${1//(#m)<->-<->/\{${MATCH/-/..}\}}: replace all instances of A-B, where A and B are numbers, with {A..B}
• for x (${(s:/:)}): split that on / and loop:
  • ${x/:/,z\},\{z,} replace : with ,z},{z,
  • This constructs strings that follow Zsh's pattern of brace expansion, which is the easiest way to do a Cartesian product
  • By evaling them, they are expanded properly, and print -l prints them newline-separated.
  • The ,zs are to work around the fact that things of the form {0} are treated as literal strings, and don't just expand to a 1-element list. They are removed again by the |grep -v z

Answer 8

Ruby, 7977 bytes

->s{eval"[#{s.gsub(?:,'].product([').gsub(/\d+-/,'*\00..').gsub ?/,'])+['}]"}

Try it online!

• Saved 2 thanks to @G B

The literal already has a structure we can use, we just have to substitute a few symbols and then we evaluate it

[      prepend a [  
#{s.gsub(..).gsub(...    transform input by replacing:  
  `:`       => '].product(['  
  `/(\d+)-/` => '*\1..'  here \1 is the captured number  
  `/`       => '])+[' we add next square  
] which we close empty if there's no group available.

Here is an example with adds and substitutions :
100 : 0- 1 , 2 , 3- 4 / 1 : 2 /
[ 100 ].product([ *0.. 1,2, *3.. 4 ])+[ 1 ].product([ 2 ])+[ ]

Answer 9

Retina, 79 bytes

!_S`/
%(+`\b(\d+)-(\1\b|())
$1$#3*$(,$.(*__)-
Lw$`\b(\d+)\b.*:.*\b(\d+)\b
$1,$2

Try it online! Outputs each pair on its own line but link includes test suite that joins the lines back together for convenience. Explanation:

!_S`/

Split on /s, but drop empty entries.

%(`

Separately for each split:

\b(\d+)-(\1\b|())
$1$#3*$(,$.(*__)-

Expand a range: if it has already expanded to the form n-n then simply delete the -n otherwise replace it with n,n+1-m.

+`

Repeat until all ranges have been completely expanded.

Lw$`\b(\d+)\b.*:.*\b(\d+)\b
$1,$2

Take the Cartesian product of both sets by considering overlapped matches of one number from each of the sets.

Answer 10

Charcoal, 49 bytes

Ｆ⪪Ｓ/¿ι«≔⟦⟧θＦ²ＦＥ⪪§⪪ι:¬κ,Ｉ⪪λ-Ｆ…·§λ⁰⊟λ¿¬κ⊞θμＦθ⟦⁺⁺μ,ν

Try it online! Link is to verbose version of code. Would be 1 byte shorter if the product could be output in a different order. Explantion:

Ｆ⪪Ｓ/¿ι«

Split the input on /s and loop over non-empty groups.

≔⟦⟧θ

Prepare to collect the second set.

Ｆ²

Loop over each set.

ＦＥ⪪§⪪ι:¬κ,Ｉ⪪λ-

Split the group on :, extract the desired set, then split that on ,, then split that on -, then cast to integer.

Ｆ…·§λ⁰⊟λ

Loop over each of the resulting ranges. (Where there was no - in that range, the same integer will be used as the start and end of the range, resulting in a range of that integer.)

¿¬κ

If this is the second set (which is being processed first), then...

⊞θμ

... save this integer for later, otherwise...

Ｆθ⟦⁺⁺μ,ν

... for all integers from the second set, pair the current integer from the first set with it.

Answer 11

Bash + GNU coreutils, 126 bytes

tr :/ \\n|sed -Ee 's/([0-9]+)-([0-9]+)/{\1..\2}/g' -e 's/.+,.+/{\0}/'|while read s&&read t;do eval printf %s\\\\n $s\\ $t;done

Try it online! Takes input on STDIN without a trailing newline. Explanation:

tr :/ \\n|

Split the input on both colons and slashes. This results in a trailing newline but read eats that anyway.

sed -Ee 's/([0-9]+)-([0-9]+)/{\1..\2}/g' -e 's/.+,.+/{\0}/'|

Expand numeric ranges and wrap lists in braces.

while read s&&read t;do eval printf %s\\\\n $s\\ $t;done

Read two sets at a time and generate their Cartesian product.

Answer 12

Python 3, 187 bytes

import itertools as t
[k for b in s.split('/')[:-1] for k in t.product(*[[j for x in m.split(',') for j in range(*[int(x.split('-')[0]),int(x.split('-')[-1])+1])] for m in b.split(':')])]

Answer 13

Pure Bash, 223 213 205 bytes

IFS=/
for i in $1
do
l=
IFS=:
for j in $i
do
while [[ $j =~ ([0-9]*)-([0-9]*) ]]
do
set -- ${BASH_REMATCH[@]}
j=${j/$1/"{$2..$3}"}
done
k=${j##*,*}
l=$l\\\ ${k:-"{$j}"}
done
eval printf %s\\\\n ${l:2}
done

Try it online! Takes input as a command-line parameter. Edit: Saved 10 bytes thanks to @pxeger. Explanation:

IFS=/
for i in $1
do
...
done

Split the input on /s. (The last empty string gets ignored.)

l=

Start building up the sets.

IFS=:
for j in $i
do
...
done

Split the group on :s.

while [[ $j =~ ([0-9]*)-([0-9]*) ]]
do
set -- ${BASH_REMATCH[@]}
j=${j/$1/"{$2..$3}"}
done

Expand numeric ranges.

k=${j##*,*}
l=$l\\\ ${k:-"{$j}"}

Wrap lists in braces and concatenate the sets.

eval printf %s\\\\n ${l:2}

Generate the Cartesian product of the sets.

Answer 14

Burlesque, 54 bytes

~]'/;;{':;;{',;;{J'-~[{'-;;)ti^pr@}qtiIE}\m}MPcp}\m}MP

Try it online!

~]           # Drop final /
'/;;         # Split on /
{
  ':;;       # Split on :
  {
   ',;;      # Split on ,
   {
    J'-~[    # Contains -
    {
     '-;;    # Split on -
     {ti}MP  # Map to int and force onto stack
     r@      # Range from low to high
    }  
    {ti}     # To int
    IE       # If else
   }\m       # Map and concatenate
  }MP        # Map and push
  cp         # Cartesian product
 }\m         # Map and concatenate
}MP          # Map and push

Answer 15

R, 196 bytes

function(x,`[`=sapply,t=strsplit,d=do.call)apply(matrix(t(x,'/')[t,":"][t,","][t,"-"][lapply,function(j)as.list(scan(t=j)+!3:4)][function(i)unlist(i[d,w=`:`])],2),2,function(l)d(outer,c(l,paste)))

Try it online!

Outputs a list of each 'group of products' (separated by / in the input), containing space-separated pairs of elements.
+8 bytes to output as a flat vector.

Ungolfed:

a=
 sapply( ... strsplit(x,'/'),   # split input on '/
  sapply( ... strsplit(x,':'),  # split that on ':'
   sapply( ... strsplit(x,','), # split that on ','
    sapply(strsplit(x,'-'))     # and finally split that on '-'
b=lapply(a,function(j)as.list(rep(j,2)[1:2]))
                                # double any lists of one item
c=sapply(b,function(i)unlist(s(i,do.call,what=`:`)))
                                # and apply ':' (range) using
                                # 2-element lists as arguments,
                                # concatenating (unlist) the results
m=matrix(c,2)                   # put the output into 2-row matrices
apply(m,2,function(l)do.call(outer,c(l,paste)))
                                # and, for each column, paste togethe
                                # the elements of each of the two rows

Answer 16

JavaScript (ES10), 150 bytes

This seems quite long...

s=>s.replace(/(\d+)-(\d+)/g,g=(_,a,b)=>a-b?a+[,g(_,-~a,b)]:a)[S='split']`/`.map(s=>s?(g=k=>s[S]`:`[k][S]`,`)(0).map(a=>g(1).map(b=>[a,b])):[]).flat(2)

Try it online!