title: Breadth-first Search: how to get currency exchange?
body: <p>I am doing some LeetCode like questions to practice and encountered this question:</p>
  <pre><code>Given a list of currency pairs and the rates between these two currencies:
   
  // USD = 6.4CNY, CNY = 0.13 EUR, EUR = 0.87 GBP, GBP = 89.4 INR
  //
   
  // Question: Input two currencies, return the rate
  
  // Example: CNY, INR; return 10.1111
   
  // Complexity?
  </code></pre>
  <p>Wondering if there is any Python 3 way to solve this problem? Looks like a Breadth-first Search problem. Any leads on how to solve this? Thanks!</p>
  <p>Comment:</p>
  <p>I see a solution here:</p>
  <p><a href="https://leetcode.com/problems/evaluate-division/discuss/88275/Python-fast-BFS-solution-with-detailed-explantion" rel="nofollow noreferrer">https://leetcode.com/problems/evaluate-division/discuss/88275/Python-fast-BFS-solution-with-detailed-explantion</a></p>
  <pre><code>class Solution(object):
      
      def calcEquation(self, equations, values, queries):
  
          graph = {}
          
          def build_graph(equations, values):
              def add_edge(f, t, value):
                  if f in graph:
                      graph[f].append((t, value))
                  else:
                      graph[f] = [(t, value)]
              
              for vertices, value in zip(equations, values):
                  f, t = vertices
                  add_edge(f, t, value)
                  add_edge(t, f, 1/value)
          
          def find_path(query):
              b, e = query
              
              if b not in graph or e not in graph:
                  return -1.0
                  
              q = collections.deque([(b, 1.0)])
              visited = set()
              
              while q:
                  front, cur_product = q.popleft()
                  if front == e:
                      return cur_product
                  visited.add(front)
                  for neighbor, value in graph[front]:
                      if neighbor not in visited:
                          q.append((neighbor, cur_product*value))
              
              return -1.0
          
          build_graph(equations, values)
          
          return [find_path(q) for q in queries]
      
  s=Solution()
  </code></pre>
  <p>Wonder how can I test this function?</p>
  <pre><code>s.calcEquation('USD/CNY=?, CNY/EUR = ?, EUR/GBP = ?, GBP/INR = ?', '6.4, 0.13, 0.87, 89.4','CNY/INR=?')
  </code></pre>
  <p>give me the error message</p>
  <pre><code>Traceback (most recent call last):
    File &quot;/home/coderpad/solution.py&quot;, line 45, in &lt;module&gt;
      s.calcEquation('USD/CNY=?, CNY/EUR = ?, EUR/GBP = ?, GBP/INR = ?', '6.4, 0.13, 0.87, 89.4','CNY/INR=?')
    File &quot;/home/coderpad/solution.py&quot;, line 39, in calcEquation
      build_graph(equations, values)
    File &quot;/home/coderpad/solution.py&quot;, line 15, in build_graph
      f, t = vertices
  ValueError: not enough values to unpack (expected 2, got 1)
  </code></pre>