Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 72
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

In a directed graph, each node is assigned an uppercase letter. We define a path's value as the number of most frequently-occurring letter along that path. For example, if a path in the graph goes through "ABACA", the value of the path is 3, since there are 3 occurrences of 'A' on the path.

Given a graph with n nodes and m directed edges, return the largest value path of the graph. If the largest value is infinite, then return null.

The graph is represented with a string and an edge list. The i-th character represents the uppercase letter of the i-th node. Each tuple in the edge list `(i, j)` means there is a directed edge from the i-th node to the j-th node. Self-edges are possible, as well as multi-edges.

For example, the following input graph:
```
ABACA
[(0, 1),
 (0, 2),
 (2, 3),
 (3, 4)]
```
Would have maximum value 3 using the path of vertices `[0, 2, 3, 4], (A, A, C, A)`.

The following input graph:
```
A
[(0, 0)]
```
Should return null, since we have an infinite loop.

Pull request:
Day72
Resolves #153.

Patch:
diff --git a/README.md b/README.md
index 2d5c92b..19ca210 100644
--- a/README.md
+++ b/README.md
@@ -81,3 +81,4 @@ problems from
 * [Day 69](https://github.com/vaskoz/dailycodingproblem-go/issues/147)
 * [Day 70](https://github.com/vaskoz/dailycodingproblem-go/issues/149)
 * [Day 71](https://github.com/vaskoz/dailycodingproblem-go/issues/151)
+* [Day 72](https://github.com/vaskoz/dailycodingproblem-go/issues/153)
diff --git a/day72/problem.go b/day72/problem.go
new file mode 100644
index 0000000..dd64793
--- /dev/null
+++ b/day72/problem.go
@@ -0,0 +1,67 @@
+package day72
+
+import (
+	"errors"
+)
+
+var errInfiniteLoop = errors.New("loop detected")
+
+// AdjacencyMatrix represents a sparse adjacency matrix.
+type AdjacencyMatrix map[int]map[int]struct{}
+
+// Edge represents a directed edge going 'From' and 'To' a different node.
+// Nodes are represented by integers from 0..N.
+type Edge struct {
+	From, To int
+}
+
+// ErrInfiniteLoop returns the error if an infinite loop is detected.
+func ErrInfiniteLoop() error {
+	return errInfiniteLoop
+}
+
+// LargestPathValue takes a slice of runes representing nodes.
+// Edges represents all the directed edges.
+// Returns the largest path value or an error if an infinite loop is detected.
+func LargestPathValue(nodes []rune, edges []Edge) (int, error) {
+	graph := buildAdjacencyMatrix(edges)
+	largest := 0
+	for from := range graph {
+		visited := make([]bool, len(nodes))
+		counts := make(map[rune]int)
+		stack := make([]int, 0, len(nodes))
+		stack = append(stack, from)
+		for len(stack) != 0 {
+			var v int
+			v, stack = stack[len(stack)-1], stack[:len(stack)-1]
+			if !visited[v] {
+				visited[v] = true
+				counts[nodes[v]]++
+				for k := range graph[v] {
+					stack = append(stack, k)
+				}
+				for _, count := range counts {
+					if count > largest {
+						largest = count
+					}
+				}
+			} else {
+				return 0, ErrInfiniteLoop() // cycle found
+			}
+		}
+	}
+	return largest, nil
+}
+
+func buildAdjacencyMatrix(edges []Edge) AdjacencyMatrix {
+	graph := make(AdjacencyMatrix)
+	for _, edge := range edges {
+		if _, found := graph[edge.From]; found {
+			graph[edge.From][edge.To] = struct{}{}
+		} else {
+			graph[edge.From] = make(map[int]struct{})
+			graph[edge.From][edge.To] = struct{}{}
+		}
+	}
+	return graph
+}


Test patch:
diff --git a/day72/problem_test.go b/day72/problem_test.go
new file mode 100644
index 0000000..ac6b3cd
--- /dev/null
+++ b/day72/problem_test.go
@@ -0,0 +1,30 @@
+package day72
+
+import "testing"
+
+func TestLargestPathValue(t *testing.T) {
+	t.Parallel()
+	nodes := []rune("ABACA")
+	edges := []Edge{{0, 1}, {0, 2}, {2, 3}, {3, 4}}
+	expected := 3
+	if result, _ := LargestPathValue(nodes, edges); result != expected {
+		t.Errorf("Expected %v but got %v", expected, result)
+	}
+}
+
+func TestLargestPathValueInfiniteLoop(t *testing.T) {
+	t.Parallel()
+	nodes := []rune("A")
+	edges := []Edge{{0, 0}}
+	if _, err := LargestPathValue(nodes, edges); err != ErrInfiniteLoop() {
+		t.Errorf("Expected an error")
+	}
+}
+
+func BenchmarkLargestPathValue(b *testing.B) {
+	nodes := []rune("ABACA")
+	edges := []Edge{{0, 1}, {0, 2}, {2, 3}, {3, 4}}
+	for i := 0; i < b.N; i++ {
+		LargestPathValue(nodes, edges)
+	}
+}