DEV Community

Discussion on: Daily Challenge #101 - Parentheses Generator

View post
Collapse
 
dwilmer profile image
Daan Wilmer • • Edited

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));
Collapse
 
dwilmer profile image
Daan Wilmer • • Edited

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.