Bracket Inc. wants to ship out new products using their excess brackets. They have tasked you with generating every possible assortment of brackets for some n brackets where the brackets will match
- A bracket match is an opening and closing version of the same kind of bracket beside each other
() - If a bracket matches then outer brackets can also match
(()) - n will be an even number
- The valid brackets are ()[]{}
For example for n = 4 the options are
- ()()
- (())
- [][]
- [[]]
- {}{}
- {{}}
- []()
- ()[]
- (){}
- {}()
- []{}
- {}[]
- ({})
- {()}
- ([])
- [()]
- {[]}
- [{}]
You must accept n as a command line argument (entered when your app is ran) and print out all of the matches, one per line
(It will be called like node main.js 4 or however else to run apps in your language)
You can use the solution tester in this post to test you followed the correct format https://programming.dev/post/1805174
Any programming language may be used. 2 points will be given if you pass all the test cases with 1 bonus point going to whoevers performs the quickest and 1 for whoever can get the least amount of characters
To submit put the code and the language you used below
Seems I’m a bit late to the party so here’s something I quickly slapped together. The problem appears to be asking us to generate all n-ary words in the Dyck language D3 with 𝛴 = {(, ), [, ], {, }} and 𝓡 = {((, )), ([, ]), ({, })}. This grows in the order of 3ⁿ⸍²𝓒ₙ⸝₂, where 𝓒ₖ is the k-th Catalan number, since it combines the regular up/down decision problem at each lattice step with a 3-way decision problem of picking a bracket type. That quickly becomes A Lot™ — napkin math tells me it would take ~21GB to store all possible strings of length n = 20, delimited by newlines, as UTF-8 bytes — which made me think that I would want to do this in constant space instead of recursively, so I quickly Googled to see what prior art there was on generating functions for generalized Dyck languages and found a nice and short paper [1] claiming to be linear in the length of the words (not the quantity of them, that’s still A Lot™) and using constant space. I cribbed their algorithm and reduced it to the specifics of D3 with the given 𝛴 and 𝓡, and then used the fact that it can generate the next word using only the previous one to split the word-space into three equal parts that can be generated on as many threads. I chose three because the pattern required to recognize the end of each third was already the same one being used by the paper’s algorithm, (and because three seemed nice considering it’s D3 and |𝓡| = 3 and such), but you could ostensibly split the space into as many chunks as you have processors without penalty (beyond the overhead of the threads themselves plus fighting for the mutex lock on stdout) if you can recognize the chunk-ending patterns fast enough. After tweaking the buffer size to match my system setup (Arch on an i7 Kaby Lake), I can get it to pipe ~2GB/s to wc -l (which is ~11s for that n = 20 example). I’m sure there’s probably a bunch more that I could optimize but I’m afraid of SIMD and don’t want to think too hard about the algorithm, so I’ll just leave it here and let someone else tell me how I’m wrong / what I missed :)
Coming here after the hard challenge, and I realized that the hard challenge already did most of my work for me, so here’s the solution with help from the hard challenge. :)
Python: https://pastebin.com/0Neaj0r9
import sys
from itertools import product
string_length = sys.argv[1]
matches = {
"}": "{",
"]": "[",
")": "("
}
brackets = ['{', '[', '(', ')', ']', '}']
def bracket_gen(length):
combinations = product(brackets, repeat=length)
return [''.join(combo) for combination in combinations]
def get_matching_substring_strict(string):
substring = ''
index_start = -1
index_end = -1
bracket_counts = {
"{": 0,
"[": 0,
"(": 0
}
for index, letter in enumerate(string):
if letter in matches.values():
if index_start == -1:
index_start = index
substring += letter
bracket_counts[letter] += 1
if letter in matches.keys():
if not substring:
break
if substring[-1] == matches[letter]:
substring = substring[:-1]
bracket_counts[matches[letter]] -= 1
if not [cnt for cnt in bracket_counts.values() if cnt]:
index_end = index
if [cnt for cnt in bracket_counts.values() if cnt < 0]:
break
else:
break
if index_start != -1 and index_end != -1:
matching_substring = string[index_start:index_end + 1]
return matching_substring
valid_combos = []
bracket_combos = bracket_gen(eval(string_length))
for combo in bracket_combos:
if combo == get_matching_substring_strict(combo):
print(combo)
Figured out my old solution didn’t actually work past 4, so here’s a new solution in C. It matches @SleveMcDichael@programming.dev’s solution up to n=10.
Some stats using wc -l:
n=0 has 1 combinations
n=2 has 3 combinations
n=4 has 18 combinations
n=6 has 135 combinations
n=8 has 1134 combinations
n=10 has 10206 combinations
n=12 has 96228 combinations
n=14 has 938223 combinations
n=16 has 9382230 combinations
n=18 has 95698746 combinations
n=20 has 991787004 combinations
#include
#include
char const brackets[6] = "({[)}]";
int update(int *buf, int len)
{
int width = *buf >> 2;
if (width > len - 2) {
return -1;
}
if ((++*buf & 3) < 3) {
return 0;
}
*buf &= ~3;
if (update(buf + 1, width)) {
buf[1] = 0;
if (update(buf + width + 2, len - width - 2)) {
*buf = (width += 2) << 2;
if (width > len - 2) {
return -1;
}
buf[width + 2] = 0;
}
}
return 0;
}
void display(int *buf, int len)
{
int width = *buf >> 2;
char const *bracket = brackets + (*buf & 3);
if (len <= 0) {
return;
};
putchar(bracket[0]);
display(buf + 1, width);
putchar(bracket[3]);
display(buf + width + 2, len - width - 2);
}
int main(int argc, char **argv)
{
int n;
int *buf;
if (argc < 2) {
fputs("Bad invocation", stderr);
exit(EXIT_FAILURE);
}
sscanf(argv[1], "%d", &n);
buf = calloc(n + 2, sizeof(*buf));
display(buf, n);
putchar('\n');
while (!update(buf, n)) {
display(buf, n);
putchar('\n');
}
free(buf);
return 0;
}
v1 slightly incorrect solution
#include
#include
char const brackets[6] = "({[)}]";
int update(int *buf, int len)
{
int width = *buf >> 2;
if (width > len - 2) {
return -1;
}
if ((++*buf & 3) < 3) {
return 0;
}
*buf &= ~3;
if (update(buf + 1, width)) {
buf[1] = 0;
if (update(buf + width + 2, len - width - 2)) {
*buf = (width += 2) << 2;
if (width > len - 2) {
return -1;
}
buf[width + 2] = 0;
}
}
return 0;
}
void display(int *buf, int len)
{
int width = *buf >> 2;
char const *bracket = brackets + (*buf & 3);
if (len <= 0) {
return;
};
putchar(bracket[0]);
display(buf + 1, width);
putchar(bracket[3]);
display(buf + width + 2, len - width - 2);
}
int main(int argc, char **argv)
{
int n;
int *buf;
sscanf(argv[1], "%d", &n);
if (n == 0) {
return 0;
}
buf = calloc(n + 20, sizeof(*buf));
display(buf, n);
putchar('\n');
while (!update(buf, n)) {
display(buf, n);
putchar('\n');
}
free(buf);
return 0;
}
Factor, take 2: much longer, much faster:
USING: kernel regexp command-line namespaces sequences io math.combinatorics math.parser math strings ;
IN: l
: g ( s -- ? )
R/ (\{\}|\(\)|\[\])/
[
2dup re-contains?
pick empty? not
and
] [
[ "" re-replace ] keep
] while drop empty?
;
: a ( n -- )
2 -
dup neg? [ drop ] [
dup 0 = [ drop "{}" "[]" "()" [ print ] tri@ ] [
"{[(" "}])" cartesian-product concat swap
"(){}[]" swap [
over
[
[ dup ] dip
[ first ] [ last ] bi [ 1string ] bi@
surround
dup g [ print ] [ drop ] if
] each drop
] each-selection drop
] if
] if
;
MAIN: [ command-line get [ string>number a ] each ]
Rust solution:
fn completer(bracket: char) -> char {
match bracket {
'[' => ']',
'{' => '}',
'(' => ')',
')' => '(',
'}' => '{',
']' => '[',
_ => unreachable!(),
}
}
fn rec(v: &mut Vec, stack: &mut Vec, depth: usize) {
// If we have more characters in the stack to complete
// than the space avaiable, bail!
if stack.len() > depth {
return;
}
if depth == 0 {
let output: String = v.iter().collect();
println!("{}", output);
return;
}
for b in &['[', '{', '('] {
v.push(*b);
stack.push(*b);
rec(v, stack, depth - 1);
stack.pop();
v.pop();
}
if let Some(c) = stack.pop() {
v.push(completer(c));
rec(v, stack, depth - 1);
stack.push(c);
v.pop();
}
}
fn main() {
let depth: usize = std::env::args().nth(1).unwrap().parse().unwrap();
let mut v = Vec::with_capacity(depth);
let mut s = Vec::with_capacity(depth / 2);
rec(&mut v, &mut s, depth);
}
Hope you enjoy this!
Edit: Lemmy makes the usize in angle brackets disappear after parse::. Idk what to do.
Edit: I kinda fixed it by assigning the type as a part of the variable definition.
Note to self: the angle bracket problem persists nonetheless.