Expand a bash brace expansion

Question

For mostly historical reasons, bash is quite a hodge-podge of syntax and programming paradigms - this can make it awkward and sometimes frustrating to golf in. However it does have a few tricks up its sleeve that can often make it competitive with other mainstream script languages. One of these is brace expansion.

There are two basic types of brace expansion:

• List braces may contain comma-separated lists of arbitrary strings (including duplicates and the empty string). For example {a,b,c,,pp,cg,pp,} will expand to a b c pp cg pp (note the spaces around the empty strings).
• Sequence braces may contain sequence endpoints separated by ... Optionally another .. may follow, followed by a step size. Sequence endpoints may be either integers or characters. The sequence will automatically ascend or descend according to which endpoint is greater. For example:
  • {0..15} will expand to 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  • {-10..-5} will expand to -10 -9 -8 -7 -6 -5
  • {3..-6..2} will expand to 3 1 -1 -3 -5
  • {a..f} will expand to a b c d e f
  • {Z..P..3} will expand to Z W T Q

Beyond this, sequence and list braces may exist with list braces:

• {a,b,{f..k},p} will expand to a b f g h i j k p
• {a,{b,c}} will expand to a b c

Braces expand with non-whitespace strings either side of them. For example:

• c{a,o,ha,}t will expand to cat cot chat ct

This also works for multiple braces concatenated together:

• {ab,fg}{1..3} will expand to ab1 ab2 ab3 fg1 fg2 fg3

This can get quite complex. For example:

• {A..C}{x,{ab,fg}{1..3},y,} will expand to Ax Aab1 Aab2 Aab3 Afg1 Afg2 Afg3 Ay A Bx Bab1 Bab2 Bab3 Bfg1 Bfg2 Bfg3 By B Cx Cab1 Cab2 Cab3 Cfg1 Cfg2 Cfg3 Cy C

However, if there is whitespace between expansions, then they simply expand as separate expansions. For example:

• {a..c} {1..5} will expand to a b c 1 2 3 4 5

Note how order is always preserved.

---

Entries for this challenge will expand bash brace expansions as described above. In particular:

• eval by bash (or other shells that perform similar expansion) is not allowed
• sequence braces will always be number-to-number, lowercase-to-lowercase or uppercase-to-uppercase with no mixing. Numbers will be integers in the 32-bit signed range. If given, the optional step size will always be a positive integer. (Note that bash will also expand {A..z} as well, but this may be ignored for this challenge)
• individual items in list braces will always be composed only of upper- and lower-case alphanumeric characters (empty string included)
• list braces may contain arbitrary nestings of other brace expansions
• braces may be concatenated arbitrary numbers of times. This will be limited by your language's memory, so the expectation is that you can theoretically do arbitrary numbers of concatenations but if/when you run out of memory that won't count against you.

The examples in the text above serve as testcases. Summarised, with each line of input corresponding to the same line of output, they are:

Input

{0..15}
{-10..-5}
{3..-6..2}
{a..f}
{Z..P..3}
{a,b,{f..k},p}
{a,{b,c}}
c{a,o,ha,}t
{ab,fg}{1..3}
{A..C}{x,{ab,fg}{1..3},y,}
{a..c} {1..5}
{a{0..100..10},200}r

Output

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
-10 -9 -8 -7 -6 -5
3 1 -1 -3 -5
a b c d e f
Z W T Q
a b f g h i j k p
a b c
cat cot chat ct
ab1 ab2 ab3 fg1 fg2 fg3
Ax Aab1 Aab2 Aab3 Afg1 Afg2 Afg3 Ay A Bx Bab1 Bab2 Bab3 Bfg1 Bfg2 Bfg3 By B Cx Cab1 Cab2 Cab3 Cfg1 Cfg2 Cfg3 Cy C
a b c 1 2 3 4 5
a0r a10r a20r a30r a40r a50r a60r a70r a80r a90r a100r 200r

Answer 1

Python 2.7, 752 728 bytes

Wow, this is like a bunch of code golfs in one challenge!

Thanks to @Neil for shortening a lambda

def b(s,o,p):
 t,f=s>':'and(ord,chr)or(int,str);s,o=t(s),t(o);d=cmp(o,s)
 return list(map(f,range(s,o+d,int(p)*d)))
