5
\$\begingroup\$

We already have challenges to check if a string of brackets is fully matched and to count the number of balanced strings. It remains for us to generate these strings, but it will not be so easy…

A Dyck word is a string, of length 2n, consisting of n opening and n closing parentheses (( and )) fully matched (that is to say: for all prefixes of the string, the number of opening parentheses is greater than or equal to the number of closing ones).

It is interesting to note that the number of different Dyck words of length 2n is equal to the (n + 1)-th Catalan number.

It’s pretty straightforward to write a program that generates these words with a recursive function. But the goal here is to do the same thing without.

Challenge

Write a full program or function that takes a positive integer, n, using stdin or an acceptable alternative, and outputs all the different Dyck words of length 2n. The words can appear in any order and each must be separated from each other by a line break. Moreover, your program should not use recursive functions (see details below).

Rules

  • The output of your program should only contain Dyck words of length 2n, separated by line breaks. Each word must appear only once.
  • Your program must work at minimum for inputs 0 to 15.
  • You may not write recursive functions, neither direct (a function that calls itself) nor indirect (e.g. a function f that calls another function g that calls function f). That being said, you can still use the standard functions of your language without worry of how they work internally.
  • Similarly, your program should not call itself.
  • You may not use non-standard librairies.
  • Your program may not read or write files.
  • Your program must be able to run in a reasonable time for 0 ≤ n ≤ 15 (hence, naively generate all arrangements is probably not a good idea). Let’s say less than 20 minutes with a memory limit of 4 GB (my reference implementation in C manages n = 15 in less than 5 seconds).
  • All standard loopholes are forbidden.

As usual in , the shortest code in bytes wins. But if you have found an interesting way to achieve this challenge in your language, please do not hesitate.

Test I/O

For this input:

3

The output could be (any other order is correct too):

((()))
()()()
(()())
(())()
()(())
\$\endgroup\$
  • 4
    \$\begingroup\$ This is a very interesting challenge. but most of the rules make it worse. For example You may not write recursive functions Why not? Similarly, your program should not call itself. Why not? Your program may not read or write files. Submissions are unlikely to, but why not? That also goes against our default allowed IO methods. Also, it is standard to allow functions rather than just full programs. \$\endgroup\$ – DJMcMayhem Jun 28 '16 at 17:33
  • 4
    \$\begingroup\$ I think you may be falling into the trap of assuming languages are all similar. I think as it stands this challenge is too broad, as I will be totally uncertain as to what would count as valid "emulation" of recursion vs the banned actual recursion, in say stack based languages. \$\endgroup\$ – FryAmTheEggman Jun 28 '16 at 17:50
  • 8
    \$\begingroup\$ This challenge hits too many things to avoid: Needless fluff with the extra conditions, Do X without Y and disadvantaging functional languages by patching out recursion, chameleon challenges with the minor-seeming time/space requirement actually being a big limitation. \$\endgroup\$ – xnor Jun 29 '16 at 0:09
  • 5
    \$\begingroup\$ For a first challenge, I think you're off to a good start, but in the future I recommend less micromanaging requirements. \$\endgroup\$ – xnor Jun 29 '16 at 0:10
  • 4
    \$\begingroup\$ It appears no one has pointed out the sandbox yet. For future challenges, I recommend giving it a try: you post a challenge specification there instead of here and can get feedback and iron out some of the details before the challenge goes live and people start working on/answering it. That can help avoid a lot of frustration for everyone and often results in an overall better challenge. \$\endgroup\$ – Martin Ender Jun 29 '16 at 11:15

11 Answers 11

5
\$\begingroup\$

Pyth, 26 23 bytes

jeuaGsMs*VjRL`()_GGQ]]k

Try it online

                    ]]k   starting at G=[['']],
  u                Q      repeat the given number of times:
                _G          reversed G
          jRL`()            parenthesize each level-2 element
        *V        G         take Cartesian products of corresponding
                              elements of that and G
       s                    concatenate, yielding a list of pairs
     sM                     concatenate each resulting pair
   aG                       append the resulting list to G
je                        finally, join the last result on newlines

