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

  • lavafroth@programming.dev
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    1 year ago

    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.