# 399 Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is: vector> equations, vector& values, vector> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.
The Idea: In summary, have a/b = k as a link between node a and b, the weight from a to b as k, the reverse link is 1/k. A query follows to the path between two nodes, and the result is the product of the edges within this path. As to why this is, is explained in the graphic below. For my graph, I used a dictionary of sets to represent the relationship between nodes, and an edges map for the look up of the value between two nodes. For finding the path, I used BFS (although DFS would work as well). BFS is able to find the shortest path, which will give it a computational advantage with larger graphs. When the target node is identified, we can backtrack by continously hashing in our prev_array until the start node is reached. Complexity: O((v+1)*q) time where v is the number of values and q is the number queries and O(n) space.
import collections
import queue
class Solution:
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
hash_list = collections.defaultdict(set)
edges_map = {}
for equation, value in zip(equations, values):
a = equation
b = equation
edges_map[a + '-' + b] = value
edges_map[b + '-' + a] = 1 / value
def BFS(start, end):
q = queue.Queue()
q.put(start)
visited = set()
prev = {}
while not q.empty():
front = q.get()
if front == end:
break
# backtrack
if end not in prev:
return float(-1)
cur_prev = prev[end]
cur_mult = edges_map[cur_prev + '-' + end]
while cur_prev != start:
temp = cur_prev
cur_prev = prev[temp]
cur_mult *= edges_map[cur_prev + '-' + temp]
return cur_mult
solutions = []
for a, b in queries:
if a in hash_list and b in hash_list:
if a == b:
solutions.append(float(1))
else:
sol = BFS(a, b)
solutions.append(sol)
# potentially shorter path for future queries
edges_map[a + '-' + b] = sol
edges_map[b + '-' + a] = 1 / sol
else:
solutions.append(float(-1))
return solutions
obj = Solution()
equations = [["a","b"],["b","c"],["bc","cd"]]
values = [1.5,2.5,5.0]
queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
print(obj.calcEquation(equations, values, queries))
obj2 = Solution()
equations2 = [ ["a", "b"], ["b", "c"] ]
values2 = [2.0, 3.0]
queries2 = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]
print(obj2.calcEquation(equations2, values2, queries2))
obj3 = Solution()
equations3 = [["a","b"],["c","d"]]
values3 = [1.0,1.0]
queries3 = [["a","c"],["b","d"],["b","a"],["d","c"]]
print(obj3.calcEquation(equations3, values3, queries3))