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
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.
I have a concern. I don’t think the tester can accurately test this problem. I could be wrong though
- 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… - 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.
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
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)
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 ]
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.