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

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

    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)