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
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.
Factor:
USING: kernel regexp command-line namespaces sequences io math.combinatorics math.parser ;
IN: l
: g ( s -- ? )
R/ (\{\}|\(\)|\[\])/
[
over empty? [ f ] [
2dup re-contains?
pick [ first "[{(" member? ] [ last "]})" member? ] bi
and and
] if
] [
[ "" re-replace ] keep
] while drop empty?
;
: a ( n -- )
"(){}[]" swap [
dup g [ print ] [ drop ] if
] each-selection
;
MAIN: [ command-line get [ string>number a ] each ]
Rust:
A super simple brute force attempt: https://pastebin.com/qbYQNQ7h
Also super slow. Took me a bit more than a minute for n=10.
edit: An updated version: https://pastebin.com/wVhxLmt9
Added some simple constraints to reduce the number of unfiltered entries that need to be generated, bringing the n=10 time down to 10ish seconds. EDIT: if any of the test cases are n=12 or greater, probably best to fail this without testing. It’s super inefficient memory wise.
Older solution that doesn’t work quite right
spoiler
This time I did it in JavaScript. Overall, it solves it in a reasonable amount of time up to n = 16, but won’t at n = 18 and up.
const BRACKETS = [['(', ')'], ['[', ']'], ['{', '}']];
function brackets(n) {
if (n === 1) return ['()', '[]', '{}'];
let o = {};
function addBracket(s) {
BRACKETS.forEach(b => {
o[b[0] + b[1] + s] = true;
o[b[0] + s + b[1]] = true;
o[s + b[0] + b[1]] = true;
});
}
brackets(n - 1).forEach(addBracket);
return Object.keys(o);
}
brackets(Number(process.argv[2]) / 2).forEach(v => console.log(v));
I don’t feel experienced enough with data structures and algorithms to make this more efficient. I really just started learning this stuff and don’t have a great grasp of it yet. I could of probably used a set to save some lines instead of a hashmap, but eh, its probably slightly faster because I went the hashmap route to get rid of duplicates.
I revised it because I was pointed out I missed an aspect of the problem. This is in JavaScript
const BRACKETS = ['()', '[]', '{}'];
function brackets(n) {
if (n === 0) return [''];
let strings = brackets(n - 1);
let o = {};
for (let s of strings) {
for (let i = 0; brackets.length >= i; i++) {
for (let b of BRACKETS) {
o[s.slice(0, i) + b + s.slice(i)] = true;
}
}
}
return Object.keys(o);
}
brackets(Number(process.argv[2]) / 2).forEach(v => console.log(v));
Interesting approach, but from my understanding of the code, it doesn’t generate matches like [()][()]
. I could be wrong, but I don’t see how you can get that by prepending, appending, and enclosing just ()
, []
, and/or {}
.
I’m also assuming that [()][()]
is supposed to be one of the results for n = 8. At least two others here seem to have made that assumption, and I believe it’s consistent with the previous challenge. Would be nice to have some clarification on this, though.
You know, you are right. I overlooked the idea of there being multiple nests. That complicates things.
I could probably revise the current method, but build different n sized clusters through recursion, then just mix them.
Or, maybe just an insertion based one, placing a full bracket at every position in the string. That probably would be faster than the previous idea.
I guess I’ll work on that tomorrow.
I ended up updating it now.
Thanks for the heads up.
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 ]