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:;}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
3I think you need to define recursion better. You can easily build your own function with
goto
statements, stacks in loops, etc. I don't think this kind of exclusion will ever work nicely for a challenge, as any approach to do this could be argued to be some form of implementing recursion yourself? – FryAmTheEggman – 2016-06-28T17:30:44.8504
This is a very interesting challenge. but most of the rules make it worse. For example
– James – 2016-06-28T17:33:54.620You 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.1@FryAmTheEggman Yes, it is still possible to emulate the recursion. But it is penalized by the place that takes this “emulation”. The goal is not to prohibit all forms of recursion, just make it more difficult (bracket it ;-]). So I see two valid approaches: circumvent the ban, or do completely differently. – mlpo – 2016-06-28T17:40:49.973
1@DrGreenEggsandIronMan As I said, the goal is to make harder to use a recursive principle. Although, as noted above, it is still possible. All cited rules are designed with that in mind. Regarding the remark on functions rather than full programs, it seems perfectly acceptable, I will add it. – mlpo – 2016-06-28T17:47:54.023
4
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.
– FryAmTheEggman – 2016-06-28T17:50:46.8772@FryAmTheEggman It came to my mind while writing the challenge. That's why the challenge does not prohibit all forms of recursion. It just does not allow to write recursive functions. If the concept of functions does not exist in the selected language, or if recursion is underlying, the answer seems valid to me. – mlpo – 2016-06-28T17:58:44.770
Using an approach which builds the strings one character at a time and then filters them (so it generates at most twice as many strings as Dyke paths), I'm running out of memory with a 2GB heap for
n=15
. I can getn=14
in 3m41s with a 2GB heap. – Peter Taylor – 2016-06-28T19:15:06.057@FryAmTheEggman, doubling the time taken is only reasonable if the reference implementation is in a slow high-level language, unless the intention is to exclude high-level languages. See e.g. my question on practical numbers for an example of what I consider reasonable: that allowed taking 250 times as long as my reference Java answer, and 10 times as long as my reference Python answer.
– Peter Taylor – 2016-06-28T19:17:44.433@mlpo Oh, whoops, don't mind me I'm bad at using my calculator :P Anyway, then how long does it take? Try using Peter's guidelines along with your own solution to come up with something reasonable. – FryAmTheEggman – 2016-06-28T19:21:17.997
@FryAmTheEggman With an old PC, my solution takes less than 5 seconds in C. – mlpo – 2016-06-28T19:24:35.997
@PeterTaylor Thanks for your advices. I have set the limit at 20 minutes. – mlpo – 2016-06-28T19:31:34.083
@PeterTaylor My solution has a small memory footprint, but I do not want to disqualify other approaches. I increased the limit to 4 GB. – mlpo – 2016-06-28T19:50:07.187
8
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.
– xnor – 2016-06-29T00:09:21.9005For a first challenge, I think you're off to a good start, but in the future I recommend less micromanaging requirements. – xnor – 2016-06-29T00:10:39.703
4
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.
– Martin Ender – 2016-06-29T11:15:46.040Thank you both for your constructive comments. I did not know the sandbox, thank you for the information, I’ll use it next time. – mlpo – 2016-06-29T15:13:14.140