This directly follows the Catalan recurrence (with a non-recursive dynamic programming implementation) and doesn’t use any filtering. On my laptop, it runs in 55 seconds using 2.67 GiB RAM for n = 15.

Pyth, 33 bytes, O(n) memory

=S*Q`()Wn2J+3x
Q"(()"=+.<S<QJ1>QJ

Try it online

  *Q`()                  build a string with Q copies of "()"
 S                       sort it
=                        assign it to Q

       W                 while the following is true:
(newline)                  print Q
Q
             x             take the index of the first occurrence of "(()"
 "(()"
           +3              add 3
          J                assign to J
        n2                 is this not equal to 2 (i.e. was "(()" found)?
                         do the following:
           <QJ             take the first J characters of Q
          S                sort them
        .<    1            cyclically shift them left by 1
       +       >QJ         add the remaining characters of Q
      =                    assign to Q

This algorithm outputs all Dyck words in a stream, with each word being generated from the previous one and no additional state. On my laptop, it runs in 170 seconds using basically no RAM for n = 15.

As an example illustrating how it works:

()()()()((()()(())))(())
         ^^^               becomes
(((((()))))(()(())))(())

Similarly computing the words in the reverse of this order also takes 33 bytes:

=*QK`()WJhx
Q_K=+t.iFc2_<QJ+K>QhJ

Try it online

\$\endgroup\$
  • \$\begingroup\$ Nice answer! Well done for the generation of a word from the previous one, it was also the spirit of my solution. \$\endgroup\$ – mlpo Jun 29 '16 at 15:17
6
\$\begingroup\$

C99, 105 bytes

i,j,s;f(n){for(char a[31]={};++i%(1<<2*n);s||puts(a))for(j=s=0;~s&&j<2*n;)s+=1-(a[j]=40+(i>>j++)%2)%2*2;}

Iterates over all strings of 2n parentheses.

With piped output and compiler flag -O3, input n = 15 takes roughly 15.5 seconds on my machine. Memory consumption is 1.2 MB.

Test it on Ideone.

\$\endgroup\$
  • \$\begingroup\$ It takes a bit more than 1 minute here. This answer seems valid. It is possible to have a more efficient approach than generate all arrangements, but I'm not sure that it is shorter to write. \$\endgroup\$ – mlpo Jun 28 '16 at 20:35
  • 1
    \$\begingroup\$ Well, I precisely chose C because I thought I could get away with a brute-force approach, and I wasn't disappointed. The last edit (125 to 124) doubles the run time by the way. \$\endgroup\$ – Dennis Jun 28 '16 at 20:36
  • 1
    \$\begingroup\$ Breaking out of the inner loop as soon as there's an unmatched ) lowered the run time to one fourth and reduced the byte count. \$\endgroup\$ – Dennis Jun 28 '16 at 21:14
5
\$\begingroup\$

CJam (48 bytes)

ri"()"*${_p_,{1$>_)-,\(-,<},_{W=/(\s$1m>+}{&}?}h

Online demo. This effectively takes one obvious recursive solution and makes it iterative. Instead of actually simulating the steps back up the stack, it applies a successor rule:

Find the last ( which starts a suffix with strictly more ) than (; sort that suffix, and rotate once.

Note that this is deliberately designed to avoid keeping the full list of solutions in memory, because I don't think it fits (at least, not if run on a 64-bit machine. It might on a 32-bit machine). There are 9694845 Dyck paths for n=15, so that's 30*9694845 characters, and 92*9694845 = 891925740 bytes of memory just for the (Java) String objects. But then the List holding the objects probably wraps an array with space for 16777216 elements, which is a further 256MB, and the CJam interpreter itself seems to add quite a bit of overhead.


(42 bytes)

Ma{{_'(+\')+}%{"()"\f{\-,}I+_$=},}ri:I2**,

This builds the strings up one character at a time, filtering to ensure that no string has more than n opening parentheses or more closing than opening parentheses. However, it runs out of memory with 3GB for n=15.

The same idea at 39 bytes, but this runs out of memory earlier.

Ma{"()":Sm*::+{S\f{\-,}I+_$=},}ri:I2**`

Online demo


(24 bytes)

My original answer, now disqualified by rule changes.

{"()"*e!{0\+{~_}*]1&!},}

