Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 308
Good morning! Here's your coding interview problem for today.

This problem was asked by Quantcast.

You are presented with an array representing a Boolean expression. The elements are of two kinds:

`T` and `F`, representing the values True and False.
`&, |, and ^`, representing the bitwise operators for `AND, OR, and XOR`.
Determine the number of ways to group the array elements using parentheses so that the entire expression evaluates to True.

For example, suppose the input is `['F', '|', 'T', '&', 'T']`. In this case, there are two acceptable groupings: `(F | T) & T` and `F | (T & T)`.

Pull request:
Day308
Resolves #629.

Patch:
diff --git a/README.md b/README.md
index 8fe170d..96d4618 100644
--- a/README.md
+++ b/README.md
@@ -317,6 +317,7 @@ problems from
 * [Day 305](https://github.com/vaskoz/dailycodingproblem-go/issues/622)
 * [Day 306](https://github.com/vaskoz/dailycodingproblem-go/issues/626)
 * [Day 307](https://github.com/vaskoz/dailycodingproblem-go/issues/628)
+* [Day 308](https://github.com/vaskoz/dailycodingproblem-go/issues/629)
 * [Day 309](https://github.com/vaskoz/dailycodingproblem-go/issues/631)
 * [Day 310](https://github.com/vaskoz/dailycodingproblem-go/issues/633)
 * [Day 311](https://github.com/vaskoz/dailycodingproblem-go/issues/635)
diff --git a/day308/problem.go b/day308/problem.go
new file mode 100644
index 0000000..a7b9ae4
--- /dev/null
+++ b/day308/problem.go
@@ -0,0 +1,62 @@
+package day308
+
+// CountParensEqualTrue returns the number of possible
+// paren patterns that evaluate to True.
+// Runs in O(N^3) time and O(N^2) extra space.
+func CountParensEqualTrue(input []rune) int {
+	var sym, ops []rune
+
+	for i := range input {
+		if i%2 == 0 {
+			sym = append(sym, input[i])
+		} else {
+			ops = append(ops, input[i])
+		}
+	}
+
+	f := make([][]int, len(sym))
+	t := make([][]int, len(sym))
+
+	for i := range f {
+		f[i] = make([]int, len(sym))
+		t[i] = make([]int, len(sym))
+
+		if sym[i] == 'F' {
+			f[i][i] = 1
+		}
+
+		if sym[i] == 'T' {
+			t[i][i] = 1
+		}
+	}
+
+	for gap := 1; gap < len(sym); gap++ {
+		for i, j := 0, gap; j < len(sym); i, j = i+1, j+1 {
+			t[i][j] = 0
+			f[i][j] = 0
+
+			for g := 0; g < gap; g++ {
+				k := i + g
+				tik := t[i][k] + f[i][k]
+				tkj := t[k+1][j] + f[k+1][j]
+
+				if ops[k] == '&' {
+					t[i][j] += t[i][k] * t[k+1][j]
+					f[i][j] += tik*tkj - t[i][k]*t[k+1][j]
+				}
+
+				if ops[k] == '|' {
+					f[i][j] += f[i][k] * f[k+1][j]
+					t[i][j] += tik*tkj - f[i][k]*f[k+1][j]
+				}
+
+				if ops[k] == '^' {
+					t[i][j] += f[i][k]*t[k+1][j] + t[i][k]*f[k+1][j]
+					f[i][j] += t[i][k]*t[k+1][j] + f[i][k]*f[k+1][j]
+				}
+			}
+		}
+	}
+
+	return t[0][len(t[0])-1]
+}


Test patch:
diff --git a/day308/problem_test.go b/day308/problem_test.go
new file mode 100644
index 0000000..676b828
--- /dev/null
+++ b/day308/problem_test.go
@@ -0,0 +1,30 @@
+package day308
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	input    []rune
+	expected int
+}{
+	{[]rune{'F', '|', 'T', '&', 'T'}, 2},
+	{[]rune{'T', '|', 'T', '&', 'F', '^', 'T'}, 4},
+}
+
+func TestCountParensEqualTrue(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if result := CountParensEqualTrue(tc.input); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkCountParensEqualTrue(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CountParensEqualTrue(tc.input)
+		}
+	}
+}