11
\$\begingroup\$

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 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.
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Please clarify how exactly the permutations should be generated (a worked example might be useful here). I think I can figure out what you want but I shouldn't have to work backwards from your example to understand the specification. \$\endgroup\$
    – hyper-neutrino
    Nov 25 at 19:31
  • 1
    \$\begingroup\$ Could you please clarify some details about the format? Is the last character always a "/"? Does the input string always contain at least one part? Can the ranges contain only one number (is 13-13 allowed as input)? \$\endgroup\$
    – AnttiP
    Nov 25 at 19:39
  • 4
    \$\begingroup\$ This seems like a good concept, and could do with some time in the Sandbox. For future reference, I highly recommend using the Sandbox before posting so you can get feedback, suggestions, and clarifications first. \$\endgroup\$
    – hyper-neutrino
    Nov 25 at 22:31
  • 2
    \$\begingroup\$ I edited completely because it seemed a nice challenge but it was not very well written, I hope I understood correctly your intentions and hope it's reasonably well written now, I think Cartesian product is more appropriate. If you feel I did wrong feel free to rollback or comment or edit again. Next time use the sandbox please to get some help as suggested previously, \$\endgroup\$
    – AZTECCO
    Nov 26 at 4:01
  • 2
    \$\begingroup\$ @hyper-neutrino I did post it in Sandbox for a week. But there was only one guy made some comment. The Post in Sandbox \$\endgroup\$
    – obnews
    Nov 26 at 13:04

16 Answers 16

4
\$\begingroup\$

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

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

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

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.

\$\endgroup\$
2
  • \$\begingroup\$ this doesn't seem to concat the arrays \$\endgroup\$
    – Natte
    Nov 26 at 9:02
  • \$\begingroup\$ Fixed (+2 bytes) \$\endgroup\$
    – G B
    Nov 26 at 9:27
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Vyxal, 36 27 bytes

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

Try it Online!

-9 thanks to Kevin

With colour:

enter image description here

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ \//'; can be ṫ/ for -3 and (n÷)W can be f2ẇ for another -2 \$\endgroup\$ Nov 26 at 7:42
  • 1
    \$\begingroup\$ ~c[/⌊÷ṡ|_⌊] to /k≈•⌊÷ṡ for another -4 bytes: 27 bytes. \$\endgroup\$ Nov 26 at 8:42
  • \$\begingroup\$ (mold lists) indeed makes it the first argument-list the size of the second argument-list. In 05AB1E we have the shorten/enlarge builtin with a length argument, so it would be 2∍, but it works similarly. If it helps, imagine the first list as an infinite repeating list (e.g. [5] would be [5,5,5,5,5,...], [1,2] would be [1,2,1,2,1,...], etc.) after which it's shortened to the length of the second list. The k≈ is just one of the size-2 lists I could find in the docs, but any of size 2 would do. :) \$\endgroup\$ Nov 26 at 15:27
2
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ So... not pure Zsh, but actually Zsh + coretools? \$\endgroup\$
    – Neil
    Nov 26 at 17:51
  • \$\begingroup\$ @Neil I (almost) never post Zsh answers without meaning "Zsh + GNU coreutils". I take it for granted that the tools designed for shell use can be used in a shell without needing to specify it ;) \$\endgroup\$
    – pxeger
    Nov 26 at 17:56
1
\$\begingroup\$

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.

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

Charcoal, 49 bytes

F⪪S/¿ι«≔⟦⟧θF²FE⪪§⪪ι:¬κ,I⪪λ-F…·§λ⁰⊟λ¿¬κ⊞θμFθ⟦⁺⁺μ,ν

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:

F⪪S/¿ι«

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

≔⟦⟧θ

Prepare to collect the second set.

F²

Loop over each set.

FE⪪§⪪ι:¬κ,I⪪λ-

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

F…·§λ⁰⊟λ

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

Fθ⟦⁺⁺μ,ν

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

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

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ -10 bytes by saving $BASH_REMATCH: Try it online! \$\endgroup\$
    – pxeger
    Nov 26 at 20:59
  • \$\begingroup\$ @pxeger Thanks, that inspired me to shave another 7 bytes off by using set -- instead. \$\endgroup\$
    – Neil
    Nov 26 at 23:31
1
\$\begingroup\$

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

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

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 ])+[ ]

\$\endgroup\$
1
  • \$\begingroup\$ 77 \$\endgroup\$
    – G B
    Dec 2 at 12:24
0
\$\begingroup\$

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.

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

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(':')])]
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Isn't there some ways to use ranges + splat and eval in js? \$\endgroup\$
    – AZTECCO
    Nov 27 at 14:46
  • 1
    \$\begingroup\$ @AZTECCO There is no range builtin in JS. There's at least one proposal, though. \$\endgroup\$
    – Arnauld
    Nov 27 at 14:52

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.