Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 406
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:
Day406
Resolves #821.

Patch:
diff --git a/README.md b/README.md
index 9ba14eb..71bbb13 100644
--- a/README.md
+++ b/README.md
@@ -403,4 +403,5 @@ problems from
 * [Day 403](https://github.com/vaskoz/dailycodingproblem-go/issues/815)
 * [Day 404](https://github.com/vaskoz/dailycodingproblem-go/issues/817)
 * [Day 405](https://github.com/vaskoz/dailycodingproblem-go/issues/819)
+* [Day 406](https://github.com/vaskoz/dailycodingproblem-go/issues/821)
 
diff --git a/day402/problem.go b/day402/problem.go
index 1fbde27..8f95920 100644
--- a/day402/problem.go
+++ b/day402/problem.go
@@ -1,4 +1,4 @@
-package day362
+package day402
 
 import (
 	"fmt"
diff --git a/day403/problem.go b/day403/problem.go
index b6d41a4..1ec54c0 100644
--- a/day403/problem.go
+++ b/day403/problem.go
@@ -1,4 +1,4 @@
-package day45
+package day403
 
 import (
 	"math/rand"
diff --git a/day404/problem.go b/day404/problem.go
index a5329dc..2bd6d33 100644
--- a/day404/problem.go
+++ b/day404/problem.go
@@ -1,4 +1,4 @@
-package day21
+package day404
 
 import "sort"
 
diff --git a/day405/problem.go b/day405/problem.go
index 2c6bd2a..649eea1 100644
--- a/day405/problem.go
+++ b/day405/problem.go
@@ -1,4 +1,4 @@
-package day93
+package day405
 
 // BinaryTree is a binary tree: left & right children.
 type BinaryTree struct {
diff --git a/day406/problem.go b/day406/problem.go
new file mode 100644
index 0000000..a872903
--- /dev/null
+++ b/day406/problem.go
@@ -0,0 +1,62 @@
+package day406
+
+// 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/day402/problem_test.go b/day402/problem_test.go
index cd3a4a7..a7dfdb4 100644
--- a/day402/problem_test.go
+++ b/day402/problem_test.go
@@ -1,4 +1,4 @@
-package day362
+package day402
 
 import (
 	"reflect"
diff --git a/day403/problem_test.go b/day403/problem_test.go
index a14c733..d0966ac 100644
--- a/day403/problem_test.go
+++ b/day403/problem_test.go
@@ -1,4 +1,4 @@
-package day45
+package day403
 
 import "testing"
 
diff --git a/day404/problem_test.go b/day404/problem_test.go
index 5a80205..8a2d64a 100644
--- a/day404/problem_test.go
+++ b/day404/problem_test.go
@@ -1,4 +1,4 @@
-package day21
+package day404
 
 import "testing"
 
diff --git a/day405/problem_test.go b/day405/problem_test.go
index 29905e9..ea64cc1 100644
--- a/day405/problem_test.go
+++ b/day405/problem_test.go
@@ -1,4 +1,4 @@
-package day93
+package day405
 
 import "testing"
 
diff --git a/day406/problem_test.go b/day406/problem_test.go
new file mode 100644
index 0000000..cb299c2
--- /dev/null
+++ b/day406/problem_test.go
@@ -0,0 +1,30 @@
+package day406
+
+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)
+		}
+	}
+}