The problem (original found here) is to be given a random string of t's and f's (standing for boolean true/false) separated by one of & | ^ e.g. "T&F|F^T&T^F" and write a function to return the number of unique bracket placements (where total # of bracket pairs = # of t/f's - 1) for which the overall expression will evaluate to true. (T&((F^T)|(T&F))) is true. My code returns the correct answer, but not in the allotted time (for very long input strings). I'm looking for a hint as to whether I need to understand an algorithm trick that drastically reduces iterations/recursions, or my code just isn't efficient enough.
My algorithm essentially iterates through every pairing, but after reducing any given tf pair to a single new value, it checks the resulting string of char/bracket placement against a lookup table to see if that pattern has been reached previously, and continues without recursing if it has.
For instance if the input is T T F T F F T: If we're on a permutation where the first pair is (T T)F T F F T, and the second pair is (T T)F T(F F)T, well, eventually we'll have a permutation whose first pair is T T F T(F F)T and whose second is (T T)F T(F F)T, at which point the table will show this path to have already been traversed and will proceed to the next permutation.
I also perform a check each time a tf string is reduced e.g. (T&F)^F|T&T --> F^F|T&T to make sure there is at least one T left, since F^F|F&F needs no more recursion.
I feel like there must be a way to reduce the amount of traversal beyond what I've done. (CodeWars discussion here)
// C++. The input will be given as two strings, e.g. "ttfftf","&&^|^"
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <iostream>
using namespace std;
using pairVec = vector<pair<string,char>>;
unordered_map<string, bool> usedPatMap{};
inline char tOrF(char c1, char c2, char op){
if(c1=='f') {
if(c2=='f') return 'f';
else { // c2=='t'
if(op=='&') return 'f';
return 't';
}
}
else { //c1=='t'
if(c2=='f') {
if(op=='&') return 'f';
return 't';
}
else { // c2=='t'
if(op=='^') return 'f';
return 't';
}
}
}
void traverse(pairVec& tfs, string ops, int64_t& ct) {
for(int i = 0; i + 1 < tfs.size(); ++i) {
char tf = tOrF(tfs[i].second, tfs[i+1].second, ops[i]);
string newBracePat = "(" + tfs[i].first + tfs[i+1].first + ")";
pairVec tfs2 = tfs;
string ops2 = ops;
auto p = tfs2.erase(tfs2.begin() + i, tfs2.begin() + 2 + i);
tfs2.insert(p,make_pair(newBracePat,tf));
if(find_if(tfs2.begin(), tfs2.end(),
[](auto x){ return x.second=='t';})==tfs2.end()) continue;
string checkStr;
for(auto pr:tfs2) checkStr.append(pr.first);
if(!usedPatMap[checkStr]) usedPatMap[checkStr] = true;
else continue;
ops2.erase(ops2.begin()+i);
if(ops2.empty()) {
if(tfs2[0].second=='t') ++ct;
return; }
traverse(tfs2, ops2, ct);
}
}
int64_t solve(const string &s, const string &ops) {
if(s.length() < 2 || ops.length()!=s.length() - 1) return 0;
int64_t ct = 0;
string s2 = s, ops2 = ops;
pairVec v(s2.length(),{"x",'t'});
for(int i = 0; i < s2.length(); ++i) if(s2[i]=='f') v[i].second = 'f';
traverse(v, ops2, ct);
return ct;
}
int main(int argc, char **argv) {
cout<<solve("ttftfftftf","|&^&&||^&");
}
From a brief look at your code I notice that you actually construct strings with the parentheses inserted at different places. This certainly represents a lot of manipulation that actually is not necessary.
No string manipulation is needed. It should suffice to calculate the results for substrings of your input, and collect for each the number of false-results and the number of true-results. If you start with the smallest substrings, having just one f or t value, then it is trivial. Then you can rely on those results to calculate the counts for substrings which have two operands and one operator. This gives a new layer of results. For the next layers you need to also consider the choice of the operator you will have at the top (with a left and right side operand of smaller sizes, for which you already have the counts).
This is a description of a bottom-up dynamic programming solution.
I provide here C style code, using plain arrays. For C++ it would be good to use vectors instead as you were doing:
int64_t solve(const std::string &s, const std::string &ops)
{
size_t n = s.length();
int64_t dp[n][n][2]; // Dynamic programming tabulation
for (size_t i = 0; i < n; i++) {
int64_t isTrue = (s[i] == 't');
dp[0][i][0] = 1 - isTrue;
dp[0][i][1] = isTrue;
}
int64_t *counters = dp[0][0];
for (size_t opCount = 1; opCount < n; opCount++) {
for (size_t start = 0; start + opCount < n; start++) {
counters = dp[opCount][start];
counters[0] = counters[1] = 0;
for (size_t leftOpCount = 0; leftOpCount < opCount; leftOpCount++) {
int64_t *left = dp[leftOpCount][start];
int64_t *right = dp[opCount - 1 - leftOpCount][start + leftOpCount + 1];
int64_t ff = left[0] * right[0];
int64_t ft = left[0] * right[1] + left[1] * right[0];
int64_t tt = left[1] * right[1];
char op = ops[start + leftOpCount];
if (op == '&') {
counters[0] += ff + ft;
counters[1] += tt;
} else if (op == '|') {
counters[0] += ff;
counters[1] += tt + ft;
} else {
counters[0] += ff + tt;
counters[1] += ft;
}
}
}
}
return counters[1];
}
The first dimension of dp represents the number of operators in the considered expression. The second dimension has the start index in s where this sub-expression starts. The third dimension has just two entries: one for the false-counts and one for the true-counts.