Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 56
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given an undirected graph represented as an adjacency matrix and an integer k, write a function to determine whether each vertex in the graph can be colored such that no two adjacent vertices share the same color using at most k colors.

Pull request description:
Day56
Resolves #123.

Patch:
diff --git a/README.md b/README.md
index cb383ed..d605c51 100644
--- a/README.md
+++ b/README.md
@@ -67,3 +67,4 @@ problems from
 * [Day 53](https://github.com/vaskoz/dailycodingproblem-go/issues/114)
 * [Day 54](https://github.com/vaskoz/dailycodingproblem-go/issues/118)
 * [Day 55](https://github.com/vaskoz/dailycodingproblem-go/issues/121)
+* [Day 56](https://github.com/vaskoz/dailycodingproblem-go/issues/123)
diff --git a/day56/problem.go b/day56/problem.go
new file mode 100644
index 0000000..8fb1e22
--- /dev/null
+++ b/day56/problem.go
@@ -0,0 +1,31 @@
+package day56
+
+// Graph represents an adjacency list.
+type Graph map[int]map[int]struct{}
+
+// CanColor returns true if the graph can be colored with at
+// most k colors.
+func CanColor(v int, g Graph, color []int, k int) bool {
+	if v == len(g) {
+		return true
+	}
+	for c := 1; c <= k; c++ {
+		if isSafe(v, g, color, c) {
+			color[v] = c
+			if CanColor(v+1, g, color, k) {
+				return true
+			}
+			color[v] = 0
+		}
+	}
+	return false
+}
+
+func isSafe(v int, g Graph, color []int, c int) bool {
+	for i := 0; i < len(g); i++ {
+		if _, found := g[v][i]; found && c == color[i] {
+			return false
+		}
+	}
+	return true
+}


Test patch:
diff --git a/day56/problem_test.go b/day56/problem_test.go
new file mode 100644
index 0000000..97a903f
--- /dev/null
+++ b/day56/problem_test.go
@@ -0,0 +1,67 @@
+package day56
+
+import "testing"
+
+var testcases = []struct {
+	g        Graph
+	k        int
+	canColor bool
+}{
+	{map[int]map[int]struct{}{
+		0: map[int]struct{}{
+			1: struct{}{},
+			2: struct{}{},
+			3: struct{}{},
+		},
+		1: map[int]struct{}{
+			0: struct{}{},
+			2: struct{}{},
+		},
+		2: map[int]struct{}{
+			0: struct{}{},
+			1: struct{}{},
+			3: struct{}{},
+		},
+		3: map[int]struct{}{
+			1: struct{}{},
+			2: struct{}{},
+		},
+	}, 3, true},
+	{map[int]map[int]struct{}{
+		0: map[int]struct{}{
+			1: struct{}{},
+			2: struct{}{},
+			3: struct{}{},
+		},
+		1: map[int]struct{}{
+			0: struct{}{},
+			2: struct{}{},
+		},
+		2: map[int]struct{}{
+			0: struct{}{},
+			1: struct{}{},
+			3: struct{}{},
+		},
+		3: map[int]struct{}{
+			1: struct{}{},
+			2: struct{}{},
+		},
+	}, 2, false},
+}
+
+func TestCanColor(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if canColor := CanColor(0, tc.g, make([]int, len(tc.g)), tc.k); canColor != tc.canColor {
+			t.Errorf("Expected %v got %v", tc.canColor, canColor)
+		}
+	}
+}
+
+func BenchmarkCanColor(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CanColor(0, tc.g, make([]int, len(tc.g)), tc.k)
+		}
+	}
+}