ブール式の文字列を括弧で括って目的の結果に評価する方法の数を数える方法

Question

CTCIの真ん中、8.14：記号0（偽）、1（真）、&（AND） | （OR）、および^（XOR）、および所望のブール結果値の結果を評価するように、式をかっこする方法の数を数える関数を実装します。

私は、可能なすべてのコンボを計算し、希望の結果と一致する場合はそれを配列に追加し（コンボ）、その結果の長さを返すブルートフォースアプローチを試みています。それはほとんどの表現ではうまくいくようですが、2番目の例ではありません。私は何が失われているように見えるのですか？

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

それは最初のもののために働く与えられた2例では

が、2番目ない...

console.log(countEval('1^0|0|1', false)); // 2, correct 
console.log(countEval('0&0&0&1^1|0', true)); // 30, should be 10!?!?! 

Answer 1

バグ

あなたのプログラムは、アカウントの重複を考慮されていません。

例

は、あなたのプログラムs = '1|1|1|1'を考えてみましょう。

深度優先検索反復の1つで、アルゴリズムでは、減算がs = (1|1)|1|1になります。次に、同じ検索でより深い再帰レベルで、アルゴリズムは減算を行いますs = (1|1)|(1|1)。今度はsが完全に削減されているので、コンボの長さを増やします。

異なる奥行き検索の繰り返しでは、アルゴリズムでは最初に縮小を行いますs = 1|1|(1|1)。次に、同じ検索でより深い再帰レベルで、アルゴリズムは減算を行いますs = (1|1)|(1|1)。今度はsが完全に削減されているので、コンボの長さを増やします。

どちらの場合も、sは同じ方法でカッコで括られていることに注意してください。プログラムで重複が考慮されていません。

Aよりよい解決策は

多くの時間、問題が何かを行うことができますいくつかの方法を求めている、これは通常、動的プログラミングは潜在的な解決策になることができることは大きな指標です。この問題に対する再発の関係は少し難解です。

「原理」演算子を選択して、左右の値がtrueまたはfalseと評価される方法の数を決定するだけで済みます。次に、「原理」演算子と目標ブール値に基づいて、我々が選んだ演算子が「原理」演算子であると仮定して、式が目標ブール値に評価できる方法の数式を導出することができる。

コード

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