Time: 2023-07-21 12:35:24Z
Hover over any symbol to see what it does. If this appears glitched unformulated version below.
Try it
If the "fancy" formatting above doesn't display for you, a version without formatting:
i>:?v~l2,b2.
10-1<.02}}
:?v~{{l2,06.
v \&'('o:2*[{1+}]$:
\:?v~$}}&1-b2.
')'/.31-1o
>:?v;
1+&\&:2*[{1-:}]?v:@l1-2,&:&-1+=?v$
{{&>:?v~}}50ao./~0}]
.61-1&>1-&:2*[{/>1{{69!.<96{{1~$<
If my Interpreter is too slow for you, TIO link
Not super well golfed, relying on people being too intimidated by fish.
How this works
The standard recursive version doesn't work well for fish because:
- It doesn't have functions
- There is no easy way to copy an array
- The only array type thing you have is the stack and there is only one of them
I came up with a completely different approach that does not involve recursion at all, and uses O(n) memory.
We note that, for a number of parenthesis N, we can place opening parenthesis on fixed places then just dynamically decide where to place the closing one that matches it. We can use this to encode a given configuration as the distance between each opening and the corresponding closing parenthesis (+1 for technical reasons)
(())()() = 2, 1, 1, 1
((()())) = 3, 2, 1, 1
(((()))) = 4, 3, 2, 1
()()(()) = 1, 1, 2, 1
Now all we need to find is an algorithm that can, from one set of numbers, figure out the "next" valid configuration.
Rendering
The render loop works as follows: We store next to each number an extra 0. This 0 represents the number of closing parenthesis that need to be drawn after that number. Now, when we for example need
to render a parenthesis with a distance of 1, we increment the value in the stack at 2 * 1. In this case it will be the closing parenthesis for the same number. Then after printing the ( we can print N ) characters depending on the value stored.
All of this means we can avoid any kind of recursion.
Incrementing
The incrementing logic is harder, but we can re-use the information from the closing parenthesis from the render stage. First, we try to increment the order of the last opening brace. If this makes us extend past the edge of the set, we skip and go to the next one. This part is easy.
An harder part is making sure the area we enclode does not partially intersect any other pair. There couldn't be any pairs to the right since they have all been reset to 1, but there could
be intersecting pairs to the left. For this purpose, we check the closing parenthesis again. We subtract one closing parenthesis from N steps to the front. If they are now zero, we can safely
increment past the boudary. Otherwise, we must again reset and try the next pair to the left.
If we have found a opening that can be incremented, we must reset the rest of the ")" counters to 0, then can render and continue. If we have reached the leftmost brace and it also can't be incremented, we have tried all sets and we can safely exit.
Approximately the same algorithm in Rust
|x|{
let mut z=vec![(1,0);x];
loop{
for i in 0..x{
print!("(");
let closing_index = z[i].0 + i - 1;
z[closing_index].1+=1;
print!("{}",")".repeat(z[i].1));
}
let mut done=false;
for i in 0..x{
let closing_index =z[i].0 + i - 1;
z[closing_index].1-=1;
if !done && !(i + z[i].0 >= x || z[closing_index].1> 0) {
z[i].0+=1;
done=true;
}
}
if !done {
return;
}
println!();
}
}