def e(s):
 c=1;i=d=0
 while c:d+=-~'{}}'.count(s[i])%3-1;i+=1;c=i<len(s)and 0<d
 return i
def m(s):
 if len(s)<1:return[]
 if','==s[-1]:return m(s[:-1])+['']
 i=0
 while i<len(s)and','!=s[i]:i+=e(s[i:])
 return[s[:i]]+m(s[i+1:])
n=lambda a,b:[c+d for c in a for d in b]or a or b
def p(s):
 h=s.count
 if h('{')<1:return[s]
 f,l=s.index('{'),e(s)
 if h('{')<2and h('..')>0and f<1:s=s[1:-1].split('..');return b(s[0],s[1],s[2])if len(s)>2 else b(s[0],s[1],1)
 if f>0 or l<len(s):return n(p(s[:f]),n(p(s[f:l]),p(s[l:])))
 return sum(map(list,map(p,m(s[1:-1]))),[])
o=lambda s:' '.join(p('{'+s.replace(' ',',')+'}'))

Explanation

• b: calculates range according to specs.
• e: returns position of first outermost close brace. Iterative.
• m: splits outermost elements on commas. Recursive.
• n: combines arrays while checking for empties. I couldn't get and/or to work.
• p: Where most of the work is done. Checks all the cases (Range, just list, needs to combine). Recursive.
• o: What should take input. Formats input/output to p.

---

I feel I can improve in some places, so I will try to golf more. Also I should put in more detail in the explanation.

Answer 2

Ruby, 405 403 401 400 bytes

A wise man (Jamie Zawinski) once said, "Some people, when confronted with a problem, think 'I know, I'll use regular expressions.' Now they have two problems."

I don't think I fully appreciated that quote until I tried to solve this problem with recursive regex. Initially, the regex cases seemed simple, until I had to deal with the edge cases involving letters adjacent to brackets, and then I knew that I was in hell.

Anyways, run it online here with test cases

