Evaluate Division
You are given some facts of the form "variable A divided by variable B equals a number". Variables are strings, and equations[i] = [A, B] together with values[i] = k means A / B = k. Every k is a positive number.
Then you are given a list of queries. For each query [C, D], compute C / D using only the given facts, which you may combine freely (for example from a / b = 2 and b / c = 3 you can conclude a / c = 6, and also b / a = 1/2).
Return one number per query. If an answer cannot be determined (a variable never appears in the equations, or the two variables are not linked), the answer is -1. A known variable divided by itself is 1; an unknown variable divided by itself is -1.
Answers are compared with a small tolerance (about 1e-5), so floating-point results are fine. In Python, / already gives a float.
Constraints
1 <= equations.length <= 20,values.length === equations.length,1 <= queries.length <= 20- Variable names are non-empty lowercase or alphanumeric strings.
0 < values[i] <= 20, and the facts do not contradict each other.
Examples
Example 1
Input: equations = [["a","b"],["b","c"]], values = [2,3], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] Output: [6,0.5,-1,1,-1]
a / c = (a / b) * (b / c) = 6. b / a = 1/2. e is unknown, so a / e is -1. a / a is 1 because a is known. x is unknown, so even x / x is -1.
Example 2
Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] Output: [3.75,0.4,5,0.2]
a, b, c form one group and bc, cd another; a query across groups would be -1. Here a / c = 3.75, c / b = 0.4, and the second group gives 5 and 0.2.
Example 3
Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] Output: [0.5,2,-1,-1]
Only one equation: a / b = 0.5, so b / a = 2.
JavaScript you'll use: Map and Set Graphs and grids in JavaScript
/**
* @param {string[][]} equations
* @param {number[]} values
* @param {string[][]} queries
* @return {number[]}
*/
function calcEquation(equations, values, queries) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.