Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 227
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Boggle is a game played on a 4 x 4 grid of letters. The goal is to find as many words as possible that can be formed by a sequence of adjacent letters in the grid, using each cell at most once. Given a game board and a dictionary of valid words, implement a Boggle solver.

Pull request description:
Day227
Resolves #469.

Patch:
diff --git a/README.md b/README.md
index 8bb7875..f389e11 100644
--- a/README.md
+++ b/README.md
@@ -237,6 +237,7 @@ problems from
 * [Day 224](https://github.com/vaskoz/dailycodingproblem-go/issues/462)
 * [Day 225](https://github.com/vaskoz/dailycodingproblem-go/issues/465)
 * [Day 226](https://github.com/vaskoz/dailycodingproblem-go/issues/467)
+* [Day 227](https://github.com/vaskoz/dailycodingproblem-go/issues/469)
 * [Day 228](https://github.com/vaskoz/dailycodingproblem-go/issues/470)
 * [Day 230](https://github.com/vaskoz/dailycodingproblem-go/issues/473)
 * [Day 231](https://github.com/vaskoz/dailycodingproblem-go/issues/475)
diff --git a/day227/problem.go b/day227/problem.go
new file mode 100644
index 0000000..48b6c05
--- /dev/null
+++ b/day227/problem.go
@@ -0,0 +1,79 @@
+package day227
+
+// Board is an NxN board of runes.
+type Board [][]rune
+
+type trie struct {
+	word    bool
+	letters map[rune]*trie
+}
+
+// BoggleSolver takes a boggle board (2D runes NxN) and a dictionary
+// of valid words.
+func BoggleSolver(board Board, dict []string) []string {
+	t := buildTrie(dict)
+	visited := make([][]bool, len(board))
+	for i := range visited {
+		visited[i] = make([]bool, len(board[i]))
+	}
+	result := make([]string, 0, len(dict))
+	for i := range board {
+		for j := range board[i] {
+			result = append(result, boggleSolver(board, visited, t, []rune{}, i, j)...)
+		}
+	}
+	// dedup
+	m := make(map[string]struct{})
+	for _, w := range result {
+		m[w] = struct{}{}
+	}
+	result = make([]string, 0, len(m))
+	for w := range m {
+		result = append(result, w)
+	}
+	return result
+}
+
+func boggleSolver(board Board, visited [][]bool, t *trie, path []rune, i, j int) []string {
+	if i < 0 || i >= len(board) ||
+		j < 0 || j >= len(board[i]) ||
+		visited[i][j] || t.letters[board[i][j]] == nil {
+		return nil
+	}
+	var result []string
+	path = append(path, board[i][j])
+	t = t.letters[board[i][j]]
+	if t.word {
+		result = append(result, string(path))
+	}
+	visited[i][j] = true
+	// visit 8 directions: up,down,left,right and the 4 diagonals
+	result = append(result, boggleSolver(board, visited, t, path, i-1, j)...)   // up
+	result = append(result, boggleSolver(board, visited, t, path, i+1, j)...)   // down
+	result = append(result, boggleSolver(board, visited, t, path, i, j-1)...)   // left
+	result = append(result, boggleSolver(board, visited, t, path, i, j+1)...)   // right
+	result = append(result, boggleSolver(board, visited, t, path, i-1, j-1)...) // up-left
+	result = append(result, boggleSolver(board, visited, t, path, i-1, j+1)...) // up-right
+	result = append(result, boggleSolver(board, visited, t, path, i+1, j-1)...) // down-left
+	result = append(result, boggleSolver(board, visited, t, path, i+1, j+1)...) // down-right
+	visited[i][j] = false
+	return result
+}
+
+func buildTrie(dict []string) *trie {
+	root := &trie{false, make(map[rune]*trie)}
+	for _, word := range dict {
+		curr := root
+		for _, r := range word {
+			if next, found := curr.letters[r]; found {
+				curr = next
+			} else {
+				next = &trie{false, make(map[rune]*trie)}
+				curr.letters[r] = next
+				curr = next
+			}
+		}
+		curr.word = true
+	}
+	return root
+}


Test patch:
diff --git a/day227/problem_test.go b/day227/problem_test.go
new file mode 100644
index 0000000..95e160b
--- /dev/null
+++ b/day227/problem_test.go
@@ -0,0 +1,48 @@
+package day227
+
+import "testing"
+
+var testcases = []struct {
+	board Board
+	dict  []string
+	valid []string
+}{
+	{Board{
+		[]rune("aaga"),
+		[]rune("abaf"),
+		[]rune("acea"),
+		[]rune("adaa"),
+	},
+		[]string{"abcdefga", "abcda", "foobar"},
+		[]string{"abcdefga", "abcda"},
+	},
+}
+
+func TestBoggleSolver(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		words := BoggleSolver(tc.board, tc.dict)
+		m := make(map[string]struct{}, len(tc.valid))
+		for _, w := range tc.valid {
+			m[w] = struct{}{}
+		}
+		for _, w := range words {
+			if _, found := m[w]; !found {
+				t.Errorf("got word %v, but didn't expect it", w)
+			} else {
+				delete(m, w)
+			}
+		}
+		if len(m) != 0 {
+			t.Errorf("expected more words: %v", m)
+		}
+	}
+}
+
+func BenchmarkBoggleSolver(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BoggleSolver(tc.board, tc.dict)
+		}
+	}
+}