16
\$\begingroup\$

A brace string is defined as a string consisting of the characters *()[] in which braces match correctly:

[brace-string] ::= [unit] || [unit] [brace-string]
[unit]         ::= "" || "*" || "(" [brace-string] ")" || "[" [brace-string] "]"

This is a valid brace-string:

((())***[]**)****[(())*]*

But these are not:

)(
**(**[*](**)
**([*)]**

Your task is to write a program (or function) that, given a positive integer n, takes a number as input and outputs (or returns) all valid brace strings of length n.

Specifications

  • You may output the strings in any order.
  • You may output as a list or a string separated by a different character.
  • Your program must handle 0 correctly. There is 1 possible brace-string of length 0, which is the empty string "".
  • This is , so the shortest valid answer – measured in bytes – wins.

Test Cases

0. 
1. *
2. ** () []
3. *** ()* []* (*) [*] *() *[]
4. **** ()** []** (*)* [*]* (**) **() **[] *(*) *[*] (()) ()() ()[] ([]) [**] [()] [[]] []() [][] *()* *[]*
\$\endgroup\$
  • 3
    \$\begingroup\$ The number of entries in the output is A025235 \$\endgroup\$ – Gabriel Benamy Nov 30 '16 at 3:48
  • \$\begingroup\$ @GabrielBenamy Ah. I was wondering whether that had been looked at before. Interesting. \$\endgroup\$ – Esolanging Fruit Nov 30 '16 at 5:57
  • 2
    \$\begingroup\$ What is the winning condition? I assume shortest program (code golf). \$\endgroup\$ – Zgarb Nov 30 '16 at 7:46
  • \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender Nov 30 '16 at 7:59
  • 1
    \$\begingroup\$ Since everyone is assuming this is code golf, I will tag the challenge accordingly (as it would otherwise make all existing answers somewhat pointless). If you intended a different winning criterion, you could consider posting a new challenge. \$\endgroup\$ – Martin Ender Nov 30 '16 at 9:04

10 Answers 10

3
\$\begingroup\$

Jelly, 29 bytes

-3 bytes thanks to @JonathanAllan

Please, alert me if there are any problems/bugs/errors or bytes I can knock off!

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ

Try it online!

The previous solution(s) I had:

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐLµ€Ṇ€×Jḟ0ị

Explanation (My best attempt at a description):

Input n
“[(*)]”ṗ-All strings composed of "[(*)]" of length n
µḟ”*    -Filter out all occurences of "*"
œṣ⁾()   -Split at all occurences of "()"
F       -Flatten
œṣ⁾[]   -Split at all occurences of "[]"
F       -Flatten
µÐL     -Repeat that operation until it gives a duplicate result
Ðḟ      -Filter
\$\endgroup\$
  • \$\begingroup\$ You can save three bytes using filtering (“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ) \$\endgroup\$ – Jonathan Allan Sep 9 '17 at 21:55
15
\$\begingroup\$

Prolog, 69 bytes

s-->[];e,s.
e-->"*";"(",s,")";"[",s,"]".
b(N,A):-length(A,N),s(A,[]).

One of the most interesting properties of Prolog is that in many cases it's capable of running a program backwards; for example, instead of testing to see if something's true, you can generate all solutions for which it's true, and instead of checking the length of a string, you can generate all strings with a given length. (Another nice property of Prolog is that it requires whitespace after the end of each predicate definition, and a newline can be inserted as cheaply as a space; thus even golfed programs are often fairly readable.)

The above defines a predicate (the equivalent of a function) b which tests to see if a string has a given length and is a "brace string" as defined in the question. Specifically, it does this via Prolog's grammar/regex/pattern-match support that gives some nice, short sugar for defining this sort of expression (apparently this is standard/portable, but I was unaware of this while originally writing the answer, and thus assumed the answer would work on only one Prolog implementation; it seems it works on every implementation that complies with the standards, though). The program can be translated into English fairly directly; the first two lines say "an s is an empty string, or an e followed by an s; an e is an asterisk, or an s in parentheses, or an s in square brackets". The third line can be interpreted as "The b of N can be A if A is a list with length N and A is an s followed by a null string."

I took some care to write s (and thus b) so that they match each "brace string" in exactly one way (which is the reason that both s and e have to exist, rather than grouping them into one predicate). This makes them both entirely reversible; thus b can be used to generate all "brace strings" of a given length, in addition to testing if a string is a brace string of a given length (it can also be used a third way round, to figure out the length of a brace string, but that is almost certainly its least useful mode of operation). The implementation is recursive, e.g. to generate an s, the code will generate all possible es that are no longer than the required length of the output, and append all possible ss that fit in the remaining space to them; because I specified the length of the argument in advance (within b), the Prolog engine knows that it can't generate output that's longer than the given length, which allows the recursion to terminate.

Here's an example of the program in operation:

| ?- b(4,A),format("~s ",[A]),fail.
**** **() **[] *()* *(*) *[]* *[*] ()** ()() ()[] (*)* (**) (()) ([]) []** []() [][] [*]* [**] [()] [[]]
\$\endgroup\$
  • \$\begingroup\$ it feels like there should be some cost to the syntax required to specify whether you want to run the program "forwards" or "backwards". perl pays 1 byte for every bit of that sort of thing \$\endgroup\$ – Sparr Nov 30 '16 at 2:43
  • \$\begingroup\$ Well, you could make a rule that arguments at the end are always the return value, then reverse the order of the arguments to specify which way round you're running the program. It's fairly common for golfing languages to figure out what they should be doing partly by looking at whether they were given any input, and this is a comparable principle. In general, though, it's hard to make rules that apply to every possible language; running builtins like length and append either way round is a fundamental part of the language, and user functions often do the same. \$\endgroup\$ – user62131 Nov 30 '16 at 6:12
  • \$\begingroup\$ Oh, hmm. I assumed there was some indication in your example that triggered the behavior in question. \$\endgroup\$ – Sparr Nov 30 '16 at 7:16
  • \$\begingroup\$ Nah, it's entirely due to which arguments are given. In the program above, I write length(A,N); if N is given and A isn't (which will happen if the predicate's used in the way requested in the program), length will generate a list A consisting of N unknown elements. Using length to measure the length of a list is probably more commonly used (although using it "backwards" is fairly common in Prolog programming). Most predicates end up working much the same way (the only reason they don't is if attempting to reverse them would construct an infinite loop, which is fairly common). \$\endgroup\$ – user62131 Nov 30 '16 at 7:21
  • 1
    \$\begingroup\$ @ais523 --> and DCGs in general are standard ISO Prolog. \$\endgroup\$ – Fatalize Nov 30 '16 at 11:13
5
\$\begingroup\$

Haskell, 101 94 bytes

7 bytes saved by Zgarb!

b 0=[""]
b n=[x++y|k<-[1..n],x<-u k,y<-b$n-k]
u 1=["*"]
u n=[a:s++b|s<-b$n-2,a:b<-["()","[]"]]

Almost straightforward, following the definition, but with the "" case moved.

Use:

*Main> map b [0..3]
[[""],["*"],["**","()","[]"],["***","*()","*[]","()*","[]*","(*)","[*]"]]
*Main> length $ b 10
21595

(The second computation takes less than a second on a slow machine.)

I'd also like to share the result of another approach I came up with while thinking about generating functions. It defines a list b of lists of strings such that b!!n contains all brace-strings of length n. Similarly, u!!n contains all atoms of size n-1. One nice thing is that the code is not using any numbers. It is not completely golfed: u and i could be inlined, and it certainly misses a few other golfing opportunities. Unfortunately, it doesn't look like it can be made shorter than the first version, but it computes length $ b !! 10 even faster.

b=[""]:b%u
u=["*"]:map i b
i=concatMap(\s->['(':s++")",'[':s++"]"])
(b:c)%f=zipWith(++)[[x++y|x<-b,y<-e]|e<-f]([]:c%f)
\$\endgroup\$
  • \$\begingroup\$ Save two bytes with b$n-k and b$n-2. Also, on the final line you can do a:b<-["()","[]"] and return a:s++b. \$\endgroup\$ – Zgarb Nov 30 '16 at 8:38
  • \$\begingroup\$ Oh I wanted to use ["()","[]"] but couldn't see how to improve code size with it. Thanks! \$\endgroup\$ – Christian Sievers Nov 30 '16 at 13:42
4
\$\begingroup\$

Mathematica, 116 bytes

#<>""&/@Select[Characters@"*([)]"~Tuples~#,(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&]&

Explanation

Characters@"*([)]"

Find the characters of the string "*([)]", giving the List {"*", "(", "[", ")", "]"}.

... ~Tuples~#

Find the tuples of the above list with length n.

(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&

Unnamed Boolean function to find whether the tuple is balanced:

#/."*"->Nothing

Delete all "*" in the input.

... //.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b}

Repeatedly delete all consecutive occurrences of "(" and ")" or "[" and "]" until the input does not change.

... =={}

Check whether the result is an empty List.

Select[ ... , ... ]

Find the tuples that give True when the Boolean function is applied.

#<>""&/@

Convert each List of characters into Strings.

\$\endgroup\$
  • 2
    \$\begingroup\$ Somewhat unexpectedly, {x=a___,"(",")",y=b___}|{x,"[","]",y} seems to work. \$\endgroup\$ – Martin Ender Nov 30 '16 at 12:16
4
\$\begingroup\$

Python 2, 128 bytes

n=input()
for i in range(5**n):
 try:s=','.join('  "00([*])00"  '[i/5**j%5::5]for j in range(n));eval(s);print s[1::4]
 except:1

Screw recursive regexes – we’re using Python’s parser! In order to verify that, for example, *(**[])* is a brace-string, we do the following:

  1. Make a string like "*", (0,"*","*", [0,0] ,0) ,"*", where every second character of four is a character from the brace-strings, and the remaining characters are glue to make this a potential Python expression.

  2. eval it.

  3. If that doesn’t throw an error, print s[1::4] (the brace-string characters).

The glue characters are picked so that the string I make is a valid Python expression if and only if taking every second character out of four yields a valid brace-string.

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

PHP, 149 bytes

for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));

Uses the good old generate all possible and then filter method. Use like:

php -r "for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));" 4
\$\endgroup\$
1
\$\begingroup\$

Python, 134 bytes

from itertools import*
lambda n:[x for x in map(''.join,product('*()[]',repeat=n))if''==eval("x"+".replace('%s','')"*3%('*',(),[])*n)]

repl.it

Unnamed function that returns a list of valid strings of length n.
Forms all length n tuples of the characters *()[], joins them into strings using map(''.join,...) and filters for those that have balanced brackets by removing the "pairs" "*", "()", and "[]" in turn n times and checking that the result is an empty string (n times is overkill, especially for "*" but is golfier).

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

Retina, 78 bytes

Byte count assumes ISO 8859-1 encoding.

.+
$*
+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]
%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

