Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 352
Good morning! Here's your coding interview problem for today.

This problem was asked by Palantir.

A typical American-style crossword puzzle grid is an `N x N` matrix with black and white squares, which obeys the following rules:

* Every white square must be part of an "across" word and a "down" word.
* No word can be fewer than three letters long.
* Every white square must be reachable from every other white square.
* The grid is rotationally symmetric (for example, the colors of the top left and bottom right squares must match).

Write a program to determine whether a given matrix qualifies as a crossword grid.

Pull request:
Day352
Resolves #699.

Patch:
diff --git a/README.md b/README.md
index a473b19..df0a55c 100644
--- a/README.md
+++ b/README.md
@@ -338,3 +338,4 @@ problems from
 * [Day 346](https://github.com/vaskoz/dailycodingproblem-go/issues/688)
 * [Day 347](https://github.com/vaskoz/dailycodingproblem-go/issues/689)
 * [Day 350](https://github.com/vaskoz/dailycodingproblem-go/issues/695)
+* [Day 352](https://github.com/vaskoz/dailycodingproblem-go/issues/699)
diff --git a/day352/problem.go b/day352/problem.go
new file mode 100644
index 0000000..1cc34b9
--- /dev/null
+++ b/day352/problem.go
@@ -0,0 +1,146 @@
+package day352
+
+import "reflect"
+
+// Square represents either a white or black square
+// on a crossword puzzle.
+type Square int
+
+const (
+	// W is a white square
+	W Square = iota
+	// B is a white square
+	B
+)
+
+func IsValidCrossword(puzzle [][]Square) bool {
+	if isValid := checkHorizontal(puzzle); !isValid {
+		return false
+	}
+	if isValid := checkVertical(puzzle); !isValid {
+		return false
+	}
+	if isValid := checkReachable(puzzle); !isValid {
+		return false
+	}
+	if isValid := checkRotationallySymmetric(puzzle); !isValid {
+		return false
+	}
+	return true
+}
+
+func checkRotationallySymmetric(puzzle [][]Square) bool {
+	for r := range puzzle {
+		rBottom := len(puzzle) - r - 1
+		cRight := len(puzzle[r]) - r - 1
+		cMost := len(puzzle[r]) - 1
+		for i := 0; i < cRight; i++ {
+			if puzzle[r][i] != puzzle[rBottom][cMost-i] {
+				return false
+			}
+		}
+	}
+	return true
+}
+
+func checkReachable(puzzle [][]Square) bool {
+	var startR, startC int
+	whiteSquares := make(map[int]map[int]struct{})
+	visited := make(map[int]map[int]struct{})
+	for r := range puzzle {
+		if whiteSquares[r] == nil {
+			whiteSquares[r] = make(map[int]struct{})
+			visited[r] = make(map[int]struct{})
+		}
+		for c := range puzzle[r] {
+			if puzzle[r][c] == W {
+				whiteSquares[r][c] = struct{}{}
+				startR, startC = r, c
+			}
+		}
+	}
+	dfs(whiteSquares, visited, startR, startC)
+	return reflect.DeepEqual(whiteSquares, visited)
+}
+
+func dfs(whiteSquares, visited map[int]map[int]struct{}, r, c int) {
+	visited[r][c] = struct{}{}
+	// up
+	if _, exists := whiteSquares[r-1]; exists {
+		if _, next := whiteSquares[r-1][c]; next {
+			if _, seen := visited[r-1][c]; !seen {
+				dfs(whiteSquares, visited, r-1, c)
+			}
+		}
+	}
+	// down
+	if _, exists := whiteSquares[r+1]; exists {
+		if _, next := whiteSquares[r+1][c]; next {
+			if _, seen := visited[r+1][c]; !seen {
+				dfs(whiteSquares, visited, r+1, c)
+			}
+		}
+	}
+	// left
+	if _, exists := whiteSquares[r]; exists {
+		if _, next := whiteSquares[r][c-1]; next {
+			if _, seen := visited[r][c-1]; !seen {
+				dfs(whiteSquares, visited, r, c-1)
+			}
+		}
+	}
+	// right
+	if _, exists := whiteSquares[r]; exists {
+		if _, next := whiteSquares[r][c+1]; next {
+			if _, seen := visited[r][c+1]; !seen {
+				dfs(whiteSquares, visited, r, c+1)
+			}
+		}
+	}
+}
+
+func checkHorizontal(puzzle [][]Square) bool {
+	var r, c int
+	for r < len(puzzle) {
+		if puzzle[r][c] == B {
+			c++
+		} else if puzzle[r][c] == W {
+			count := 0
+			for c < len(puzzle[r]) && puzzle[r][c] == W {
+				count++
+				c++
+			}
+			if count < 3 {
+				return false
+			}
+		}
+		if c == len(puzzle[r]) {
+			c = 0
+			r++
+		}
+	}
+	return true
+}
+
+func checkVertical(puzzle [][]Square) bool {
+	var r, c int
+	for c < len(puzzle[r]) {
+		if puzzle[r][c] == B {
+			r++
+		} else if puzzle[r][c] == W {
+			count := 0
+			for r < len(puzzle) && puzzle[r][c] == W {
+				count++
+				r++
+			}
+			if count < 3 {
+				return false
+			}
+		}
+		if r == len(puzzle) {
+			r = 0
+			c++
+		}
+	}
+	return true
+}


Test patch:
diff --git a/day352/problem_test.go b/day352/problem_test.go
new file mode 100644
index 0000000..13ab2ca
--- /dev/null
+++ b/day352/problem_test.go
@@ -0,0 +1,127 @@
+package day352
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	puzzle  [][]Square
+	isValid bool
+}{
+	{
+		[][]Square{
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, B, W, W, W, B, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, B, W, W, W, W, W, B, B, B},
+			{B, B, W, W, W, B, W, W, W, B, W, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, B, W, W, W, W, W, W, W, B, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, W, B, W, W, W, B, W, W, W, B, B},
+			{B, B, B, W, W, W, W, W, B, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, B, W, W, W, B, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+		},
+		true,
+	},
+	{
+		[][]Square{
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, B, W, W, W, B, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, B, W, W, W, W, W, B, B, B},
+			{B, B, W, W, W, B, W, W, W, B, W, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, B, W, W, W, W, W, W, W, B, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, W, B, W, W, W, B, W, W, W, B, B},
+			{B, B, B, W, W, W, W, W, B, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, B, W, W, W, B, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, B, W, B, W, W, W, W, W, B, W, W, W, W},
+		},
+		false,
+	},
+	{
+		[][]Square{
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, B, W, W, W, B, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, B, W, W, W, W, W, B, B, B},
+			{B, B, W, W, W, B, W, W, W, B, W, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, B, W, W, W, W, W, W, W, B, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, W, B, W, W, W, B, W, W, W, B, B},
+			{B, B, B, W, W, W, W, W, B, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, B, W, W, W, B, W, W, W},
+			{W, W, W, W, W, W, W, W, W, B, W, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+		},
+		false,
+	},
+	{
+		[][]Square{
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{B, B, B, B, B, B, B, B, B, B, B, B, B, B, B},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+		},
+		false,
+	},
+	{
+		[][]Square{
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, B, W, W, W, B, W, W, W, W, W, W, W},
+			{W, W, W, W, W, W, B, W, W, W, W, W, B, B, B},
+			{B, B, W, W, W, B, W, W, W, B, W, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, B, W, W, W, W, W, W, W, B, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, W, B, W, W, W, B, W, W, W, B, B},
+			{B, B, B, W, W, W, W, W, B, W, W, W, W, W, W},
+			{W, W, W, W, W, W, W, B, W, W, W, B, W, W, W},
+			{W, W, W, W, W, W, W, W, W, W, W, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, W, B, W, W, W, W},
+			{W, W, W, W, B, W, W, W, W, B, B, W, W, W, W},
+		},
+		false,
+	},
+}
+
+func TestIsValidCrossword(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if valid := IsValidCrossword(tc.puzzle); valid != tc.isValid {
+			t.Errorf("TCID %d. Expected %v, got %v", tcid, tc.isValid, valid)
+		}
+	}
+}
+
+func BenchmarkIsValidCrossword(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			IsValidCrossword(tc.puzzle)
+		}
+	}
+}