Evaluate Variable Quotients
Problem
You're given known ratios like a / b = 2.0. Build a directed weighted graph where each ratio adds an edge in both directions (with reciprocal weight). For each query x / y, DFS from x to y multiplying edge weights; if no path exists, return -1.
Input
known = [["a","b",2.0],["b","c",3.0]], query = "a / c"Output
6.0a→b weight 2, b→c weight 3 → a/c = 2 × 3 = 6.
def evaluate(eqs, q):
from collections import defaultdict
adj = defaultdict(list)
for a, b, k in eqs:
adj[a].append((b, k)); adj[b].append((a, 1 / k))
x, y = q
if x not in adj or y not in adj: return -1
if x == y: return 1
seen = {x}
def dfs(u, acc):
if u == y: return acc
for v, w in adj[u]:
if v in seen: continue
seen.add(v)
r = dfs(v, acc * w)
if r != -1: return r
return -1
return dfs(x, 1)function evaluate(eqs, q) {
const adj = new Map();
for (const [a, b, k] of eqs) {
if (!adj.has(a)) adj.set(a, []); if (!adj.has(b)) adj.set(b, []);
adj.get(a).push([b, k]); adj.get(b).push([a, 1 / k]);
}
const [x, y] = q;
if (!adj.has(x) || !adj.has(y)) return -1;
if (x === y) return 1;
const seen = new Set([x]);
function dfs(u, acc) {
if (u === y) return acc;
for (const [v, w] of adj.get(u)) if (!seen.has(v)) {
seen.add(v);
const r = dfs(v, acc * w);
if (r !== -1) return r;
}
return -1;
}
return dfs(x, 1);
}class Solution {
Map<String, List<Object[]>> adj;
Set<String> seen;
String Y;
public double evaluate(String[][] eqs, double[] vals, String x, String y) {
adj = new HashMap<>();
for (int i = 0; i < eqs.length; i++) {
String a = eqs[i][0], b = eqs[i][1]; double k = vals[i];
adj.computeIfAbsent(a, z -> new ArrayList<>()).add(new Object[]{ b, k });
adj.computeIfAbsent(b, z -> new ArrayList<>()).add(new Object[]{ a, 1.0 / k });
}
if (!adj.containsKey(x) || !adj.containsKey(y)) return -1;
if (x.equals(y)) return 1;
seen = new HashSet<>(); seen.add(x);
this.Y = y;
return dfs(x, 1.0);
}
private double dfs(String u, double acc) {
if (u.equals(Y)) return acc;
for (Object[] e : adj.get(u)) {
String v = (String) e[0]; double w = (double) e[1];
if (seen.contains(v)) continue;
seen.add(v);
double r = dfs(v, acc * w);
if (r != -1) return r;
}
return -1;
}
}unordered_map<string, vector<pair<string, double>>> adj_;
unordered_set<string> seen_;
string Y_;
double dfs(string u, double acc) {
if (u == Y_) return acc;
for (auto& [v, w] : adj_[u]) {
if (seen_.count(v)) continue;
seen_.insert(v);
double r = dfs(v, acc * w);
if (r != -1) return r;
}
return -1;
}
double evaluate(vector<vector<string>>& eqs, vector<double>& vals, string x, string y) {
adj_.clear();
for (int i = 0; i < (int)eqs.size(); i++) {
adj_[eqs[i][0]].push_back({eqs[i][1], vals[i]});
adj_[eqs[i][1]].push_back({eqs[i][0], 1.0 / vals[i]});
}
if (!adj_.count(x) || !adj_.count(y)) return -1;
if (x == y) return 1;
seen_.clear(); seen_.insert(x);
Y_ = y;
return dfs(x, 1.0);
}