A`;

Try it online!

Explanation

I'm generating all possible strings of length 5 and then I filter out the invalid ones.

.+
$*

This converts the input to unary, using 1 as the digit.

+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]

This repeatedly (+) replaces the first (1) one in each line (%) in such a way that it makes five copies of the line, one for each possible character. This is done by using the prefix and suffix substitutions, $` and $' to construct the remainder of each line.

This loop stops when there are no more 1s to replace. At this point we've got all possible strings of length N, one on each line.

%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

These two stages are executed for each line separately (%). The first stage simply duplicates the line, with a ; to separate the two copies.

The second stage is another loop (+), which repeatedly removes [], () or * from the first copy of the string, or removes a semicolon at the beginning of the line (which is only possible after the string has vanished completely).

A`;

Valid strings are those that no longer have a semicolon in front of them, so we simply discard all lines (A) which contain a semicolon.

\$\endgroup\$
  • \$\begingroup\$ I tried onliny with input 5: ok. With input 6 I got an error page \$\endgroup\$ – edc65 Nov 30 '16 at 10:49
  • \$\begingroup\$ @edc65 Works for me, but of course this approach is not exactly efficient, so it takes a few seconds. What sort of error page do you mean? \$\endgroup\$ – Martin Ender Nov 30 '16 at 11:03
  • \$\begingroup\$ Input 5: answer in 3 sec. Input 6: after 7 seconds, Inside the Output box, I get the html source of what is probably an error page from my proxy. If it's a timeout then it's a very short timeout ... I was trying to get a right test case for input 6, as I my answer seems ok up to input 5, but wrong for 6 or more \$\endgroup\$ – edc65 Nov 30 '16 at 11:33
  • \$\begingroup\$ @edc65 It definitely takes longer than 7 seconds, and TIO's timeout is a minute. I've never seen the error you describe, might be worth bringing this up in the TIO chat (or if you prefer on gitter or GitHub). As for reference output, here is what I get for input 6: pastebin.com/WmmPPmrc (Input 7 takes more than a minute.) \$\endgroup\$ – Martin Ender Nov 30 '16 at 12:06
1
\$\begingroup\$

Python 3.5, 146 bytes

import re;from itertools import*;lambda f:{i for i in map(''.join,permutations("[()]*"*f,f))if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)}

Very long compared to other answers, but the shortest one I could currently find. It is in the form of an anonymous lambda function and therefore must be called in the format

print(<Function Name>(<Integer>))

Outputs a Python set of unordered strings representing all possible brace-strings of the input length.

For example, assuming the above function is named G, invoking G(3) would result in the following output:

{'[*]', '*()', '*[]', '(*)', '***', '[]*', '()*'}

Try It Online! (Ideone)


However, if, like me, you aren't really a fan of simplifying things using built-ins, then here is my own original answer not using any external libraries to find permutations, and currently standing at a whopping 288 237 bytes:

import re;D=lambda f:f and"for %s in range(%d)"%(chr(64+f),5)+D(f-1)or'';lambda g:[i for i in eval('["".join(('+''.join('"[()]*"['+chr(o)+'],'for o in range(65,65+g))+'))'+D(g)+']')if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)]

Again, like the competing answer, this one is in the form of a lambda function and therefore must also be called in the format

print(<Function Name>(<Integer>))

And outputs a Python list of unsorted strings representing all brace-strings of the input length. For example, if the lambda were to be invoked as G(3), this time the output would be the following:

['*()', '(*)', '*[]', '[*]', '()*', '[]*', '***']

Also, this one is also a lot faster than my other answer, being able to find all brace-strings of length 11 in about 115 seconds, those of length 10 in about 19 seconds, those of length 9 in about 4 seconds, and those of length 8 in about 0.73 seconds on my machine, whereas my competing answer takes much longer than 115 seconds for an input of 6.

Try It Online! (Ideone)

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

05AB1E, 23 bytes

…[(*.∞sãʒ'*м„()„[]‚õ:õQ

Some of these features might have been implemented after the question was posted. Any suggestions are welcome!

Try it online!

How?

…[(* - the string '[(*'
.∞ - intersected mirror, '[(*'=>'[(*)]'
s - swap the top two items, which moves the input to the top
ã - cartesian power
ʒ ...  - filter by this code:
  '*м      - remove all occurrences of '*'
  „()„[]‚  - the array ["()","[]"]
  õ        - the empty string ""
  :        - infinite replacement (this repeatedly removes "()", "[]", and "*" from the string
  õQ       - test equality with the empty string
\$\endgroup\$
  • \$\begingroup\$ I don't know 05AB1E, but couldn't the * also be in the removal array? And could the õQ check be replaced with something like NOT? \$\endgroup\$ – Esolanging Fruit Sep 10 '17 at 19:44
  • \$\begingroup\$ The first suggestion won't save any bytes: '*м„()„[]‚õ: vs „()„[]‚'*«õ: (not tested), since there is no command to concatenate 3 values AFAIK. The second one won't work since there's no NOT that would operate like that on a string, AFAIK. (Where AFAIK represents "as far as I know") \$\endgroup\$ – Zacharý Sep 10 '17 at 20: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.