Daily Challenge #101 - Parentheses Generator

twitter logo ・1 min read

Daily Challenge (132 Part Series)

1) Daily Challenge #1 - String Peeler 2) Daily Challenge #2 - String Diamond 3 ... 130 3) Daily Challenge #3 - Vowel Counter 4) Daily Challenge #4 - Checkbook Balancing 5) Daily Challenge #5 - Ten Minute Walk 6) Daily Challenge #6 - Grandma and her friends 7) Daily Challenge #7 - Factorial Decomposition 8) Daily Challenge #8 - Scrabble Word Calculator 9) Daily Challenge #9 - What's Your Number? 10) Daily Challenge #10 - Calculator 11) Daily Challenge #11 - Cubic Numbers 12) Daily Challenge #12 - Next Larger Number 13) Daily Challenge #13 - Twice Linear 14) Daily Challenge #14 - Square into Squares 15) Daily Challenge #15 - Stop gninnipS My sdroW! 16) Daily Challenge #16 - Number of People on the Bus 17) Daily Challenge #17 - Double Trouble 18) Daily Challenge #18 - Triple Trouble 19) Daily Challenge #19 - Turn numbers into words 20) Daily Challenge Post #20 - Number Check 21) Daily Challenge #21 - Human Readable Time 22) Daily Challenge #22 - Simple Pig Latin 23) Daily Challenge #23 - Morse Code Decoder 24) Daily Challenge #24 - Shortest Step 25) Daily Challenge #25 - Double Cola 26) Daily Challenge #26 - Ranking Position 27) Daily Challenge #27 - Unlucky Days 28) Daily Challenge #28 - Kill the Monster! 29) Daily Challenge #29 - Xs and Os 30) Daily Challenge #30 - What is the price? 31) Daily Challenge #31 - Count IPv4 Addresses 32) Daily Challenge #32 - Hide Phone Numbers 33) Daily Challenge #33 - Did you mean...? 34) Daily Challenge #34 - WeIrD StRiNg CaSe 35) Daily Challenge #35 - Find the Outlier 36) Daily Challenge #36 - Let's go for a run! 37) Daily Challenge #37 - Name Swap 38) Daily Challenge #38 - Middle Name 39) Daily Challenge #39 - Virus 40) Daily Challenge #40 - Counting Sheep 41) Daily Challenge #41 - Greed is Good 42) Daily Challenge #42 - Caesar Cipher 43) Daily Challenge #43 - Boardgame Fight Resolver 44) Daily Challenge #44 - Mexican Wave 45) Daily Challenge #45 - Change Machine 46) Daily Challenge #46 - ??? 47) Daily Challenge #47 - Alphabets 48) Daily Challenge #48 - Facebook Likes 49) Daily Challenge #49 - Dollars and Cents 50) Daily Challenge #50 - Number Neighbor 51) Daily Challenge #51 - Valid Curly Braces 52) Daily Challenge #52 - Building a Pyramid 53) Daily Challenge #53 - Faro Shuffle 54) Daily Challenge #54 - What century is it? 55) Daily Challenge #55 - Building a Pile of Cubes 56) Daily Challenge #56 - Coffee Shop 57) Daily Challenge #57 - BMI Calculator 58) Daily Challenge #58 - Smelting Iron Ingots 59) Daily Challenge #59 - Snail Sort 60) Daily Challenge #60 - Find the Missing Letter 61) Daily Challenge #61 - Evolution Rate 62) Daily Challenge #62 - Josephus Survivor 63) Daily Challenge #63- Two Sum 64) Daily Challenge #64- Drying Potatoes 65) Daily Challenge #65- A Disguised Sequence 66) Daily Challenge #66- Friend List 67) Daily Challenge #67- Phone Directory 68) Daily Challenge #68 - Grade Book 69) Daily Challenge #69 - Going to the Cinema 70) Daily Challenge #70 - Pole Vault Competition Results 71) Daily Challenge #71 - See you next Happy Year 72) Daily Challenge #72 - Matrix Shift 73) Daily Challenge #73 - ATM Heist 74) Daily Challenge #74 - Free Pizza 75) Daily Challenge #75 - Set Alarm 76) Daily Challenge #76 - Bingo! (or not...) 77) Daily Challenge #77 - Bird Mountain 78) Daily Challenge #78 - Number of Proper Fractions with Denominator d 79) Daily Challenge #79 - Connect Four 80) Daily Challenge #80 - Longest Vowel Change 81) Daily Challenge #81 - Even or Odd 82) Daily Challenge #82 - English Beggars 83) Daily Challenge #83 - Deodorant Evaporator 84) Daily Challenge #84 - Third Angle of a Triangle 85) Daily Challenge #85 - Unwanted Dollars 86) Daily Challenge #86 - Wouldn't, not Would. 87) Daily Challenge #87 - Pony Express 88) Daily Challenge #88 - Recursive Ninjas 89) Daily Challenge #89 - Extract domain name from URL 90) Daily Challenge #90 - One Step at a Time 91) Daily Challenge #91 - Bananas 92) Daily Challenge #92 - Boggle Board 93) Daily Challenge #93 - Range Extraction 94) Daily Challenge #94 - Last Digit 95) Daily Challenge #95 - CamelCase Method 96) Daily Challenge #96 - Easter Egg Crush Test 97) Daily Challenge #97 - Greed is Good 98) Daily Challenge #98 - Make a Spiral 99) Daily Challenge #99 - Balance the Scales 100) Daily Challenge #100 - Round Up 101) Daily Challenge #101 - Parentheses Generator 102) Daily Challenge #102 - Pentabonacci 103) Daily Challenge #103 - Simple Symbols 104) Daily Challenge #104 - Matrixify 105) Daily Challenge #105 - High-Sum Matrix Drop 106) Daily Challenge #106 - Average Fuel Consumption 107) Daily Challenge #107 - Escape the Mines 108) Daily Challenge #108 - Find the Counterfeit Coin 109) Daily Challenge #109 - Decorate with Wallpaper 110) Daily Challenge #110 - Love VS. Friendship 111) Daily Challenge #111 - 99 Bottles of Beer 112) Daily Challenge #112 - Functions of Integers on the Cartesian Plane 113) Daily Challenge #113 - Iterative Rotation Cipher 114) Daily Challenge #114 - Speed Control 115) Daily Challenge #115 - Look and Say Sequence 116) Daily Challenge #116 - Shortest Knight Path 117) Daily Challenge #117 - MinMinMax 118) Daily Challenge #118 - Reversing a Process 119) Daily Challenge #119 - Adding Big Numbers 120) Daily Challenge #120 - Growth of a Population 121) Daily Challenge #121 - Who has the most money? 122) Daily Challenge #122 - Clockwise Spirals 123) Daily Challenge #123 - Curry me Softly 124) Daily Challenge #124 - Middle Me 125) Daily Challenge #125 - 23 Matches or More 126) Daily Challenge #126 - The Supermarket Line 127) Daily Challenge #127 - Playing with Passphrases 128) Daily Challenge #128 - Blackjack Scorer 129) Daily Challenge #129 - Clay Pigeon Shooting 130) Daily Challenge #130 - GCD Sum 131) Daily Challenge #131 - Remove Anchor from URL 132) Daily Challenge #132 - Is my friend cheating?

