Evaluate Division

You are given equations like a / b = value and queries like x / y. Return the result for each query, or -1.0 if it cannot be determined.

Function signature

func CalcEquation(equations [][]string, values []float64, queries [][]string) []float64

Inputs / outputs

• equations[i] = [Ai, Bi] with Ai / Bi = values[i].
• queries[j] = [Xj, Yj].
• Return: slice of results in query order.

Example

Equations: a/b=2.0, b/c=3.0
Query: a/c
Output: 6.0

Constraints

• 1 <= number of equations <= 100_000
• variable names are non-empty strings

Core idea (near-solution)

Model variables as nodes in a weighted graph. Each equation adds two directed edges: a->b with weight v and b->a with weight 1/v. For each query, run BFS/DFS to find a path and multiply edge weights along the path.

Invariant: when you traverse an edge u->v with weight w, the accumulated value from start to v is value[start->u] * w.

Algorithm (step-by-step)

1. Build adjacency list with weights from equations.
2. For each query:
   • If either variable is missing, return -1.0.
   • If x == y, return 1.0.
   • BFS/DFS from x to find y, multiplying weights along the path.
3. If not found, return -1.0.

Correctness sketch

• Invariant: when you traverse an edge u->v with weight w, the accumulated value from start to v is value[start->u] * w.
• DFS visits exactly all nodes reachable from a start node.
• Marking visited prevents revisits and guarantees termination.
• Repeating from unvisited nodes correctly handles all components.

Trace (hand walkthrough)

Example input:
Equations: a/b=2.0, b/c=3.0
Query: a/c
Output: 6.0

Walk:
- graph: a->b (2.0), b->c (3.0)
- DFS a->b->c accumulates 2.0*3.0=6.0
- return 6.0

Pitfalls to avoid

• Reusing a visited set across different queries.
• Returning 0 for unknown variables instead of -1.

Complexity

• Building graph: O(E).
• Each query: O(V + E) in worst case.

Implementation notes (Go)

• Build bidirectional edges with reciprocal weights.
• Use a fresh visited map per query to avoid cross-query contamination.