Added hard/bracket_combinations

bradhanson · bradhanson · commit cbb1e36ea579 · 2018-07-18T09:28:49.000-04:00
diff --git a/hard/bracket_combinations.js b/hard/bracket_combinations.js
@@ -0,0 +1,31 @@
+/**
+ * Have the function bracketCombinations(num) read num which will be an integer
+ * greater than or equal to zero, and return the number of valid combinations
+ * that can be formed with num pairs of parentheses. For example, if the input
+ * is 3, then the possible combinations of 3 pairs of parenthesis, namely:
+ * ()()(), are ()()(), ()(()), (())(), ((())), and (()()). There are 5 total
+ * combinations when the input is 3, so your program should return 5.
+ *
+ * https://www.coderbyte.com/results/bhanson:Bracket%20Combinations:JavaScript
+ *
+ * @param  {number} num
+ * @return {number}
+ */
+function bracketCombinations(num) {
+    // https://en.wikipedia.org/wiki/Catalan_number
+    return (1 / (num + 1)) * choose(2 * num, num);
+}
+
+function factorial(num) {
+    let sum = 1;
+    for (let i = 1; i <= num; i++) {
+        sum *= i;
+    }
+    return sum;
+}
+
+function choose(num, k) {
+    return factorial(num) / (factorial(k) * factorial(num - k));
+}
+
+module.exports = bracketCombinations;
diff --git a/hard/bracket_combinations.test.js b/hard/bracket_combinations.test.js
@@ -0,0 +1,21 @@
+const bracketCombinations = require('./bracket_combinations');
+
+describe('bracketCombinations()', () => {
+    test('passes Coderbyte.com tests', () => {
+        expect(bracketCombinations(0)).toBe(1);
+
+        expect(bracketCombinations(3)).toBe(5);
+
+        expect(bracketCombinations(4)).toBe(14);
+
+        expect(bracketCombinations(5)).toBe(42);
+
+        expect(bracketCombinations(6)).toBe(132);
+
+        expect(bracketCombinations(7)).toBe(429);
+
+        expect(bracketCombinations(8)).toBe(1430);
+
+        expect(bracketCombinations(9)).toBe(4862);
+    });
+});