Write a function that will generate all possible combinations of grammatically correct parentheses. The function should be able to work with n pairs of parentheses.

Given n = 3, an example solution set would be:

[
  "((()))",
  "(())()",
  "()(())",
  "()()()",
  "(()())"
]

Looking forward to seeing your solutions!


Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

twitter logo DISCUSS (10)
markdown guide
 

I made it using python.

Edit: Using inbuilt function for generating permutations is a bad idea. This code works fine till n = 5 but then it takes noticeably long long time to execute. For n = 6, it took 1 minute 19 seconds!

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))
 

Quick formatting tip: type python after the three backticks to get python formatting (like '''python but with the correct symbol).

I like how you are using the features Python gives you, even if it took a while for me to get it — after a few minutes I realized that the inner for loop was a check to see if the string i is properly formatted.

 

Thanks for this 👍 I was looking for something like this before posting but couldn't find anything.

 
 

Typescript!

First, solving it with numbers. Each solution string is represented by an array of numbers with number incrementing for "(" and decrementing for ")".
For example, "(())()" is [1, 2, 1, 0, 1, 0]

The recursive helper function "solveWithNumbers" receives the beginning of a solution and returns an array with all complete solutions starting with these numbers.

The function "paren" runs "solveWithNumbers" and then converts the solution to the required format

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));
}

[stackblitz.com/edit/typescript-n51vvd]

 

I tried using C++. Haven't tested it much. I know there exists a method in C++ to generate all permutations of a string. But this program is better optimized. It doesn't check all permutations. It stops following a sequence whenever it runs into a condition from where a valid sequence cannot be generated. For example, whenever number of closing braces are more than number of opening braces, there is no point following that recursion because it will never generate any valid permutations.

/**
 * 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;
}
 

This is an O(n!) because the output is O(n!) - there is no way around it. Still - it can be greatly optimized if we generate the valid combinations in order instead of generating all the combinations and filtering for the valid ones - which both increases the number of combinations we need to generate and forces us to pay for validating each configuration.

First, we need to represent the combinations. It is enough to represent the positions of the opening parenthesis, as we can fill the closing parenthesis when we generate the string. So our data structure will be an n sized vector of positions. The first position is always 0, but we'll keep it in the vector anyway for the sake of simplicity.

What makes a representation valid? The first position - p[0] - must be 0. Technically this means we can just use an n-1 sized vector, but we'll keep it in the vector anyway for the sake of simplicity.

What about the other position? For each k in [1,n), what are the valid values for p[k]? Obviously p[k] > p[k-1] so we have a minimum. The maximum is less obvious but also easy - k * 2. This is the maximum number of characters before it - k opening parenthesis and k closing parenthesis. There cannot be more opening parenthesis because k is the kth, and there cannot be more closing parenthesis because then there won't be enough opening parenthesis to match them.

So, if we have p[0], p[1], ... p[k] we know the valid ranges of p[k+1] - and that's enough to advance p:

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())
    }
}

You can see it in action at play.rust-lang.org/?version=stable...

On my machine, when built with release, it can generate all 35,357,670 combinations for n=16 in between 4 and 5 seconds. Printing them takes much much much longer - even when I redirect the output to /dev/null it takes half a minute, and when I don't it takes forever (didn't let it finish). I suspect other implementations will have similar problems, so you should try to time them without printing the combinations (just print how many you got)

 

I whipped this one up in PHP, going for readability first. As I'm building the solutions from smaller solutions using recursion with a lot of duplicate requests, memoization here is a must.
Also, damn, this requires a lot of memory. At n=16 it crashes when trying to claim 2GB of memory when it already has 5GB used. I'll try to see how far I can get with some optimizations, but I'm not holding my breath on this one.

<?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));
 

Yeah, here is the most memory efficient one I could think of:

<?php
$n = 16;
$solutions = array_fill(0, 16, []);
$solutions[0][] = '';
for ($size = 1; $size <= $n; $size++) { // $i i
    for ($nestSize = 0; $nestSize < $size; $nestSize++) {
        $tailSize = $size - $nestSize - 1;
        $nestPossibilities = count($solutions[$nestSize]);
        $tailPossibilities = count($solutions[$tailSize]);
        for ($i = 0; $i < $nestPossibilities; $i++) {
            for ($j = 0; $j < $tailPossibilities; $j++) {
                $solutions[$size][] = '(' . $solutions[$nestSize][$i] . ')' . $solutions[$tailSize][$j];
            }
        }
    }
}

for ($i = 1; $i <= $n; $i++) {
    $count = count($solutions[$i]);
    printf("%02d: %d\n", $i, $count);
}

It now fails with a different amount of memory allocated, but still doesn't reach 16.

With the way it grows, I'm guessing the number of strings for 16 pairs of parentheses to be around 30 million. With each string being 33 characters (16 opening + 16 closing parenthesis, + 1 null terminator) I'm looking at almost 8 GB of memory for the strings alone. No wonder my laptop can't compute it.

 

This is another case where dynamic programming is useful.
Refactoring the problem as "Give me all the valid (eg. don't end in an open) parenthesis combos of some given string length which, in aggregate, close some given number of parentheses along their length"
Then we get a nice substructure to work with: the result for some given length is just an easy convolution on the result for a smaller length.

Hmm, that came out a bit confusing.
Hopefully the code is easier to follow...

TypeScript:

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 });

A couple of runs...

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)
Classic DEV Post from Apr 4

Design Patterns in Java

I thought it would be a fun to write a series of blog posts looking at differen...

dev.to staff profile image
The hardworking team behind dev.to ❤️