Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 255
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

The transitive closure of a graph is a measure of which vertices are reachable from other vertices. It can be represented as a matrix M, where M[i][j] == 1 if there is a path between vertices i and j, and otherwise 0.

For example, suppose we are given the following graph in adjacency list form:
```
graph = [
    [0, 1, 3],
    [1, 2],
    [2],
    [3]
]
```
The transitive closure of this graph would be:
```
[1, 1, 1, 1]
[0, 1, 1, 0]
[0, 0, 1, 0]
[0, 0, 0, 1]
```
Given a graph, find its transitive closure.

Pull request:
Day255
Resolves #525.

Patch:
diff --git a/README.md b/README.md
index c0251d9..55077a5 100644
--- a/README.md
+++ b/README.md
@@ -265,3 +265,4 @@ problems from
 * [Day 252](https://github.com/vaskoz/dailycodingproblem-go/issues/519)
 * [Day 253](https://github.com/vaskoz/dailycodingproblem-go/issues/521)
 * [Day 254](https://github.com/vaskoz/dailycodingproblem-go/issues/523)
+* [Day 255](https://github.com/vaskoz/dailycodingproblem-go/issues/525)
diff --git a/day255/problem.go b/day255/problem.go
new file mode 100644
index 0000000..0a153f7
--- /dev/null
+++ b/day255/problem.go
@@ -0,0 +1,49 @@
+package day255
+
+// Graph is an integer based ajacency matrix.
+type Graph map[int][]int
+
+// TransitiveClosure returns the transitive closure
+// matrix.
+func TransitiveClosure(g Graph) [][]int {
+	var largest int
+	for start, ends := range g {
+		if start > largest {
+			largest = start
+		}
+		for _, node := range ends {
+			if node > largest {
+				largest = node
+			}
+		}
+	}
+	result := make([][]int, largest+1)
+	for i := range result {
+		result[i] = make([]int, largest+1)
+	}
+	visited := make(map[int]struct{}, largest+1)
+	result = transitiveClosure(-1, g, result, visited)
+	return result
+}
+
+func transitiveClosure(node int, g Graph, result [][]int, visited map[int]struct{}) [][]int {
+	if node == -1 {
+		for start := range g {
+			result = transitiveClosure(start, g, result, visited)
+		}
+	} else {
+		for start := range visited {
+			result[start][node] = 1
+		}
+		visited[node] = struct{}{}
+		for _, n := range g[node] {
+			if n == node {
+				result[node][n] = 1
+			} else if _, found := visited[n]; !found {
+				result = transitiveClosure(n, g, result, visited)
+			}
+		}
+		delete(visited, node)
+	}
+	return result
+}


Test patch:
diff --git a/day255/problem_test.go b/day255/problem_test.go
new file mode 100644
index 0000000..f2fecc6
--- /dev/null
+++ b/day255/problem_test.go
@@ -0,0 +1,72 @@
+package day255
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	g        Graph
+	expected [][]int
+}{
+	{
+		Graph{
+			0: {0, 1, 3},
+			1: {1, 2},
+			2: {2},
+			3: {3},
+		},
+		[][]int{
+			{1, 1, 1, 1},
+			{0, 1, 1, 0},
+			{0, 0, 1, 0},
+			{0, 0, 0, 1},
+		},
+	},
+	{
+		Graph{
+			0: {1, 3},
+			1: {2},
+			2: {},
+			3: {},
+		},
+		[][]int{
+			{0, 1, 1, 1},
+			{0, 0, 1, 0},
+			{0, 0, 0, 0},
+			{0, 0, 0, 0},
+		},
+	},
+	{
+		Graph{
+			0: {1, 3},
+			1: {2},
+			2: {3},
+			3: {2},
+		},
+		[][]int{
+			{0, 1, 1, 1},
+			{0, 0, 1, 1},
+			{0, 0, 0, 1},
+			{0, 0, 1, 0},
+		},
+	},
+}
+
+func TestTransitiveClosure(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := TransitiveClosure(tc.g); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkTransitiveClosure(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			TransitiveClosure(tc.g)
+		}
+	}
+}