user
Brace expansion is a type of parameter expansion made popular by Unix shells, where it allows users to specify multiple similar string parameters without having to type them all out. E.g. the parameter `enable_{audio,video}` would be interpreted as if both `enable_audio` and `enable_video` had been specified.

Task

Write a function that can perform brace expansion on any input string, according to the following specification.  
Demonstrate how it would be used, and that it passes the four test cases given below.

Specification

In the input string, balanced pairs of braces containing comma-separated substrings (details below) represent *alternations* that specify multiple alternatives which are to appear at that position in the output. In general, one can imagine the information conveyed by the input string as a tree of nested alternations interspersed with literal substrings, as shown in the middle part of the following diagram:

|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| It{{em,alic}iz,erat}e{d,} | *parse*  ―――――▶ ‌ | |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | It | |  |  |  |  |  |  |  |  | | --- | --- | --- | --- | --- | --- | --- | --- | | ⎧ ⎨ ⎩ | |  |  |  | | --- | --- | --- | | ⎧ ⎨ ⎩ | em | ⎫ ⎬ ⎭ | | alic | | iz | ⎫ ⎬ ⎭ | | erat | | | e | |  |  |  | | --- | --- | --- | | ⎧ ⎨ ⎩ | d | ⎫ ⎬ ⎭ | | ‌ | | | *expand*  ―――――▶ ‌ | Itemized Itemize Italicized Italicize  Iterated Iterate |
| input string |  | alternation tree |  | output *(list of strings)* |

This tree can in turn be transformed into the intended list of output strings by, colloquially speaking, determining all the possible ways to walk through it from left to right while only descending into *one* branch of each alternation one comes across *(see the right part of the diagram)*. When implementing it, one can of course combine the parsing and expansion into a single algorithm, but this specification discusses them separately for the sake of clarity.

**Expansion** of alternations can be more rigorously described by these rules:

|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| |  |  |  |  |  |  |  |  |  |  |  |  |  |  | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | a | |  |  |  | | --- | --- | --- | | ⎧ ⎨ ⎩ | 2 | ⎫ ⎬ ⎭ | | 1 | | b | |  |  |  | | --- | --- | --- | | ⎧ ⎨ ⎩ | X | ⎫ ⎬ ⎭ | | Y | | X | | c | | ⟶ | |  | | --- | | a2bXc | | a2bYc | | a2bXc | | a1bXc | | a1bYc | | a1bXc | |

* An alternation causes the list of alternatives that will be produced by its parent branch to be increased 𝑛-fold, each copy featuring one of the 𝑛 alternatives produced by the alternation's child branches, in turn, at that position.
* This means that multiple alternations inside the same branch are cumulative  *(i.e. the complete list of alternatives produced by a branch is the string-concatenating "Cartesian product" of its parts)*.
* All alternatives (even duplicate and empty ones) are preserved, and they are ordered like the examples demonstrate  *(i.e. "lexicographically" with regard to the alternations)*.
* The alternatives produced by the root branch constitute the final output.

**Parsing** the input string involves some additional complexity to deal with escaped characters and "incomplete" brace pairs:

|  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| a\\{\\\{b,c\,d} | ⟶ | |  |  |  |  |  |  | | --- | --- | --- | --- | --- | --- | | a\\ | |  |  |  | | --- | --- | --- | | ⎧ ⎨ ⎩ | \\\{b | ⎫ ⎬ ⎭ | | c\,d | | |
| {a,b{c{,{d}}e}f | ⟶ | |  |  |  |  |  |  |  | | --- | --- | --- | --- | --- | --- | --- | | {a,b{c | |  |  |  | | --- | --- | --- | | ⎧ ⎨ ⎩ | ‌ | ⎫ ⎬ ⎭ | | {d} | | e}f | |

* An unescaped *backslash* which precedes another character, escapes that character (to force it to be treated as literal). The backslashes are passed along to the output unchanged.
* Balanced *brace pairs* are identified by, conceptually, going through the string from left to right and associating each unescaped closing brace that is encountered with the nearest still unassociated unescaped opening brace to its left (if any). Furthermore, each unescaped *comma* is associated with the innermost brace pair that contains it (if any). With that in mind:
  + Each brace pair that has at least one comma associated with it, forms an alternation (whose branches are the brace pair's contents split at its commas). The associated brace and comma characters themselves do not become part of the output.
  + Brace characters from pairs without any associated comma, as well as unassociated brace and comma characters, as well as all characters that are not covered by the preceding rules, are instead treated as literals.

For every possible input string, your implementation should produce exactly the output which this specification mandates. Please comply with this even when it's inconvenient, to ensure that all implementations are comparable. However, none of the above should be interpreted as instructions (or even recommendations) for **how** to implement it. Try to come up with a solution that is idiomatic in your programming language. *(See #Perl for a reference implementation.)*

Test Cases

:   :   :   | Input *(single string)* | Ouput *(list/array of strings)* |
            | --- | --- |
            | `~/{Downloads,Pictures}/*.{jpg,gif,png}` | `~/Downloads/*.jpg`  `~/Downloads/*.gif`  `~/Downloads/*.png`  `~/Pictures/*.jpg`  `~/Pictures/*.gif`  `~/Pictures/*.png` |
            | `It{{em,alic}iz,erat}e{d,}, please.` | `Itemized, please.`  `Itemize, please.`  `Italicized, please.`  `Italicize, please.`  `Iterated, please.`  `Iterate, please.` |
            | `{,{,gotta have{ ,\, again\, }}more }cowbell!` | `cowbell!`  `more cowbell!`  `gotta have more cowbell!`  `gotta have\, again\, more cowbell!` |
            | `{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}` | `{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}`  `{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}` |

---

Other tasks related to string operations:

Metrics

* Array length
* String length
* Copy a string
* Empty string  (assignment)

Counting

* Word frequency
* Letter frequency
* Jewels and stones
* I before E except after C
* Bioinformatics/base count
* Count occurrences of a substring
* Count how many vowels and consonants occur in a string

Remove/replace

* XXXX redacted
* Conjugate a Latin verb
* Remove vowels from a string
* String interpolation (included)
* Strip block comments
* Strip comments from a string
* Strip a set of characters from a string
* Strip whitespace from a string -- top and tail
* Strip control codes and extended characters from a string

Anagrams/Derangements/shuffling

* Word wheel
* ABC problem
* Sattolo cycle
* Knuth shuffle
* Ordered words
* Superpermutation minimisation
* Textonyms (using a phone text pad)
* Anagrams
* Anagrams/Deranged anagrams
* Permutations/Derangements

Find/Search/Determine

* ABC words
* Odd words
* Word ladder
* Semordnilap
* Word search
* Wordiff  (game)
* String matching
* Tea cup rim text
* Alternade words
* Changeable words
* State name puzzle
* String comparison
* Unique characters
* Unique characters in each string
* Extract file extension
* Levenshtein distance
* Palindrome detection
* Common list elements
* Longest common suffix
* Longest common prefix
* Compare a list of strings
* Longest common substring
* Find common directory path
* Words from neighbour ones
* Change e letters to i in words
* Non-continuous subsequences
* Longest common subsequence
* Longest palindromic substrings
* Longest increasing subsequence
* Words containing "the" substring
* Sum of the digits of n is substring of n
* Determine if a string is numeric
* Determine if a string is collapsible
* Determine if a string is squeezable
* Determine if a string has all unique characters
* Determine if a string has all the same characters
* Longest substrings without repeating characters
* Find words which contains all the vowels
* Find words which contain the most consonants
* Find words which contains more than 3 vowels
* Find words whose first and last three letters are equal
* Find words with alternating vowels and consonants

Formatting

* Substring
* Rep-string
* Word wrap
* String case
* Align columns
* Literals/String
* Repeat a string
* Brace expansion
* Brace expansion using ranges
* Reverse a string
* Phrase reversals
* Comma quibbling
* Special characters
* String concatenation
* Substring/Top and tail
* Commatizing numbers
* Reverse words in a string
* Suffixation of decimal numbers
* Long literals, with continuations
* Numerical and alphabetical suffixes
* Abbreviations, easy
* Abbreviations, simple
* Abbreviations, automatic

Song lyrics/poems/Mad Libs/phrases

* Mad Libs
* Magic 8-ball
* 99 bottles of beer
* The Name Game (a song)
* The Old lady swallowed a fly
* The Twelve Days of Christmas

Tokenize

* Text between
* Tokenize a string
* Word break problem
* Tokenize a string with escaping
* Split a character string based on change of character

Sequences

* Show ASCII table
* De Bruijn sequences
* Summarize and say sequence
* Generate lower case ASCII alphabet

:   * Brace\_expansion\_using\_ranges
assistant
(formerly Perl 6)
The task description allows the taking of shortcuts, but please note that we are not taking any shortcuts here. The solution is short because this particular problem happens to map quite naturally to the strengths of Raku.

First, the parsing is handled with a grammar that can backtrack in the few places this problem needs it. The + quantifier matches one or more alternatives (we handle the case of a single alternative in the walk now), and the % modifier requires a comma between each quantified item to its left. Note that the \* quantifiers do *not* backtrack here, because the token keyword suppresses that; all the backtracking here fails over to a different alternative in an outer alternation (that is, things separated by the | character in the grammar. Most of these failovers just nibble an uninteresting character and continue.)

On the other end, we recursively walk the parse tree returning expanded sublists, and we do the cartesian concatenation of sublists at each level by use of the X~ operator, which is a "cross" metaoperator used on a simple ~ concatenation. As a list infix operator, X~ does not care how many items are on either side, which is just what you want in this case, since some of the arguments are strings and some are lists. Here we use a fold or reduction form in square brackets to interpose the cross-concat between each value generated by the map, which returns a mixture of lists and literal strings. One other thing that might not be obvious: if we bind to the match variable, $/, we automatically get all the syntactic sugar for its submatches. In this case, $0 is short for $/[0], and represents all the submatches captured by 0th set of parens in either TOP or alt. $<meta> is likewise short for $/<meta>, and retrieves what was captured by that named submatch.

```
grammar BraceExpansion {
    token TOP  { ( <meta> | . )* }
    token meta { '{' <alts> '}' | \\ .  }
    token alts { <alt>+ % ',' }
    token alt  { ( <meta> | <-[ , } ]> )* }
}

sub crosswalk($/) {
    |[X~] flat '', $0.map: -> $/ { $<meta><alts><alt>.&alternatives or ~$/ }
}

sub alternatives($_) {
    when :not { () }
    when 1    { '{' X~ $_».&crosswalk X~ '}' }
    default   { $_».&crosswalk }
}

sub brace-expand($s) { crosswalk BraceExpansion.parse($s) }

# Testing:

sub bxtest(*@s) {
    for @s -> $s {
        say "\n$s";
        for brace-expand($s) {
            say "    ", $_;
        }
    }
}

bxtest Q:to/END/.lines;
    ~/{Downloads,Pictures}/*.{jpg,gif,png}
    It{{em,alic}iz,erat}e{d,}, please.
    {,{,gotta have{ ,\, again\, }}more }cowbell!
    a{b{1,2}c
    a{1,2}b}c
    a{1,{2},3}b
    more{ darn{ cowbell,},}
    ab{c,d\,e{f,g\h},i\,j{k,l\,m}n,o\,p}qr
    {a,{\,b}c
    a{b,{{c}}
    {a{\}b,c}d
    END

```

Output:

```
~/{Downloads,Pictures}/*.{jpg,gif,png}
    ~/Downloads/*.jpg
    ~/Downloads/*.gif
    ~/Downloads/*.png
    ~/Pictures/*.jpg
    ~/Pictures/*.gif
    ~/Pictures/*.png

It{{em,alic}iz,erat}e{d,}, please.
    Itemized, please.
    Itemize, please.
    Italicized, please.
    Italicize, please.
    Iterated, please.
    Iterate, please.

{,{,gotta have{ ,\, again\, }}more }cowbell!
    cowbell!
    more cowbell!
    gotta have more cowbell!
    gotta have\, again\, more cowbell!

{}} some {\\{edge,edgy} }{ cases, here\\\}
    {}} some {\\edge }{ cases, here\\\}
    {}} some {\\edgy }{ cases, here\\\}

a{b{1,2}c
    a{b1c
    a{b2c

a{1,2}b}c
    a1b}c
    a2b}c

a{1,{2},3}b
    a1b
    a{2}b
    a3b

more{ darn{ cowbell,},}
    more darn cowbell
    more darn
    more

ab{c,d\,e{f,g\h},i\,j{k,l\,m}n,o\,p}qr
    abcqr
    abd\,efqr
    abd\,eg\hqr
    abi\,jknqr
    abi\,jl\,mnqr
    abo\,pqr

{a,{\,b}c
    {a,{\,b}c

a{b,{{c}}
    a{b,{{c}}

{a{\}b,c}d
    {a\}bd
    {acd
```