14
[Med] Bracket Match Generation (programming.dev)
submitted 1 year ago* (last edited 1 year ago) by [email protected] to c/[email protected]
16 comments fedilink hide all child comments

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

you are viewing a single comment's thread
view the rest of the comments
[-] [email protected] 3 points 1 year ago* (last edited 1 year ago)

Older solution that doesn't work quite right

spoilerThis 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));
[-] [email protected] 1 points 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.

[-] [email protected] 3 points 1 year ago* (last edited 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.

this post was submitted on 17 Aug 2023
14 points (100.0% liked)

Programming Challenges

235 readers
1 users here now

Welcome to the programming.dev challenge community!

Three challenges will be posted every week to complete

Easy challenges will give 1 point, medium will give 2, and hard will give 3. If you have the fastest time or use the least amount of characters you will get a bonus point (in ties everyone gets the bonus point)

Exact duplicate solutions are not allowed and will not give you any points. Submissions on a challenge will be open for a week.

A leaderboard will be posted every month showing the top people for that month

founded 1 year ago
MODERATORS
[email protected]