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