How to count number of ways to parenthesize boolean expression string to evaluate to desired result

user_1131327 0
Viewed 808

Straight out of CTCI, 8.14: Given a boolean expression consisting of the symbols 0 (false), 1 (true), & (AND), | (OR), and ^(XOR), and a desired boolean result value result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result.

I'm attempting a brute force approach that calculates every single possible combo, if matches desired result, add it to an array(combos) and return that result length. It seems to work for most expressions, but not the 2nd example given. What do I seem to be missing?

function countEval(s, goalBool, combos = []) {
    // on first call make s into array since theyre easier to work with
    if (!(s instanceof Array)) {
        // and turn 1s and 0s into their bool equivalent
        s = s.split('').map((item) => {
            if (item === '1') {
                return true;
            } else if (item === '0'){
                return false;
            } else {
                return item;
            }
        });
    }
    if (s.length === 1 && s[0] === goalBool) {
        combos.push(s[0]); // can be anything really
    } else {
        for (let i = 0; i < s.length - 2; i = i + 2) {
            // splice out the next 3 items
            const args = s.splice(i, 3);
            // pass them to see what they evaluate too
            const result = evalHelper(args[0], args[1], args[2]);
            // splice that result back in s array
            s.splice(i, 0, result);
            // pass that array to recurse
            countEval(s, goalBool, combos);
            // remove said item that was just put in
            s.splice(i, 1);
            // and reset array for next iteration
            s.splice(i, 0, ...args);
        }
    }
    return combos.length;
}

function evalHelper(a, op, b) {
    if (op === '|') {
        return a || b;
    } else if (op === '&') {
        return a && b;
    } else if (op === '^') {
        return a !== b;
    }
}

With the 2 examples given it works for the first one, but not the second...

console.log(countEval('1^0|0|1', false)); // 2, correct
console.log(countEval('0&0&0&1^1|0', true)); // 30, should be 10!?!?!
dynamic-programming boolean-expression recursion algorithm javascript
1 Answers

The Bug

Your program is not taking into account overlap.

Example

Consider your program when s = '1|1|1|1'.

In one of the depth-first search iterations, your algorithm will make the reduction s = (1|1)|1|1. Then in a deeper recursive level in the same search, your algorithm will make the reduction s = (1|1)|(1|1). Now s is fully reduced, so you increment the length of combos.

In a different depth-first search iteration, your algorithm will first make the reduction s = 1|1|(1|1). Then in a deeper recursive level in the same search, your algorithm will make the reduction s = (1|1)|(1|1). Now s is fully reduced, so you increment the length of combos.

Notice that for both cases, s was parenthesized the same way, thus your program does not take into account overlap.

A Better Solution

A lot of times, when a problem is asking the number of ways something can be done, this is usually a big indicator that dynamic programming could be a potential solution. The recurrence relation to this problem is a bit tricky.

We just need to pick a "principle" operator, then determine the number of ways the left and right side could evaluate to true or false. Then, based on the "principle" operator and the goal boolean, we can derive a formula for the number of ways the expression could evaluate to the goal boolean given that the operator we picked was the "principle" operator.

Code

function ways(expr, res, i, j, cache, spaces) {
  if (i == j) {
    return parseInt(expr[i]) == res ? 1 : 0;
  } else if (!([i, j, res] in cache)) {
    var ans = 0;
    for (var k = i + 1; k < j; k += 2) {
      var op = expr[k];
      var leftTrue = ways(expr, 1, i, k - 1, cache);
      var leftFalse = ways(expr, 0, i, k - 1, cache);
      var rightTrue = ways(expr, 1, k + 1, j, cache);
      var rightFalse = ways(expr, 0, k + 1, j, cache);
      if (op == '|') {
        if (res) {
          ans += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue;
        } else {
          ans += leftFalse * rightFalse;
        }
      } else if (op == '^') {
        if (res) {
          ans += leftTrue * rightFalse + leftFalse * rightTrue;
        } else {
          ans += leftTrue * rightTrue + leftFalse * rightFalse;
        }
      } else if (op == '&') {
        if (res) {
          ans += leftTrue * rightTrue;
        } else {
          ans += leftFalse * rightFalse + leftTrue * rightFalse + leftFalse * rightTrue;
        }
      }
    }
    cache[[i, j, res]] = ans;
  }
  return cache[[i, j, res]];
}

function countEval(expr, res) {
  return ways(expr, res ? 1 : 0, 0, expr.length - 1, {});
}
user_64543870
Related