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.

Why this is worth learning

This is path-product reachability, not a weighted shortest-path problem. Store a/b on edge a->b and its reciprocal on b->a; multiplying ratios along a path cancels intermediate variables.

Before coding: one-minute experiment

Given a/b=2 and b/c=3, what should queries a/c, c/a, a/a, and unknown/unknown return?

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; each equation/query has two names, and len(values) == len(equations).
• Equations are mutually consistent and have finite, nonzero values. Reciprocals and intermediate path products must remain finite and nonzero in float64; allow normal floating-point rounding.

Core idea (near-solution)

An equation a/b=v gives a directed relationship and its reciprocal, so store a→b with factor v and b→a with factor 1/v. Chaining relationships multiplies factors: (a/b)(b/c)=a/c. A query can therefore search for any connecting path while carrying that product. It does not seek a minimum-weight path; mutual consistency makes alternative path products agree up to rounding. Check whether both variables are known before accepting the zero-edge identity query, since unknown/unknown is outside the known equation graph.

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

Every queued state (v,p) has p equal to the product along a discovered source-to-v path. It is true initially with product 1 at the source and remains true after multiplying by an outgoing edge. Under consistent nonzero finite equations, all paths between the same pair describe the same ratio, so one visit per variable suffices; there is no optimization over competing weights. Reaching the destination yields the required ratio. Exhausting the reachable component proves no relation can be inferred. Membership is checked before the self-query shortcut: an unknown x does not make x/x a known equation.

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.

Debugging lens

Check reciprocal orientation and reset visited state per query. A globally reused visited set can make a later valid query fail. Floating results need tolerance, not string equality.

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.

Contract precision

The finite, nonzero and consistency conditions are preconditions, not cases to repair. Unknown/disconnected queries return -1.0; a known self-query returns 1.0. Contradictory equations, division by zero, NaN and infinity are outside the contract. Equations, values, and queries remain unchanged.

Reconstruction checkpoint

Given p/q=0.5 and q/r=4, derive p/r and r/p. Then suppose a third equation p/r=3 is added: which stated assumption fails, and why can a path search no longer promise a unique answer?

Return to Graph General · Module quiz