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:
day 72: fixing the problem. thx @nkskalyan
@nkskalyan graciously pointed out my initial solution was incorrect. Thank you very much @nkskalyan!

Really resolves #153. ;) 

Patch:
diff --git a/day72/problem.go b/day72/problem.go
index dd64793..2c785c8 100644
--- a/day72/problem.go
+++ b/day72/problem.go
@@ -9,6 +9,9 @@ var errInfiniteLoop = errors.New("loop detected")
 // AdjacencyMatrix represents a sparse adjacency matrix.
 type AdjacencyMatrix map[int]map[int]struct{}
 
+// Node is a character representation of a node in a graph.
+type Node rune
+
 // Edge represents a directed edge going 'From' and 'To' a different node.
 // Nodes are represented by integers from 0..N.
 type Edge struct {
@@ -23,45 +26,55 @@ func ErrInfiniteLoop() error {
 // 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) {
+func LargestPathValue(nodes []Node, 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
-			}
+	visited := make(map[int]struct{}, len(nodes))
+	freq := make(map[Node]int)
+	var largest int
+	for start := range graph {
+		if count, err := dfsBacktracking(graph, nodes, start, visited, freq); err != nil {
+			return 0, err
+		} else if count > largest {
+			largest = count
 		}
 	}
 	return largest, nil
 }
 
+func dfsBacktracking(g AdjacencyMatrix, nodes []Node, n int, visited map[int]struct{}, freq map[Node]int) (int, error) {
+	visited[n] = struct{}{}
+	freq[nodes[n]]++
+	var max int
+	var err error
+	if len(g[n]) == 0 {
+		for _, count := range freq {
+			if count > max {
+				max = count
+			}
+		}
+	} else {
+		for next := range g[n] {
+			if _, seen := visited[next]; seen {
+				return 0, ErrInfiniteLoop()
+			} else if v, err := dfsBacktracking(g, nodes, next, visited, freq); err != nil {
+				return 0, err
+			} else if v > max {
+				max = v
+			}
+		}
+	}
+	freq[nodes[n]]--
+	delete(visited, n)
+	return max, err
+}
+
 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 {
+		if _, found := graph[edge.From]; !found {
 			graph[edge.From] = make(map[int]struct{})
-			graph[edge.From][edge.To] = struct{}{}
 		}
+		graph[edge.From][edge.To] = struct{}{}
 	}
 	return graph
 }


Test patch:
diff --git a/day72/problem_test.go b/day72/problem_test.go
index ac6b3cd..a8ec04f 100644
--- a/day72/problem_test.go
+++ b/day72/problem_test.go
@@ -2,29 +2,31 @@ 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)
-	}
+var testcases = []struct {
+	nodes       []Node
+	edges       []Edge
+	expected    int
+	expectedErr error
+}{
+	{[]Node("ABACA"), []Edge{{0, 1}, {0, 2}, {2, 3}, {3, 4}}, 3, nil},
+	{[]Node("ABAACB"), []Edge{{0, 1}, {0, 2}, {0, 3}, {1, 4}, {4, 5}}, 2, nil},
+	{[]Node("A"), []Edge{{0, 0}}, 0, ErrInfiniteLoop()},
+	{[]Node("AAAA"), []Edge{{0, 1}, {1, 2}, {2, 3}, {3, 0}}, 0, ErrInfiniteLoop()},
 }
 
-func TestLargestPathValueInfiniteLoop(t *testing.T) {
+func TestLargestPathValue(t *testing.T) {
 	t.Parallel()
-	nodes := []rune("A")
-	edges := []Edge{{0, 0}}
-	if _, err := LargestPathValue(nodes, edges); err != ErrInfiniteLoop() {
-		t.Errorf("Expected an error")
+	for _, tc := range testcases {
+		if result, err := LargestPathValue(tc.nodes, tc.edges); result != tc.expected || err != tc.expectedErr {
+			t.Errorf("Expected (%v,%v) but got (%v,%v)", tc.expected, tc.expectedErr, result, err)
+		}
 	}
 }
 
 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)
+		for _, tc := range testcases {
+			LargestPathValue(tc.nodes, tc.edges)
+		}
 	}
 }