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

  • oessessnex
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    1 year ago

    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)