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
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)