Back to General discussions forum
Three kinds of brackets are commonly used in programming. These are (), [] and {}. If we remove all characters, other than the brackets, from program statements, it is easier to check whether or not the brackets form a valid sequence. Since every opening bracket musrt have a matching close bracket, it is clear that all valid bracket sequences must have even length. However, it is also fairly obvious that sequences such as (}{) and [(]) are not valid. This problem considers all valid bracket sequences of a given length and the lexicographic order of these sequences. For example there are 18 valid sequences of length 4. In lexicographic order these are:
(()), ()(), ()[], (){}, ([]), ({}), [()], [[]], [](), [][], []{}, [{}], {()}, {[]}, {{}}, {}(), {}[], {}{}
So the first valid sequence is (()) and the 18th is {}{}. For a given length of sequence you will be given a numeric position. You must find the bracket sequence which comes at this position in the sorted set of all valid bracket sequences having this length. The problem will have several sets of data, of increasing difficulty. No sequence length will be greater than 38.
Input/Output description: The first line of the input data will contain a single integer N. N lines of data follow. Each of these lines contains 2 space-separated integers L and P. L is the length of the bracket sequence and P is the position of the particular sequence to be chosen from the sorted list. Your answer should be a single string containing all of the required sequences, separated by single spaces.
Example:
input:
7
4 15
8 896
12 73177
16 6922270
20 600569676
24 34872014990
28 7832826488228
answer:
{{}} {[]}[[]] {[[]()]}{()} {({}([]())[()])} [{[([{[]()}{}])]}()] ({}){(())}[{{{}[[]]}}()] [{[]{[][][]}[{{}}]{}}][[]]()
Clive, thanks you! The puzzle is published - perhaps at least time I publish it quicker than Mathias have it solved :)))
https://www.codeabbey.com/index/task_view/ordered-brackets
Curious feeling - as if I almost grasp the enumeration idea, but need to pause and think more thoroughly! Meanwhile suddenly found in the mailbox interesting problem suggestion from Mathias himself so here is something to brood over!
Well, this was a brain workout. Thank you, Clive!
I also took the liberty of adding my own solution to Revoltle.
Yes, this was challenging indeed - thank you.
Thanks friends, for the feedback.
It recently occurred to me that combining the bracket validation problem with a lexicographic ordering problem could potentially produce a fun problem for CodeAbbey.
I really enjoyed designing a solution to the problem and hoped that others would also find it an interesting challenge.
I appreciate the early solutions coming in, as this provides reassurance that the problem setter and checker are working as they should.
What a shameful situation. On the first day, pondering over the problem, I found it is somewhat related to "Proper bracket sequence" count task we have elsewhere - but I found with surprise I can't remember the approach to it. It took a day to come to it again but then kicking around for some more time I found I can't immediately extend solution to this one. Well-well, at least I'm more and more share the feelings, sometimes frustration, of other people solving problems, thanks to your effort of inventing new puzzles :)
(but I don't mean to give up yet, the approach seems less or more clear, I just fail to combine bricks)