This is an anonymous function which takes input on the stack. Online demo.

It works by the obvious approach of taking all permutations of n pairs of parentheses and filtering for those which are balanced.

\$\endgroup\$
  • \$\begingroup\$ Unless I am mistaken, this answer does not meet the seventh rule. I can not run the code in a reasonable time for n ≥ 10. \$\endgroup\$ – mlpo Jun 28 '16 at 18:21
  • 2
    \$\begingroup\$ @mlpo "Reasonable" is extremely subjective. To make that rule enforcable, you should specify time and memory limits. \$\endgroup\$ – Dennis Jun 28 '16 at 18:32
  • 6
    \$\begingroup\$ @mlpo, online demos are always only for really small test cases. Running it locally on my 4-year-old computer, it computes n=12 in 3m13s, although it does run out of memory with a 1GB heap on n=13. I'm currently testing an alternative approach which seems like it should be less brute force but is actually turning out to be much slower. I'm not entirely sure what to make of "the algorithm is exponential". The output is exponential. No sub-exponential answer could meet spec! \$\endgroup\$ – Peter Taylor Jun 28 '16 at 18:46
  • 1
    \$\begingroup\$ @PeterTaylor I'm not too sure n=12 in 3m13s means fulfilling the criteria. My solution in pyth ran n=12 in 22s on my machine, but n=15 about 18minutes. \$\endgroup\$ – busukxuan Jun 28 '16 at 20:32
  • 1
    \$\begingroup\$ @busukxuan, yes, but that version was written before the criteria, and it took me a while to beat the criteria and update the answer. \$\endgroup\$ – Peter Taylor Jun 29 '16 at 21:40
4
\$\begingroup\$

JavaScript (ES6), 125 bytes

n=>{for(i=m=1<<n+n-1;i&m;i++){for(j=m,z=o=0;o>=z;j>>=1)i&j?o++:z++;o-n||console.log(i.toString(2).replace(/./g,d=>")("[d]))}}

Actually printing the results slows things down horribly, but with console.log set to ()=>{} this takes my machine about 7 seconds for n=12, which presumably translates to 7 minutes for n=15. If that's not fast enough, you can replace i++ with i+=2 or even i+=j||2 but that made only a few percent difference in my testing. Works by generating all 2n-digit binary numbers and checking whether they represent a Dyck word. Ungolfed:

function dyck(n) {
    // Don't bother generating words that begin with ),
    // so start half-way though 4 ** n.
    for (var i = 4 ** n / 2; i < 4 ** n; i += 2) {
        // Convert to the string of ()s.
        var word = i.toString(2);
        word = word.replace(/1/g, "(");
        word = word.replace(/0/g, ")");
        // Count the (s and )s separately.
        var left = 0;
        var right = 0;
        for (var j = 0; j < n + n; j++) {
            if (word[j] == "(") left++;
            else right++;
            // Abort if there are too many )s
            if (right > left) break;
        }
        // If we got exactly n (s then it's a Dyck word.
        if (left == n) console.log(word);
    }
}
\$\endgroup\$
3
\$\begingroup\$

C, 748 746 651 bytes

#define C(v,n) for(v=n==D;v<=(n<=D);v++)
void p(Z){unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;C(C,30)C(B,29)C(A,28)C(z,27)C(y,26)C(x,25)C(w,24)C(v,23)C(u,22)C(t,21)C(s,20)C(r,19)C(q,18)C(p,17)C(o,16)C(n,15)C(m,14)C(l,13)C(k,12)C(j,11)C(i,10)C(h,9)C(g,8)C(f,7)C(e,6)C(d,5)C(c,4)C(b,3)C(a,2){R=C<<29|B<<28|A<<27|z<<26|y<<25|x<<24|w<<23|v<<22|u<<21|t<<20|s<<19|r<<18|q<<17|p<<16|o<<15|n<<14|m<<13|l<<12|k<<11|j<<10|i<<9|h<<8|g<<7|f<<6|e<<5|d<<4|c<<3|b<<2|a<<1;if(__builtin_popcount(R)!=Z)goto X;F=0;for(E=D-1;E;E--)if(R&1<<E)F++;else if(F)F--;else goto X;for(;E<D;E++)putchar(40+!(R&1<<D-E-1));puts("");X:;}}

