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[0]
            b = equation[1]

            hash_list[a].add(b)  # main
            edges_map[a + '-' + b] = value

            hash_list[b].add(a)  # reciprocal
            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()
                visited.add(front)
                if front == end:
                    break

                for adj in hash_list[front]:
                    if adj not in visited:
                        prev[adj] = front
                        q.put(adj)

            # 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
                    hash_list[a].add(b)
                    edges_map[a + '-' + b] = sol
                    hash_list[b].add(a)
                    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))