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

  • QuasariEnglish
    3·
    1 year ago

    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));
    • shape-warrior-t@kbin.social
      1·
      1 year ago

      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.

      • QuasariEnglish
        3·
        1 year ago

        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.