At a whopping >600 bytes, this isn't really much of a contender...but it's pretty fast and memory efficient.

Works by encoding the parentheses strings as integers, with a set bit representing ( and an unset bit representing ). For instance, (()) would be 1100. I made the following observations:

  • All permutations must begin with ( and end with ); otherwise, it won't be valid.
  • Every valid permutation must have n left parentheses and n right parentheses, where n is the input number. I used __builtin_popcount for this.

When built via icc -march=native -O3, it takes 17s on my computer, though others have reported better times (~3-7s) on their (presumably faster) computers. In addition, it uses around 1.5 KB of memory.

Here's the code with explanatory comments:

// Z is the input number.
void p(Z){
    // All the variables.
    // R is the resulting paren number, with 1 bits for open parens and 0s for closed ones.
    // a-C are used to hold the state of each paren (1 if open, 0 if closed).
    // D holds Z*2, or the total length of the paren string.
    // E and F are used later on.
    unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;
    /* Each loop performs a basic check. If D is equal to the corresponding
       number, then the variable will start at 1 (since the first paren must
       always be open). If D is greater than or equal to the number, then the loop
       will only be run once with the variable set to 0, and a later check will
       cause the variable to be ignored. Otherwise, it will loop twice; one for a
       closed paren (0), and one for an open one (1). Of course, if D == the
       number, then it will only loop for the open paren (as stated above). */
    for (C = (D == 30); C <= (30 <= D); C++)
    for (B = (D == 29); B <= (29 <= D); B++)
    for (A = (D == 28); A <= (28 <= D); A++)
    for (z = (D == 27); z <= (27 <= D); z++)
    for (y = (D == 26); y <= (26 <= D); y++)
    for (x = (D == 25); x <= (25 <= D); x++)
    for (w = (D == 24); w <= (24 <= D); w++)
    for (v = (D == 23); v <= (23 <= D); v++)
    for (u = (D == 22); u <= (22 <= D); u++)
    for (t = (D == 21); t <= (21 <= D); t++)
    for (s = (D == 20); s <= (20 <= D); s++)
    for (r = (D == 19); r <= (19 <= D); r++)
    for (q = (D == 18); q <= (18 <= D); q++)
    for (p = (D == 17); p <= (17 <= D); p++)
    for (o = (D == 16); o <= (16 <= D); o++)
    for (n = (D == 15); n <= (15 <= D); n++)
    for (m = (D == 14); m <= (14 <= D); m++)
    for (l = (D == 13); l <= (13 <= D); l++)
    for (k = (D == 12); k <= (12 <= D); k++)
    for (j = (D == 11); j <= (11 <= D); j++)
    for (i = (D == 10); i <= (10 <= D); i++)
    for (h = (D == 9); h <= (9 <= D); h++)
    for (g = (D == 8); g <= (8 <= D); g++)
    for (f = (D == 7); f <= (7 <= D); f++)
    for (e = (D == 6); e <= (6 <= D); e++)
    for (d = (D == 5); d <= (5 <= D); d++)
    for (c = (D == 4); c <= (4 <= D); c++)
    for (b = (D == 3); b <= (3 <= D); b++)
    for (a = (D == 2); a <= (2 <= D); a++) {
        /* R is the result here. Each variable is shifted and bitwise-ORd with the
           others to generate a number representing the string.

           For instance, (()) would be 1100, and ()(()) would be 101100. */
        R=C<<29|B<<28|A<<27|z<<26|y<<25|x<<24|w<<23|v<<22|u<<21|t<<20|s<<19|r<<18|
          q<<17|p<<16|o<<15|n<<14|m<<13|l<<12|k<<11|j<<10|i<<9|h<<8|g<<7|f<<6|
          e<<5|d<<4|c<<3|b<<2|a<<1;
        // If there is an uneven balance of parens, then just jump to the loop end.
        if(__builtin_popcount(R)!=Z) goto X;
        // F here is the number of opening parens.
        F=0;
        // E is a counter used to extract each bit.
        for(E=D-1;E;E--)
            // If the bit is set, then increment the number of open parens.
            if(R&1<<E) F++;
            // If the bit wasn't set, then decrement the number of open parens...
            else if(F) F--;
            // ...but, if there were no open parens, then it's unbalanced; jump to the end
            else goto X;
        // E (the bit counter) is already 0.
        // Loop through each bit...
        for(;E<D;E++)
            /* ...and print it out. 40 is the ASCII code for `(`. If the bit
               is set, the ! will negate it, and 0 will be added to the `(`.
               Otherwise, it will turn the left paren into a right paren. */
            putchar(40+!(R&1<<D-E-1));
        // Newline.
        puts("");
        // End of loop.
        X:;
    }
}

