Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 302
Good morning! Here's your coding interview problem for today.

This problem was asked by Uber.

You are given a 2-d matrix where each cell consists of either `/`, `\`, or an empty space. Write an algorithm that determines into how many regions the slashes divide the space.

For example, suppose the input for a three-by-six grid is the following:
```
\    /
 \  /
  \/
```
Considering the edges of the matrix as boundaries, this divides the grid into three triangles, so you should return `3`.

Pull request description:
Day302
Resolves #615.

Patch:
diff --git a/README.md b/README.md
index ddbc35c..49da401 100644
--- a/README.md
+++ b/README.md
@@ -308,3 +308,4 @@ problems from
 * [Day 298](https://github.com/vaskoz/dailycodingproblem-go/issues/609)
 * [Day 299](https://github.com/vaskoz/dailycodingproblem-go/issues/611)
 * [Day 300](https://github.com/vaskoz/dailycodingproblem-go/issues/612)
+* [Day 302](https://github.com/vaskoz/dailycodingproblem-go/issues/615)
diff --git a/day302/problem.go b/day302/problem.go
new file mode 100644
index 0000000..e23e49e
--- /dev/null
+++ b/day302/problem.go
@@ -0,0 +1,37 @@
+package day302
+
+// DistinctRegions returns the number of separate regions divided
+// by the lines.
+// Uses Depth First Search to visit everything.
+func DistinctRegions(grid []string) int {
+	visited := make([][]bool, len(grid))
+	for i := range visited {
+		visited[i] = make([]bool, len(grid[i]))
+		for j := range visited[i] {
+			if grid[i][j] != ' ' {
+				visited[i][j] = true
+			}
+		}
+	}
+	var regions int
+	for i := range visited {
+		for j := range visited[i] {
+			if !visited[i][j] {
+				markRegion(visited, i, j)
+				regions++
+			}
+		}
+	}
+	return regions
+}
+
+func markRegion(visited [][]bool, r, c int) {
+	if r < 0 || r >= len(visited) || c < 0 || c >= len(visited[r]) || visited[r][c] {
+		return
+	}
+	visited[r][c] = true
+	markRegion(visited, r-1, c) // up
+	markRegion(visited, r+1, c) // down
+	markRegion(visited, r, c-1) // left
+	markRegion(visited, r, c+1) // right
+}


Test patch:
diff --git a/day302/problem_test.go b/day302/problem_test.go
new file mode 100644
index 0000000..ea90629
--- /dev/null
+++ b/day302/problem_test.go
@@ -0,0 +1,35 @@
+package day302
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	grid    []string
+	regions int
+}{
+	{
+		[]string{
+			`\    /`,
+			` \  / `,
+			`  \/  `,
+		},
+		3,
+	},
+}
+
+func TestDistinctRegions(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if regions := DistinctRegions(tc.grid); regions != tc.regions {
+			t.Errorf("Expected %v, got %v", tc.regions, regions)
+		}
+	}
+}
+
+func BenchmarkDistinctRegions(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			DistinctRegions(tc.grid)
+		}
+	}
+}