Skip to content

Instantly share code, notes, and snippets.

@phryneas
Created September 14, 2021 19:57
Show Gist options
  • Save phryneas/04865d20d426a46ba6b9f97b81b79e83 to your computer and use it in GitHub Desktop.
Save phryneas/04865d20d426a46ba6b9f97b81b79e83 to your computer and use it in GitHub Desktop.
cassidoo-fromParens
/**
This brute forces all possible () combinations by interpreting the binary
representation of an increasing number with 0 as ( and 1 as ).
Works fine for n<15. For bigger n, the amount of results will be too big for memory.
*/
function fromParens(n) {
let ret = [],
targetLen = n * 2, // target string length
max = Math.pow(2, targetLen), // maximum number to look at
current, // current number
idx, // index iterating over current number
left, // (current >> idx) - what is left after right-shifting current idx times
sum, // "sum" over ( as +1 and ) as -1
str; // current number as string
if (!n) return ret;
outer: for (current = 0; current < max; current++) {
left = current;
sum = 0;
// check if current is a vialbe candidate
for (idx = 0; idx < targetLen; idx++) {
// we only have "(" left in the string -> not a candidate
if (!left) continue outer;
sum += left & 1 ? -1 : 1;
// we have closed more parens than we openend -> not a candidate
if (sum < 0) break;
left >>= 1;
}
// if all opened parens were closed again
if (sum == 0) {
// build a string representation
left = current;
str = "";
for (idx = 0; idx < targetLen; idx++) {
str += left & 1 ? ")" : "(";
left >>= 1;
}
// and push it to the results
ret.push(str);
}
}
return ret;
}
for (let i = 1; i < 12; i++) {
console.time("i=" + i);
console.log(fromParens(i).length, "items found");
console.timeEnd("i=" + i);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment