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

  •  brie   ( @brie@beehaw.org ) English
    1•1 year ago

    Figured out my old solution didn’t actually work past 4, so here’s a new solution in C. It matches @SleveMcDichael@programming.dev’s solution up to n=10.

    Some stats using wc -l:

    n=0 has 1 combinations
n=2 has 3 combinations
n=4 has 18 combinations
n=6 has 135 combinations
n=8 has 1134 combinations
n=10 has 10206 combinations
n=12 has 96228 combinations
n=14 has 938223 combinations
n=16 has 9382230 combinations
n=18 has 95698746 combinations
n=20 has 991787004 combinations

    #include <stdio.h>
#include <stdlib.h>

char const brackets[6] = "({[)}]";

int update(int *buf, int len)
{
	int width = *buf >> 2;
	if (width > len - 2) {
		return -1;
	}
	if ((++*buf & 3) < 3) {
		return 0;
	}
	*buf &= ~3;

	if (update(buf + 1, width)) {
		buf[1] = 0;
		if (update(buf + width + 2, len - width - 2)) {
			*buf = (width += 2) << 2;
			if (width > len - 2) {
				return -1;
			}
			buf[width + 2] = 0;
		}
	}
	return 0;
}

void display(int *buf, int len)
{
	int width = *buf >> 2;
	char const *bracket = brackets + (*buf & 3);
	if (len <= 0) {
		return;
	};

	putchar(bracket[0]);
	display(buf + 1, width);
	putchar(bracket[3]);
	display(buf + width + 2, len - width - 2);
}

int main(int argc, char **argv)
{
	int n;
	int *buf;
	if (argc < 2) {
		fputs("Bad invocation", stderr);
		exit(EXIT_FAILURE);
	}

	sscanf(argv[1], "%d", &n);

	buf = calloc(n + 2, sizeof(*buf));

	display(buf, n);
	putchar('\n');
	while (!update(buf, n)) {
		display(buf, n);
		putchar('\n');
	}

	free(buf);
	return 0;
}
    v1 slightly incorrect solution 
    #include <stdio.h>
#include <stdlib.h>

char const brackets[6] = "({[)}]";

int update(int *buf, int len)
{
	int width = *buf >> 2;
	if (width > len - 2) {
		return -1;
	}
	if ((++*buf & 3) < 3) {
		return 0;
	}
	*buf &= ~3;

	if (update(buf + 1, width)) {
		buf[1] = 0;
		if (update(buf + width + 2, len - width - 2)) {
			*buf = (width += 2) << 2;
			if (width > len - 2) {
				return -1;
			}
			buf[width + 2] = 0;
		}
	}
	return 0;
}

void display(int *buf, int len)
{
	int width = *buf >> 2;
	char const *bracket = brackets + (*buf & 3);
	if (len <= 0) {
		return;
	};

	putchar(bracket[0]);
	display(buf + 1, width);
	putchar(bracket[3]);
	display(buf + width + 2, len - width - 2);
}

int main(int argc, char **argv)
{
	int n;
	int *buf;

	sscanf(argv[1], "%d", &n);
	if (n == 0) {
		return 0;
	}

	buf = calloc(n + 20, sizeof(*buf));

	display(buf, n);
	putchar('\n');
	while (!update(buf, n)) {
		display(buf, n);
		putchar('\n');
	}

	free(buf);
	return 0;
}