Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 98
Good morning! Here's your coding interview problem for today.

This problem was asked by Coursera.

Given a 2D board of characters and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example, given the following board:
```
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
exists(board, "ABCCED") returns true, exists(board, "SEE") returns true, exists(board, "ABCB") returns false.
```

Pull request:
Day98
Resolves #204.

Patch:
diff --git a/README.md b/README.md
index 343198e..2636fd1 100644
--- a/README.md
+++ b/README.md
@@ -106,4 +106,5 @@ problems from
 * [Day 95](https://github.com/vaskoz/dailycodingproblem-go/issues/198)
 * [Day 96](https://github.com/vaskoz/dailycodingproblem-go/issues/200)
 * [Day 97](https://github.com/vaskoz/dailycodingproblem-go/issues/203)
+* [Day 98](https://github.com/vaskoz/dailycodingproblem-go/issues/204)
 * [Day 99](https://github.com/vaskoz/dailycodingproblem-go/issues/205)
diff --git a/day98/problem.go b/day98/problem.go
new file mode 100644
index 0000000..e034d8e
--- /dev/null
+++ b/day98/problem.go
@@ -0,0 +1,100 @@
+package day98
+
+// Board is a 2D grid of characters.
+type Board [][]rune
+
+// Position represents a Row and Col position
+// on the 2D board.
+type Position struct {
+	Row, Col int
+}
+
+// DoesExistSeqAdj returns true if the word exists sequentially in
+// adjacent cells. Cells can not be reused to achieve this goal.
+// Returns false otherwise.
+func DoesExistSeqAdj(board Board, word string) bool {
+	letters := []rune(word)
+	exists := false
+	for row := range board {
+		for col := range board[row] {
+			exists = exists || search(board, row, col, letters, make(map[Position]struct{}))
+			if exists {
+				return true
+			}
+		}
+	}
+	return false
+}
+
+func search(board Board, row, col int, letters []rune, used map[Position]struct{}) bool {
+	if len(letters) == 0 {
+		return true
+	}
+	if board[row][col] != letters[0] {
+		return false
+	}
+	pos := Position{row, col}
+	if _, found := used[pos]; found {
+		return false
+	}
+	used[pos] = struct{}{}
+	// go up
+	if search(board, up(row, len(board)), col, letters[1:], used) {
+		return true
+	}
+	// go left
+	if search(board, row, left(col, len(board[0])), letters[1:], used) {
+		return true
+	}
+	// go right
+	if search(board, row, right(col, len(board[0])), letters[1:], used) {
+		return true
+	}
+	// go down
+	if search(board, down(row, len(board)), col, letters[1:], used) {
+		return true
+	}
+
+	delete(used, pos)
+	return false
+}
+
+func up(row, limit int) int {
+	var r int
+	if row == 0 {
+		r = limit - 1
+	} else {
+		r = row - 1
+	}
+	return r
+}
+
+func down(row, limit int) int {
+	var r int
+	if row == limit-1 {
+		r = 0
+	} else {
+		r = row + 1
+	}
+	return r
+}
+
+func left(col, limit int) int {
+	var c int
+	if col == 0 {
+		c = limit - 1
+	} else {
+		c = col - 1
+	}
+	return c
+}
+
+func right(col, limit int) int {
+	var c int
+	if col == limit-1 {
+		c = 0
+	} else {
+		c = col + 1
+	}
+	return c
+}


Test patch:
diff --git a/day98/problem_test.go b/day98/problem_test.go
new file mode 100644
index 0000000..60a7515
--- /dev/null
+++ b/day98/problem_test.go
@@ -0,0 +1,57 @@
+package day98
+
+import "testing"
+
+var testcases = []struct {
+	board    Board
+	word     string
+	expected bool
+}{
+	{Board{
+		[]rune("ABCE"),
+		[]rune("SFCS"),
+		[]rune("ADEE"),
+	}, "ABCCED", true},
+	{Board{
+		[]rune("ABCE"),
+		[]rune("SFCS"),
+		[]rune("ADEE"),
+	}, "SEE", true},
+	{Board{
+		[]rune("ABCE"),
+		[]rune("SFCS"),
+		[]rune("ADEE"),
+	}, "ABCB", false},
+	{Board{
+		[]rune("ABCE"),
+		[]rune("SFCS"),
+		[]rune("ADEE"),
+	}, "ABCESCFSADEE", true},
+	{Board{
+		[]rune("ABCE"),
+		[]rune("SFCS"),
+		[]rune("ADEE"),
+	}, "ABCESCFSADEEA", false},
+	{Board{
+		[]rune("ABCE"),
+		[]rune("SFCS"),
+		[]rune("ADEE"),
+	}, "BCEA", true},
+}
+
+func TestDoesExistSeqAdj(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := DoesExistSeqAdj(tc.board, tc.word); result != tc.expected {
+			t.Errorf("TC%d expected %v got %v", tcid, tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkDoesExistSeqAdj(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			DoesExistSeqAdj(tc.board, tc.word)
+		}
+	}
+}