746-byte version

#define C(v,n) for(v=(n==D);v<=(n<=D);v++){
void p(Z){unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;C(C,30)C(B,29)C(A,28)C(z,27)C(y,26)C(x,25)C(w,24)C(v,23)C(u,22)C(t,21)C(s,20)C(r,19)C(q,18)C(p,17)C(o,16)C(n,15)C(m,14)C(l,13)C(k,12)C(j,11)C(i,10)C(h,9)C(g,8)C(f,7)C(e,6)C(d,5)C(c,4)C(b,3)C(a,2)R=(C<<29)|(B<<28)|(A<<27)|(z<<26)|(y<<25)|(x<<24)|(w<<23)|(v<<22)|(u<<21)|(t<<20)|(s<<19)|(r<<18)|(q<<17)|(p<<16)|(o<<15)|(n<<14)|(m<<13)|(l<<12)|(k<<11)|(j<<10)|(i<<9)|(h<<8)|(g<<7)|(f<<6)|(e<<5)|(d<<4)|(c<<3)|(b<<2)|(a<<1);if(__builtin_popcount(R)!=Z)continue;F=0;for(E=D-1;E;E--)if(R&(1<<E))F++;else if(F)F--;else goto X;for(;E<D;E++)putchar('('+!(R&(1<<D-E-1)));puts("");X:;}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
\$\endgroup\$
  • \$\begingroup\$ Nice. 7 seconds here with gcc -O3 -march=native -ffast-math -DNDEBUG. \$\endgroup\$ – mlpo Jun 29 '16 at 17:15
  • 2
    \$\begingroup\$ This is quite fast (3.5 seconds on my machine) and memory-friendly (time says 1.3 MB), but I'm not sure it is a serious contender in a code golf competition... \$\endgroup\$ – Dennis Jun 29 '16 at 18:09
  • \$\begingroup\$ You can easily save 100 bytes by removing the { from the marco (only the inner loop needs it), removing the parens around the bitshifts (|'s predence is lower) and (with a speed hit) declaring the variables in the global scope where they'll default to int. \$\endgroup\$ – Dennis Jun 30 '16 at 23:21
  • \$\begingroup\$ Re speed difference: Depending on which OS you use, gcc could be a lot faster (or slower) than icc. \$\endgroup\$ – Dennis Jun 30 '16 at 23:22
  • \$\begingroup\$ No big deal, My JS answer ported to C is about 220, bytes 5 seconds and begligible ram use \$\endgroup\$ – edc65 Jul 1 '16 at 7:04
2
\$\begingroup\$

Python 2, 117 116 bytes

def f(n):r='',;exec"r=[s+c for s in r for t in[s.count('(')]for c in')('[t+t==len(s):2-t/n]];"*2*n;print'\n'.join(r)

This builds the strings character by character, without filtering.

With piped output and input n = 15, this takes roughly 39 seconds with CPython and 7.5 seconds with PyPy on my machine. Memory consumption is 1.6 GB with CPython and 2.5 GB with PyPy.

Test it on Ideone.

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

JavaScript (ES6), 203

Implementing this algorithm (point 3, totally iterative)

Within the limits of script executing in Firefox, I managed to have the 200K console output for input 12 in about 1.5 minutes

n=>{
for(b=[...Array(n)].map((_,i)=>1+2*i),z=0;!z;)
for(c=[...'('.repeat(n+n)],b.map(n=>c[n]=')'),console.log(c.join``),z=i=n;i--&&z;)
if(b[i]<n+i)for(z=0,b[j=i]++;++j<n-1;)b[j]=Math.max(b[j-1],2*j)+1
}

Less golfed

n=>{
  b=[...Array(n)].map((_,i)=>1+2*i)
  q=0
  for(z=0;!z;)
  {
    c=[...'('.repeat(n+n)],
    b.map(n=>c[n]=')'),
    console.log(++q,c.join``)
    for(z=i=n;i--&&z;)
      if(b[i]<n+i)
        for(z=0,b[j=i]++;++j<n-1;)
          b[j]=Math.max(b[j-1],2*j)+1
  }
}

Ported to C just for fun, run in 5 secs for input 15 (it compiles and works without #includes)

f(n){int i,j,z,b[49];char c[99];
for(i=n;i--;)b[i]=2*i+1;
for(z=0;!z;){memset(c,40,n+n);c[n+n]=0;
for(i=n;i--;)c[b[i]]=41;puts(c);
for(z=i=n;i--&&z;)if(b[i]<n+i)for(z=0,b[j=i]++;++j<n;)b[j]=(b[j-1]>2*j?b[j-1]:2*j)+1;
}}

Test generating all output but do not display it, just counting output rows

I got 90 sec for input 15

F=n=>{
for(b=[...Array(n)].map((_,i)=>1+2*i),z=0;!z;)
for(c=[...'('.repeat(n+n)],b.map(n=>c[n]=')'),console.log(c.join``),z=i=n;i--&&z;)
if(b[i]<n+i)for(z=0,b[j=i]++;++j<n-1;)b[j]=Math.max(b[j-1],2*j)+1
}

console.log=x=>o++ // console.log display no output, just count rows

function test() {
  n=+I.value,o=0,t=+new Date
  O.textContent='...wait...'
  setTimeout(_=>(F(n),O.textContent=['rows='+o,'time sec '+(new Date-t)/1000]), 10)
  
}

test()
N:<input id=I value=12 type=number max=20><button onclick='test()'>go</button>
<pre id=O></pre>

\$\endgroup\$
  • \$\begingroup\$ Really interesting solution, it may be possible to handle n = 15 by using another approach. \$\endgroup\$ – mlpo Jun 28 '16 at 19:34
  • \$\begingroup\$ In fact, I can run this function in less than 7 minutes on my machine using node. So, you just have to replace console.log(++q,c.join``) by console.log(c.join``) to have valid output and your answer is valid. \$\endgroup\$ – mlpo Jun 28 '16 at 20:29
2
\$\begingroup\$

J, 97 70 69 68 60 59 bytes

'()'{~(,:'')((((>:#-+/)*(]#>:2*+/))"1#]),.&0,,.&1)^:(2*[)~]

Now tacit!

This is a monad that uses binary digits to create pairs of parentheses. In order to meet the requirements, a non-recursive approach is used along with optimization by use of certain primitives to ensure that mostly boolean (1 byte) values are used to keep memory requirements low.

On my computer, using an i7-4770k, it takes about 50 seconds to compute the result for n = 15 and uses about 1.5 GB of memory.

In the interests of maximizing speed, this version with 70 bytes computes the result for n = 15 in 0.5 seconds while using about 800 MB of memory. It's also tacit!

'()'{~[:;@(<@([:,/],"1/0=|."1)/.~+/"1)<:1&(],(+/<:#-+/)"1@,.~#,.~)1$0:

Usage

   f =: '()'{~(,:'')((((>:#-+/)*(]#>:2*+/))"1#]),.&0,,.&1)^:(2*[)~]
   timer =: 6!:2
   f 3
()()()
(())()
()(())
(()())
((()))
   10 timer 'r =: f 15'  NB. Average time over 10 runs
49.9951
   # r
9694845
\$\endgroup\$
1
\$\begingroup\$

Pyth, 47 bytes

                                                               <-empty line
Musm?<J/d\(Q?>-J/d\)0,+d\(+d\)]+d\(]+d\)G*2Q]k

Took 18 minutes on my machine, and over 2GB RAM.

In pythonic pseudocode:

// newline means "print"
M                                              map(print,
 u                                               reduce(lambda G,H:
  sm                                               sum(map(lambda d:
                     ,+d\(+d\)                       ([d+"(",d+")"] if
            ?>-J/d\)0                                   J-d.count(")") > 0
                              ]+d\(                     else [d+"("]) if
    ?<J/d\(Q                                           (J=d.count("(") < Q
                                   ]+d\)               else [d+")"],
                                        G              G)),
                                         *2Q]k     2*input(),[""]))

In words:

  1. create a function that maps any string to a list of strings that can be formed by adding "(" or ")"
    if the parentheses are already matched, only "(" can be added; if there are already n "(", only ")" can be added; otherwise a pair is returned
  2. create a new function that maps the old function over its param, and then sum up the map, so that it takes a list of strings, maps to a list of lists of strings, and then de-nests it back into a list of strings
    each call essentially "grows" its params by one ( or )
  3. reduce this new function over range(2*input()), with [""] as base case
    essentially just passing [""] through the new function 2n times
  4. map print over the return value of reduce to print each string in new lines
\$\endgroup\$
1
\$\begingroup\$

Haskell, 111 105 bytes

import Data.Function
id=<<fix(\h a z->id=<<[('(':)<$>h(a-1)z|a>0]++[(')':)<$>h a(z-1)|a<z]++[[""]|a+z<1])

Usage example: id=<<fix(\h a z->id=<<[('(':)<$>h(a-1)z|a>0]++[(')':)<$>h a(z-1)|a<z]++[[""]|a+z<1]) $ 3 -> ["((()))","(()())","(())()","()(())","()()()"].

The Dyck word building algorithm used here expressed in a classic recursive way looks like

dyck a z =                    -- take two numbers, `a` (the number of `(` to use)
                              -- and `z` (the number of `)` to use)
                 [[""]|a+z<1] -- base case if both numbers are 0, the result
                              -- is an empty word
    [('(':)<$>dyck(a-1)z|a>0] -- if there are `(` left, prepend one to every result
                              -- from a recursive call with one `(` less
   [(')':)<$>dyck a(z-1)|a<z] -- same for `)` if there are more than `(`.
id=<<  ...  ++  ...  ++       -- combine those results in to a flat list

As recursion is not allowed, we pass the function to call as a third parameter h (and use a lambda instead of a named function):

\h a z ->   ....  h(a-1)z  ....  h a(z-1)

and let the fixpoint combinator fix create this function for us:

fix(\h a z ...)

finally, the leftmost id=<< duplicates the input parameter: (id=<<) f n is f n n, so when the whole function is called, the parameter n is used as a and z.

For input 15 it takes about 3min within ghci (25s when compiled) and a few MB on my 5 year old laptop.

\$\endgroup\$
  • \$\begingroup\$ Sorry for the unnecessary edit, I wanted to add the syntax highlighting tag to understand better what's going on, but it did not seem to work =/ \$\endgroup\$ – flawr Jun 29 '16 at 19:53
0
\$\begingroup\$

Haskell, 140 132 bytes

Thanks @nimi for saving a few bytes!

import Data.List
h s|m<-length s=nub[k|l<-s!!0,k<-('(':l++")"):[u++v|n<-[0..m-2],u<-s!!n,v<-s!!(m-2-n)]]:s
f n=iterate h[[""]]!!n!!0

First of all: iterate does create a recursion sequecnce of h, but this is a builtin, and by the rules we may use builtins that use recursion.

This is just a very simple recursive approach, we can generate the n-Dyck-words by putting (n-1)-Dyck-words between paranthesis, or by concatenating from shorter Dyck words. This approach however does generate duplicates, that is why we filter for unique elements using nub.

As Haskell is a functional language, it is almost impossible to do this without recursion. There is an even more direct approach, but that one is banned under the current rules.

\$\endgroup\$
  • \$\begingroup\$ I was not aware of that, thank you, I updated my answer accordingly. \$\endgroup\$ – flawr Jun 29 '16 at 13:03
  • \$\begingroup\$ A few bytes to save: f n=iterate h[[""]]!!n!!0, l<-s!!0, '(':l++")". \$\endgroup\$ – nimi Jun 29 '16 at 16:27
  • \$\begingroup\$ @nimi Thank you very much! \$\endgroup\$ – flawr Jun 29 '16 at 19:47

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.