Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 23
This problem was asked by Google.

You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on.

Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board.

For example, given the following board:
```
[[f, f, f, f],
[t, t, f, t],
[f, f, f, f],
[f, f, f, f]]
```
and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum number of steps required to reach the end is 7, since we would need to go through (1, 2) because there is a wall everywhere else on the second row.

Pull request:
Day23
Resolves #55 

Patch:
diff --git a/README.md b/README.md
index a18d8d4..e73a706 100644
--- a/README.md
+++ b/README.md
@@ -36,3 +36,4 @@ problems from
 * [Day 20](https://github.com/vaskoz/dailycodingproblem-go/issues/49)
 * [Day 21](https://github.com/vaskoz/dailycodingproblem-go/issues/51)
 * [Day 22](https://github.com/vaskoz/dailycodingproblem-go/issues/53)
+* [Day 23](https://github.com/vaskoz/dailycodingproblem-go/issues/55)
diff --git a/day23/problem.go b/day23/problem.go
new file mode 100644
index 0000000..784ce42
--- /dev/null
+++ b/day23/problem.go
@@ -0,0 +1,49 @@
+package day23
+
+import (
+	"errors"
+	"sort"
+)
+
+// Board with false representing open space and true representing a wall.
+type Board [][]bool
+
+// Cell represents a row & col position on the board.
+type Cell struct {
+	row, col int
+}
+
+var errNoPath = errors.New("No path possible")
+
+// MinimumSteps performs depth-first-search to find a path.
+func MinimumSteps(board Board, start, end Cell, visited map[Cell]struct{}) (int, error) {
+	visited[start] = struct{}{}
+	if start == end {
+		delete(visited, start)
+		return 0, nil
+	}
+	var results []int
+	cells := []Cell{{start.row + 1, start.col}, {start.row - 1, start.col}, {start.row, start.col - 1}, {start.row, start.col + 1}}
+	for _, cell := range cells {
+		if _, found := visited[cell]; !found && isValidNextCell(board, cell) {
+			dist, err := MinimumSteps(board, cell, end, visited)
+			if err == nil {
+				results = append(results, dist)
+			}
+		}
+	}
+	sort.Ints(results)
+	delete(visited, start)
+	if len(results) == 0 {
+		return 0, errNoPath
+	}
+	return 1 + results[0], nil
+}
+
+// isValidNextCell checks if the cell is a valid cell to move to.
+// Valid means inbounds and also not a wall (true)
+func isValidNextCell(board Board, cell Cell) bool {
+	return cell.row >= 0 && cell.row < len(board) &&
+		cell.col >= 0 && cell.col < len(board[cell.row]) &&
+		!board[cell.row][cell.col]
+}


Test patch:
diff --git a/day23/problem_test.go b/day23/problem_test.go
new file mode 100644
index 0000000..a4f9af7
--- /dev/null
+++ b/day23/problem_test.go
@@ -0,0 +1,42 @@
+package day23
+
+import "testing"
+
+var testcases = []struct {
+	board      Board
+	start, end Cell
+	expected   int
+	err        error
+}{
+	{Board{
+		{false, false, false, false},
+		{true, true, false, true},
+		{false, false, false, true},
+		{false, false, false, false},
+	}, Cell{3, 0}, Cell{0, 0}, 7, nil},
+	{Board{
+		{false, true, false, false},
+		{true, true, false, true},
+		{false, false, false, true},
+		{false, false, false, false},
+	}, Cell{3, 0}, Cell{0, 0}, 0, errNoPath},
+}
+
+func TestMinimumSteps(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := MinimumSteps(tc.board, tc.start, tc.end,
+			make(map[Cell]struct{})); result != tc.expected || err != tc.err {
+			t.Errorf("Expected (%v, %v) but got (%v, %v)",
+				tc.expected, tc.err, result, err)
+		}
+	}
+}
+
+func BenchmarkMinimumSteps(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinimumSteps(tc.board, tc.start, tc.end, make(map[Cell]struct{}))
+		}
+	}
+}