Task:

 Generate a string with   N   opening brackets   [   and with   N   closing brackets   ],   in some arbitrary order. 
 Determine whether the generated string is balanced; that is, whether it consists entirely of pairs of opening/closing brackets (in that order), none of which mis-nest.


Examples

   (empty)      OK
   []           OK   
   [][]         OK   
   [[][]]       OK 
   ][         NOT OK
   ][][       NOT OK
   []][[]     NOT OK



rosetta_brackets :-
	test_brackets([]),
	test_brackets(['[',']']),
	test_brackets(['[',']','[',']']),
	test_brackets(['[','[',']','[',']',']']),
	test_brackets([']','[']),
	test_brackets([']','[',']','[']),
	test_brackets(['[',']',']','[','[',']']).
 
balanced_brackets :-
	gen_bracket(2,  B1, []), test_brackets(B1),
	gen_bracket(4,  B2, []), test_brackets(B2),
	gen_bracket(4,  B3, []), test_brackets(B3),
	gen_bracket(6,  B4, []), test_brackets(B4),
	gen_bracket(6,  B5, []), test_brackets(B5),
	gen_bracket(8,  B6, []), test_brackets(B6),
	gen_bracket(8,  B7, []), test_brackets(B7),
	gen_bracket(10, B8, []), test_brackets(B8),
	gen_bracket(10, B9, []), test_brackets(B9).
 
test_brackets(Goal) :-
	(   Goal = [] -> write('(empty)'); maplist(write, Goal)),
	(   balanced_brackets(Goal, []) ->
	    writeln(' succeed')
	;
	    writeln(' failed')
	).
 
% grammar of balanced brackets
balanced_brackets --> [].
 
balanced_brackets -->
	['['],
	balanced_brackets,
	[']'].
 
balanced_brackets -->
	['[',']'],
	balanced_brackets.
 
 
% generator of random brackets
gen_bracket(0) --> [].
 
gen_bracket(N) -->
	{N1 is N - 1,
	 R is random(2)},
	bracket(R),
	gen_bracket(N1).
 
bracket(0) --> ['['].
bracket(1) --> [']'].
 