Daily Challenge #101 - Parentheses Generator

from itertools import permutations
for i in set(permutations('()' * int(input()))):
    s = []
    for j in i:
        if j == '(':
            s.append(j)
        elif s != []:
            s.pop()
    if s == []:
        print(''.join(i))

const solveWithNumbers = (startingNumbers: number[], requiredLength: number): number[][] => {
  if (requiredLength === 0) return [ startingNumbers ];
  if (startingNumbers.length === 0) return solveWithNumbers([...startingNumbers, 1], requiredLength - 1);
  const lastNumber = startingNumbers[startingNumbers.length - 1];
  if (lastNumber === 0) return solveWithNumbers([...startingNumbers, 1], requiredLength - 1);
  if (lastNumber === requiredLength) return solveWithNumbers([...startingNumbers, lastNumber - 1], requiredLength - 1);
  return [...solveWithNumbers([...startingNumbers, lastNumber - 1], requiredLength - 1), ...solveWithNumbers([...startingNumbers, lastNumber + 1], requiredLength - 1)];
}

const paren = (n) => solveWithNumbers([], n * 2).map(
  s => s.map(
    (x, i, a) => (i && (a[i - 1] < x ? '(' : ')')) || '('
  ).join('')
);


for (let i = 0; i < 10; i++) {
  console.log(i, paren(i));
}

/**
 * Parentheses Generator 
 * https://dev.to/thepracticaldev/daily-challenge-101-parentheses-generator-5d12
 */
#include <iostream>
#include <stack>

using namespace std;

bool check_balanced_parans(string s) {
    stack<char> stack;
    for(auto it = s.begin(); it != s.end(); it++) {
        if(*it == '(') {
            stack.push(*it);
        } else {
            if (stack.empty() || stack.top() == ')') {
                return false;
            } else {
                stack.pop();
            }
        }
    }

    return stack.empty();
}

void generate_all_permutations(int n, int i, string s, int open, int close) {
    if(close > open) return;
    if(open > n / 2 + 1) return;

    if(i == 0) {
        if(check_balanced_parans(s)) cout << s << endl;
    } else {
        s.push_back('(');
        generate_all_permutations(n, i - 1, s, open + 1, close);
        s.pop_back();
        s.push_back(')');
        generate_all_permutations(n, i - 1, s, open, close + 1);
    }
}

int main() {
    int n;
    cin >> n;

    string s;
    generate_all_permutations(n * 2, n * 2, s, 0, 0);

    return 0;
}

const memoKey = ({
  aggregateCloseCount,
  length
}: {
  aggregateCloseCount: number;
  length: number;
}): string => `${aggregateCloseCount} ${length}`;

const parenPermutationsMemo: { [key: string]: string[] } = {};

const parenPermutations = ({
  aggregateCloseCount = 0,
  length
}: {
  aggregateCloseCount?: number;
  length: number;
}): string[] => {
  // clip away impossible param settings:
  //   if `aggregateCloseCount<0` any string would need to open more than it closes, which would result in an invalid paren combo
  //   if `aggregateCloseCount>length` any string would need to have more close chars than chars overall
  if (aggregateCloseCount < 0 || aggregateCloseCount > length) return [];

  // early exit for `length==0`
  if (length == 0) return [""];

  const key = memoKey({ aggregateCloseCount, length });
  return (
    parenPermutationsMemo[key] ||
    (parenPermutationsMemo[key] = ["(", ")"].flatMap(prefix =>
      parenPermutations({
        length: length - 1,
        aggregateCloseCount:
          aggregateCloseCount + Number(prefix == "(") - Number(prefix == ")")
      }).map(perm => prefix + perm)
    ))
  );
};

const parenPairPermutations = (pairs: number): string[] =>
  parenPermutations({ length: pairs * 2 });

console.log(parenPairPermutations(3));
//> Array(5) ["((()))", "(()())", "(())()", "()(())", "()()()"]

// The main advantage of this approach is better complexity, coping with higher counts
const grindTestPairCount = 14;
console.time(`Time for ${grindTestPairCount} pairs`);
console.log(
  `There are ${
    parenPairPermutations(grindTestPairCount).length
  } permutations for ${grindTestPairCount} pairs of parens`
);
console.timeEnd(`Time for ${grindTestPairCount} pairs`);
//> There are 2674440 permutations for 14 pairs of parens
//> Time for 14 pairs: 6208.31201171875ms
//(old mac pro)

<?php
class ParenthesesGenerator {
    private $solutions;

    public function __construct() {
        $this->solutions = [];
    }

    public function findParentheses($n) {
        if ($n < 0) {
            throw new \Exception('N less than zero');
        }
        if (isset($this->solutions[$n])) {
            return $this->solutions[$n];
        }

        $solution = $this->generateSolution($n);
        $this->solutions[$n] = $solution;

        return $solution;
    }

    private function generateSolution($n) {
        if ($n == 0) {
            return [''];
        }

        $possibilities = [];
        for ($i = 0; $i < $n; $i++) {
            $possibilities = array_merge($possibilities, $this->combinePossibilities($i, $n - $i - 1));
        }
        return $possibilities;
    }

    private function combinePossibilities($depth, $tailLength) {
        $possibilities = [];
        $nestedPossibilities = $this->findParentheses($depth);
        $tailPossibilities = $this->findParentheses($tailLength);
        foreach ($nestedPossibilities as $nestedPossibility) {
            foreach ($tailPossibilities as $tailPossibility) {
                $possibilities[] = '(' . $nestedPossibility . ')' . $tailPossibility;
            }
        }
        return $possibilities;
    }
}

$generator = new ParenthesesGenerator();
var_dump($generator->findParentheses(1));
var_dump($generator->findParentheses(2));
var_dump($generator->findParentheses(3));

struct ValidParenthesesGenerator {
    num_pairs: usize,
    open_paren_locations: Vec<usize>,
}

impl ValidParenthesesGenerator {
    pub fn new(num_pairs: usize) -> Self {
        Self {
            num_pairs,
            open_paren_locations: Vec::new(),
        }
    }

    fn generate_placement(&self) -> String {
        let mut result = String::with_capacity(self.num_pairs * 2);
        for &open_paren_index in self.open_paren_locations.iter() {
            while result.len() < open_paren_index {
                result.push(')');
            }
            result.push('(');
        }
        while result.len() < self.num_pairs * 2 {
            result.push(')');
        }
        result
    }
}

impl Iterator for ValidParenthesesGenerator {
    type Item = String;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let last = if let Some(last) = self.open_paren_locations.pop() {
                last
            } else {
                // Special case guard. We put it here as an optimization because we only get here once anyway.
                if self.num_pairs == 0 {
                    return None;
                }
                // This is the first iteration, so we put 0 as the first index and let the
                // following `while` loop fill up the rest.
                self.open_paren_locations.push(0);
                break;
            };
            if self.open_paren_locations.is_empty() {
                return None; // Cannot move the first paren
            }
            let max_position = self.open_paren_locations.len() * 2; // when all previous opening parens are closed
            if last < max_position {
                self.open_paren_locations.push(last + 1);
                break;
            }
        }
        while self.open_paren_locations.len() < self.num_pairs {
            let &last = self
                .open_paren_locations
                .last()
                .expect("After the loop there should be at least one");
            self.open_paren_locations.push(last + 1);
        }
        Some(self.generate_placement())
    }
}