Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 345
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

You are given a set of synonyms, such as `(big, large)` and `(eat, consume)`. Using this set, determine if two sentences with the same number of words are equivalent.

For example, the following two sentences are equivalent:
```
"He wants to eat food."
"He wants to consume food."
```
Note that the synonyms `(a, b)` and `(a, c)` do not necessarily imply `(b, c)`: consider the case of `(coach, bus)` and `(coach, teacher)`.

Follow-up: what if we can assume that `(a, b)` and `(a, c)` do in fact imply `(b, c)`?

Pull request description:
Day345
Resolves #687.

Patch:
diff --git a/README.md b/README.md
index 6701573..ff0d3c7 100644
--- a/README.md
+++ b/README.md
@@ -333,5 +333,6 @@ problems from
 * [Day 339](https://github.com/vaskoz/dailycodingproblem-go/issues/676)
 * [Day 340](https://github.com/vaskoz/dailycodingproblem-go/issues/679)
 * [Day 342](https://github.com/vaskoz/dailycodingproblem-go/issues/682)
+* [Day 345](https://github.com/vaskoz/dailycodingproblem-go/issues/687)
 * [Day 346](https://github.com/vaskoz/dailycodingproblem-go/issues/688)
 * [Day 347](https://github.com/vaskoz/dailycodingproblem-go/issues/689)
diff --git a/day345/problem.go b/day345/problem.go
new file mode 100644
index 0000000..8cd322d
--- /dev/null
+++ b/day345/problem.go
@@ -0,0 +1,73 @@
+package day345
+
+import "strings"
+
+// Thesaurus represents a thesaurus of words.
+type Thesaurus map[string]map[string]struct{}
+
+// AreSentencesEquivalentTransitive answers if the two sentences are
+// equivalent given the Thesaurus.
+func AreSentencesEquivalentTransitive(s1, s2 string, thes Thesaurus) bool {
+	p1 := strings.Split(s1, " ")
+	p2 := strings.Split(s2, " ")
+	if len(p1) != len(p2) {
+		return false
+	}
+	newThes := make(Thesaurus)
+	for word := range thes {
+		newThes[word] = make(map[string]struct{})
+		words := make([]string, 0, len(thes[word]))
+		for next := range thes[word] {
+			words = append(words, next)
+			newThes[word][next] = struct{}{}
+		}
+		for i := range words {
+			for j := i + 1; j < len(words); j++ {
+				if _, exists := thes[words[i]]; !exists {
+					newThes[words[i]] = make(map[string]struct{})
+				}
+				newThes[words[i]][words[j]] = struct{}{}
+			}
+		}
+	}
+	thes = newThes
+	for i := range p1 {
+		if p1[i] != p2[i] &&
+			!isConvertible(p1[i], p2[i], thes, make(map[string]struct{})) {
+			return false
+		}
+	}
+	return true
+}
+
+// AreSentencesEquivalent answers if the two sentences are
+// equivalent given the Thesaurus.
+func AreSentencesEquivalent(s1, s2 string, thes Thesaurus) bool {
+	p1 := strings.Split(s1, " ")
+	p2 := strings.Split(s2, " ")
+	if len(p1) != len(p2) {
+		return false
+	}
+	for i := range p1 {
+		if p1[i] != p2[i] &&
+			!isConvertible(p1[i], p2[i], thes, make(map[string]struct{})) {
+			return false
+		}
+	}
+	return true
+}
+
+func isConvertible(src, target string, thes Thesaurus,
+	visited map[string]struct{}) bool {
+	if src == target {
+		return true
+	}
+	visited[src] = struct{}{}
+	for next := range thes[src] {
+		if isConvertible(next, target, thes, visited) {
+			return true
+		}
+	}
+	delete(visited, src)
+	return false
+}


Test patch:
diff --git a/day345/problem_test.go b/day345/problem_test.go
new file mode 100644
index 0000000..fc35f5c
--- /dev/null
+++ b/day345/problem_test.go
@@ -0,0 +1,100 @@
+package day345
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	sentence1, sentence2 string
+	thesaurus            Thesaurus
+	expected             bool
+	expectedTransitive   bool
+}{
+	{
+		"he wants to eat food",
+		"he wants to consume food",
+		Thesaurus{
+			"big": {
+				"large": struct{}{},
+			},
+			"eat": {
+				"consume": struct{}{},
+			},
+		},
+		true,
+		true,
+	},
+	{
+		"he wants to eat food",
+		"he wants to devour food",
+		Thesaurus{
+			"eat": {
+				"consume": struct{}{},
+			},
+		},
+		false,
+		false,
+	},
+	{
+		"he wants to eat food",
+		"he wants to consume food today",
+		Thesaurus{
+			"big": {
+				"large": struct{}{},
+			},
+			"eat": {
+				"consume": struct{}{},
+			},
+		},
+		false,
+		false,
+	},
+	{
+		"he wants to devour food",
+		"he wants to inhale food",
+		Thesaurus{
+			"eat": {
+				"consume": struct{}{},
+				"devour":  struct{}{},
+				"inhale":  struct{}{},
+			},
+		},
+		false,
+		true,
+	},
+}
+
+func TestAreSentencesEquivalentTransitive(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := AreSentencesEquivalentTransitive(tc.sentence1,
+			tc.sentence2, tc.thesaurus); result != tc.expectedTransitive {
+			t.Errorf("TCID %d Expected %v, got %v", tcid,
+				tc.expectedTransitive, result)
+		}
+	}
+}
+
+func BenchmarkAreSentencesEquivalentTransitive(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			AreSentencesEquivalentTransitive(tc.sentence1, tc.sentence2, tc.thesaurus)
+		}
+	}
+}
+
+func TestAreSentencesEquivalent(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := AreSentencesEquivalent(tc.sentence1, tc.sentence2, tc.thesaurus); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkAreSentencesEquivalent(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			AreSentencesEquivalent(tc.sentence1, tc.sentence2, tc.thesaurus)
+		}
+	}
+}