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

  •  Quasari   ( @Quasari@programming.dev ) 
    link
    fedilink
    English
    3
    edit-2
    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));
    
    • 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.

      •  Quasari   ( @Quasari@programming.dev ) 
        link
        fedilink
        English
        3
        edit-2
        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.

  • Rust:

    A super simple brute force attempt: https://pastebin.com/qbYQNQ7h

    Also super slow. Took me a bit more than a minute for n=10.

    edit: An updated version: https://pastebin.com/wVhxLmt9

    Added some simple constraints to reduce the number of unfiltered entries that need to be generated, bringing the n=10 time down to 10ish seconds. EDIT: if any of the test cases are n=12 or greater, probably best to fail this without testing. It’s super inefficient memory wise.

  • Factor:

    USING: kernel regexp command-line namespaces sequences io math.combinatorics math.parser ;
    IN: l
    
    : g ( s -- ? )
      R/ (\{\}|\(\)|\[\])/
      [
        over empty? [ f ] [
          2dup re-contains?
          pick [ first "[{(" member? ] [ last "]})" member? ] bi
          and and
        ] if
      ] [
        [ "" re-replace ] keep
      ] while drop empty?
    ;
    
    : a ( n -- )
      "(){}[]" swap [
        dup g [ print ] [ drop ] if
      ] each-selection
    ;
    
    MAIN: [ command-line get [ string>number a ] each ]
    
  • That was pretty fun :)

    My solution is in OCaml. I generate the Dyck language directly (which is basically what this is).

    type color = P | B | C
    type dyck = Fork of color * dyck * dyck | Nil
    
    let fork c i n = Fork (c, i, n)
    
    let colors = List.to_seq [P; B; C]
    
    let color_open = function P -> "(" | B -> "[" | C -> "{"
    
    let color_close = function P -> ")" | B -> "]" | C -> "}"
    
    let rec to_string = function
      | Fork (c, i, n) -> color_open c ^ to_string i ^ color_close c ^ to_string n
      | Nil -> ""
    
    let memo f =
      let t = Hashtbl.create 10 in
      let rec g x =
        try Hashtbl.find t x with
        | Not_found ->
          let y = f g x in
          Hashtbl.add t x y;
          y
      in g
    
    let ( let* ) x f = Seq.flat_map f x
    
    let generate' recur = function
      | 0 -> Seq.return Nil
      | n ->
        Seq.memoize @@
        let* d = Seq.take n @@ Seq.ints 1 in
        let* c = colors in
        Seq.map_product (fork c) (recur (d - 1)) (recur (n - d))
    
    let generate = memo generate'
    
    let () =
      let n = (int_of_string Sys.argv.(1)) / 2 in
      Seq.iter (fun d -> print_endline (to_string d)) (generate n)
    
  • Here’s my Python solution. If my reasoning is all correct, it should (in theory) run in O(n * (number of matches)), which should be optimal since it takes at least that long to print out the results anyway. IF my reasoning is all correct, and my program is all correct.

    closing_to_opening = {')': '(', ']': '[', '}': '{'}
    
    def main(n: int) -> list[str]:
        assert n % 2 == 0, f'n must be even; got {n=}'
        acc: list = [(n // 2, None, None)]
        for i in range(n):
            new_acc = []
            for closing_brackets_left, unmatched_series, full_series in acc:
                if unmatched_series is not None:
                    most_recent_closing_bracket, rest = unmatched_series
                    matching_opening_bracket = closing_to_opening[most_recent_closing_bracket]
                    new_acc.append((closing_brackets_left, rest, (matching_opening_bracket, full_series)))
                if closing_brackets_left > 0:
                    for bracket in [')', ']', '}']:
                        new_acc.append((closing_brackets_left - 1, (bracket, unmatched_series), (bracket, full_series)))
            acc = new_acc
        result = []
        for _, _, series in acc:
            series_as_list = []
            for _ in range(n):
                bracket, series = series
                series_as_list.append(bracket)
            result.append(''.join(series_as_list))
        return result
    
    if __name__ == '__main__':
        from argparse import ArgumentParser
        parser = ArgumentParser()
        parser.add_argument('n')
        result = main(int(parser.parse_args().n))
        print('\n'.join(result))
    
    

    Idea: The matches of size n are precisely the strings with n/2 closing brackets, n/2 opening brackets, and brackets arranged so that each closing bracket matches up with the opening bracket on the “top of the stack” when processing the string and removing matches. We build the strings backwards. For each match-in-construction, we track the number of closing brackets left to be added, the “stack” (but working backwards, so the roles of opening and closing brackets are reversed), and, of course, the actual string. We transform each match-in-construction into 1, 3, or 4 new matches-in-construction, adding one character at a time: the opening bracket that matches the closing bracket on the top of the stack (if any), and the three closing brackets (if we still have closing brackets to add). Because appending to strings is O(n) since we need to copy, and pushing and popping from Python lists creates mutable aliasing issues (and would take O(n) to copy, just like with strings), we do a Lisp and use cons cells to create lists instead (hence, the backwards building). I suspect it gives the same asymptotic runtime anyway, but I don’t actually know whether that’s true.

  • Factor, take 2: much longer, much faster:

    USING: kernel regexp command-line namespaces sequences io math.combinatorics math.parser math strings ;
    IN: l
    
    : g ( s -- ? )
      R/ (\{\}|\(\)|\[\])/
      [
        2dup re-contains?
        pick empty? not
        and
      ] [
        [ "" re-replace ] keep
      ] while drop empty?
    ;
    
    : a ( n -- )
      2 -
      dup neg? [ drop ] [
        dup 0 = [ drop "{}" "[]" "()" [ print ] tri@ ] [
          "{[(" "}])" cartesian-product concat swap
          "(){}[]" swap [
            over
            [
              [ dup ] dip
              [ first ] [ last ] bi [ 1string ] bi@
              surround
              dup g [ print ] [ drop ] if
            ] each drop
          ] each-selection drop
        ] if
      ] if
    ;
    
    MAIN: [ command-line get [ string>number a ] each ]
    
    
  • Rust

    Seems I’m a bit late to the party so here’s something I quickly slapped together. The problem appears to be asking us to generate all n-ary words in the Dyck language D3 with 𝛴 = {(, ), [, ], {, }} and 𝓡 = {((, )), ([, ]), ({, })}. This grows in the order of 3ⁿ⸍²𝓒ₙ⸝₂, where 𝓒ₖ is the k-th Catalan number, since it combines the regular up/down decision problem at each lattice step with a 3-way decision problem of picking a bracket type. That quickly becomes A Lot™ — napkin math tells me it would take ~21GB to store all possible strings of length n = 20, delimited by newlines, as UTF-8 bytes — which made me think that I would want to do this in constant space instead of recursively, so I quickly Googled to see what prior art there was on generating functions for generalized Dyck languages and found a nice and short paper [1] claiming to be linear in the length of the words (not the quantity of them, that’s still A Lot™) and using constant space. I cribbed their algorithm and reduced it to the specifics of D3 with the given 𝛴 and 𝓡, and then used the fact that it can generate the next word using only the previous one to split the word-space into three equal parts that can be generated on as many threads. I chose three because the pattern required to recognize the end of each third was already the same one being used by the paper’s algorithm, (and because three seemed nice considering it’s D3 and |𝓡| = 3 and such), but you could ostensibly split the space into as many chunks as you have processors without penalty (beyond the overhead of the threads themselves plus fighting for the mutex lock on stdout) if you can recognize the chunk-ending patterns fast enough. After tweaking the buffer size to match my system setup (Arch on an i7 Kaby Lake), I can get it to pipe ~2GB/s to wc -l (which is ~11s for that n = 20 example). I’m sure there’s probably a bunch more that I could optimize but I’m afraid of SIMD and don’t want to think too hard about the algorithm, so I’ll just leave it here and let someone else tell me how I’m wrong / what I missed :)

    [1]: Liebehenschel, J., 2003. Lexicographical generation of a generalized dyck language. SIAM Journal on Computing, 32(4), pp.880-903.

  •  Quasari   ( @Quasari@programming.dev ) 
    link
    fedilink
    English
    1
    edit-2
    1 year ago

    I have a concern. I don’t think the tester can accurately test this problem. I could be wrong though

    1. Because test cases are per line(in that they are separated by \r\n), you can’t necessarily have a multi-line solution, like most outputs will be \r\n for a print line function. If \n by itself is ok its easy enough, but…
    2. It checks strict equality with the solution, so the order your algorithm solves it in must be exactly the same as the test case. Its not impossible to do, but would probably require some q&a to solve exact order.
    •  Ategon   ( @Ategon@programming.dev ) OP
      link
      fedilink
      English
      1
      edit-2
      1 year ago

      Yeah ill have to push an update to it. I’ll likely check accuracy manually and just use it to calculate the runtime to deal with the random ordering or I can do some sort of formatting that handles that

      •  brie   ( @brie@beehaw.org ) 
        link
        fedilink
        English
        11 year ago

        If order doesn’t matter, implementations can be quickly compared with a reference implementation using diff + sort:

        >> for i in 2 4 6 8; do diff -qs <(./a.out $i|sort) <(./a.out $i|sort); done
        Files /dev/fd/63 and /dev/fd/62 are identical
        Files /dev/fd/63 and /dev/fd/62 are identical
        Files /dev/fd/63 and /dev/fd/62 are identical
        Files /dev/fd/63 and /dev/fd/62 are identical
        >> for i in 2 4 6 8; do diff -qs <(./a.out $i|sort) <(true $i|sort); done
        Files /dev/fd/63 and /dev/fd/62 differ
        Files /dev/fd/63 and /dev/fd/62 differ
        Files /dev/fd/63 and /dev/fd/62 differ
        Files /dev/fd/63 and /dev/fd/62 differ
        
  •  brie   ( @brie@beehaw.org ) 
    link
    fedilink
    English
    11 year ago

    Probably doesn’t count since the lines are out of order, but here’s a first attempt at a C solution.

    #include <stdio.h>
    
    char const brackets[6] = "()[]{}";
    
    void combo(int pairs, int seed)
    {
    	if (pairs <= 0) {
    		return;
    	}
    	char const *pair = brackets + ((seed % 3) << 1);
    	if (pairs == 1) {
    		putchar(pair[0]);
    		putchar(pair[1]);
    	} else {
    		putchar(pair[0]);
    		if (seed & 1) {
    			combo(pairs - 1, seed / 6);
    			putchar(pair[1]);
    		} else {
    			putchar(pair[1]);
    			combo(pairs - 1, seed / 6);
    		}
    	}
    }
    
    int main(int argc, char **argv)
    {
    	int n;
    	size_t combos = 1;
    	size_t i;
    
    	sscanf(argv[1], "%d", &n);
    	for (i = 0; i < n; i += 2) {
    		combos *= 6;
    	}
    	combos >>= 1;
    	int pairs = n / 2;
    	for (i = 0; i < combos; i++) {
    		combo(pairs, i);
    		puts("");
    	}
    	return 0;
    }
    
  •  brie   ( @brie@beehaw.org ) 
    link
    fedilink
    English
    1
    edit-2
    1 year ago

    Figured out my old solution didn’t actually work past 4, so here’s a new solution in C. It matches @SleveMcDichael@programming.dev’s solution up to n=10.

    Some stats using wc -l:

    n=0 has 1 combinations
    n=2 has 3 combinations
    n=4 has 18 combinations
    n=6 has 135 combinations
    n=8 has 1134 combinations
    n=10 has 10206 combinations
    n=12 has 96228 combinations
    n=14 has 938223 combinations
    n=16 has 9382230 combinations
    n=18 has 95698746 combinations
    n=20 has 991787004 combinations
    
    #include <stdio.h>
    #include <stdlib.h>
    
    char const brackets[6] = "({[)}]";
    
    int update(int *buf, int len)
    {
    	int width = *buf >> 2;
    	if (width > len - 2) {
    		return -1;
    	}
    	if ((++*buf & 3) < 3) {
    		return 0;
    	}
    	*buf &= ~3;
    
    	if (update(buf + 1, width)) {
    		buf[1] = 0;
    		if (update(buf + width + 2, len - width - 2)) {
    			*buf = (width += 2) << 2;
    			if (width > len - 2) {
    				return -1;
    			}
    			buf[width + 2] = 0;
    		}
    	}
    	return 0;
    }
    
    void display(int *buf, int len)
    {
    	int width = *buf >> 2;
    	char const *bracket = brackets + (*buf & 3);
    	if (len <= 0) {
    		return;
    	};
    
    	putchar(bracket[0]);
    	display(buf + 1, width);
    	putchar(bracket[3]);
    	display(buf + width + 2, len - width - 2);
    }
    
    int main(int argc, char **argv)
    {
    	int n;
    	int *buf;
    	if (argc < 2) {
    		fputs("Bad invocation", stderr);
    		exit(EXIT_FAILURE);
    	}
    
    	sscanf(argv[1], "%d", &n);
    
    	buf = calloc(n + 2, sizeof(*buf));
    
    	display(buf, n);
    	putchar('\n');
    	while (!update(buf, n)) {
    		display(buf, n);
    		putchar('\n');
    	}
    
    	free(buf);
    	return 0;
    }
    
    v1 slightly incorrect solution
    #include <stdio.h>
    #include <stdlib.h>
    
    char const brackets[6] = "({[)}]";
    
    int update(int *buf, int len)
    {
    	int width = *buf >> 2;
    	if (width > len - 2) {
    		return -1;
    	}
    	if ((++*buf & 3) < 3) {
    		return 0;
    	}
    	*buf &= ~3;
    
    	if (update(buf + 1, width)) {
    		buf[1] = 0;
    		if (update(buf + width + 2, len - width - 2)) {
    			*buf = (width += 2) << 2;
    			if (width > len - 2) {
    				return -1;
    			}
    			buf[width + 2] = 0;
    		}
    	}
    	return 0;
    }
    
    void display(int *buf, int len)
    {
    	int width = *buf >> 2;
    	char const *bracket = brackets + (*buf & 3);
    	if (len <= 0) {
    		return;
    	};
    
    	putchar(bracket[0]);
    	display(buf + 1, width);
    	putchar(bracket[3]);
    	display(buf + width + 2, len - width - 2);
    }
    
    int main(int argc, char **argv)
    {
    	int n;
    	int *buf;
    
    	sscanf(argv[1], "%d", &n);
    	if (n == 0) {
    		return 0;
    	}
    
    	buf = calloc(n + 20, sizeof(*buf));
    
    	display(buf, n);
    	putchar('\n');
    	while (!update(buf, n)) {
    		display(buf, n);
    		putchar('\n');
    	}
    
    	free(buf);
    	return 0;
    }
    
  • 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 &lt; 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)