->s{s.gsub!(/{(-?\w+)..(-?\w+)(..(\d+))?}/){x,y=$1,$2;a,b,c=[x,y,$4].map &:to_i
$1[/\d/]?0:(a,b=x,y)
k=a<b ?[*a..b]:[*b..a].reverse
?{+0.step(k.size-1,$4?c:1).map{|i|k[i]}*?,+?}}
r=1
t=->x{x[0].gsub(/^{(.*)}$/){$1}.scan(/(({(\g<1>|,)*}|[^,{}]|(?<=,|^)(?=,|$))+)/).map{|i|i=i[0];i[?{]?r[i]:i}.flatten}
r=->x{i=x.scan(/({(\g<1>)*}|[^{} ]+)/).map(&t)
i.shift.product(*i).map &:join}
s.split.map(&r)*' '}

Ungolfed:

->s{
  s.gsub!(/{(-?\w+)..(-?\w+)(..(\d+))?}/){  # Replace all range-type brackets {a..b..c}
    x,y=$1,$2;a,b,c=[x,y,$4].map &:to_i     # Set up int variables
    $1[/\d/]?0:(a,b=x,y)                    # Use int variables for a,b if they're numbers
    k=a<b ?[*a..b]:[*b..a].reverse          # Create an array for the range in the correct direction
    '{'+                                    # Return the next bit surrounded by brackets
      0.step(k.size-1,$4?c:1).map{|i|k[i]   # If c exists, use it as the step size for the array
      }*','                                 # Join with commas
      +'}'
  }
  r=1                                       # Dummy value to forward-declare the parse function `r`
  t=->x{                                    # Function to parse a bracket block
    x=x[0].gsub(/^{(.*)}$/){$1}             # Remove outer brackets if both are present
                                            # x[0] is required because of quirks in the `scan` function
    x=x.scan(/(({(\g<1>|,)*}|[^,{}]|(?<=,|^)(?=,|$))+)/)
                                            # Regex black magic: collect elements of outer bracket
    x.map{|i|i=i[0];i[?{]?r[i]:i}.flatten   # For each element with brackets, run parse function
  }
  r=->x{                                    # Function to parse bracket expansions a{b,c}{d,e}
    i=x.scan(/({(\g<1>)*}|[^{} ]+)/)        # Regex black magic: scan for adjacent sets of brackets
    i=i.map(&t)                             # Map all elements against the bracket parser function `t`
    i.shift.product(*i).map &:join          # Combine the adjacent sets with cartesian product and join them together
  }
  s.split.map(&r)*' '                       # Split on whitespace, parse each bracket collection
                                            #   and re-join with spaces
}

Answer 3

JavaScript (Firefox 30-57), 465 427 425 bytes

f=s=>/\{/.test(s)?f(s.replace(/([^,{}]*\{[^{}]*\})+[^,{}]*/,t=>t.split(/[{}]+/).map(u=>u.split`,`).reduce((a,b)=>[for(c of a)for(d of b)c+d]))):s.split`,`.join` `
s=>f(`{${s.split` `}}`.replace(/\{(-?\w+)\.\.(-?\w+)(\.\.(\d+))?\}/g,(m,a,o,_,e)=>{m=(a>'@')+(a>'_');a=parseInt(a,m?36:10);o=parseInt(o,m?36:10);e=+e||1;if(o<a)e=-e;for(r=[];e<0?o<=a:a<=o;a+=e)r.push(m?a.toString(36):a);r=`{${r}}`;return m-1?r:r.toUpperCase()}))

ES6 version of f weighs in at an extra 10 bytes:

f=s=>/\{/.test(s)?f(s.replace(/([^,{}]*\{[^{}]*\})+[^,{}]*/,t=>t.split(/[{}]+/).map(u=>u.split`,`).reduce((a,b)=>[].concat(...a.map(c=>b.map(d=>c+d)))))):s.split`,`.join` `
g=s=>f(`{${s.split` `}}`.replace(/\{(-?\w+)\.\.(-?\w+)(\.\.(\d+))?\}/g,(m,a,o,_,e)=>{m=(a>'@')+(a>'_');a=parseInt(a,m?36:10);o=parseInt(o,m?36:10);e=+e||1;if(o<a)e=-e;for(r=[];e<0?o<=a:a<=o;a+=e)r.push(m?a.toString(36):a);r=`{${r}}`;return m-1?r:r.toUpperCase()}))
h=(s,t=s.replace(/\{[^{}]*\}/,""))=>s!=t?h(t):!/[{}]/.test(s)

<input oninput="o.textContent=h(this.value)?g(this.value):'{Invalid}'"><div id=o>

Explanation: Starts by changing spaces into commas and wrapping the entire string in {} for consistency (thanks to @Blue for the idea). Then searches for all the {..} constructs and expands them into {,} constructs. Next uses recursion to repeatedly expands all {,} constructs from the inside out. Finally replaces all commas with spaces.

f=s=>/\{/.test(s)?                  while there are still {}s
 f(s.replace(                       recursive replacement
  /([^,{}]*\{[^{}]*\})+[^,{}]*/,    match the deepest group of {}s
  t=>t.match(/[^{}]+/g              split into {} terms and/or barewords
   ).map(u=>u.split`,`              turn each term into an array
   ).reduce((a,b)=>                 loop over all the arrays
    [for(c of a)for(d of b)c+d]))   cartesian product
  ):s.split`,`.join` `              finally replace commas with spaces
s=>f(                               change spaces into commas and wrap
 `{${s.split` `}}`.replace(         match all {..} seqences
   /\{([-\w]+)\.\.([-\w]+)(\.\.(\d+))?\}/g,(m,a,o,_,e)=>{
    m=(a>'@')+(a>'_');              sequence type 0=int 1=A-Z 2=a-z
    a=parseInt(a,m?36:10);          convert start to number
    o=parseInt(o,m?36:10);          convert stop to number
    e=+e||1;                        convert step to number (default 1)
    if(o<a)e=-e;                    check if stepping back
    for(r=[];e<0?o<=a:a<=o;a+=e)    loop over each value
     r.push(m?a.toString(36):a);    convert back to string
    r=`{${r}}`;                     join together and wrap in {}
    return m-1?r:r.toUpperCase()})) convert type 1 back to upper case