Breadth-first Search: how to get currency exchange?

user_2736467 0
Viewed 1723

I am doing some LeetCode like questions to practice and encountered this question:

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?

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!

Comment:

I see a solution here:

https://leetcode.com/problems/evaluate-division/discuss/88275/Python-fast-BFS-solution-with-detailed-explantion

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()

Wonder how can I test this function?

s.calcEquation('USD/CNY=?, CNY/EUR = ?, EUR/GBP = ?, GBP/INR = ?', '6.4, 0.13, 0.87, 89.4','CNY/INR=?')

give me the error message

Traceback (most recent call last):
  File "/home/coderpad/solution.py", line 45, in <module>
    s.calcEquation('USD/CNY=?, CNY/EUR = ?, EUR/GBP = ?, GBP/INR = ?', '6.4, 0.13, 0.87, 89.4','CNY/INR=?')
  File "/home/coderpad/solution.py", line 39, in calcEquation
    build_graph(equations, values)
  File "/home/coderpad/solution.py", line 15, in build_graph
    f, t = vertices
ValueError: not enough values to unpack (expected 2, got 1)
breadth-first-search python-3.x numpy algorithm python
1 Answers

I guess this'd work, however you don't need the values variable here, because they are already in the equations.

Here, we are using a re.findall() to get those three desired strings (currencies and the ratio), and then we'd loop through:

import collections
import re


class Solution:
    def calcEquation(self, equations, values, queries):
        memo = collections.defaultdict(dict)
        for equation in equations:
            num, val, den = re.findall(
                r'^\s*([A-Z]{3})\s*=\s*([0-9.]+)\s*([A-Z]{3})\s*$', equation)[0]

            val = float(val)
            memo[num][num] = memo[den][den] = 1.
            memo[num][den] = val
            memo[den][num] = 1 / val

        for key in memo:
            for val in memo[key]:
                for i in memo[key]:
                    memo[val][i] = memo[val][key] * memo[key][i]

        return [memo[num].get(den, -1.) for num, den in queries]


equations = ['USD = 6.4CNY', 'CNY = 0.13 EUR', 'EUR = 0.87 GBP', 'GBP = 89.4 INR']
values = [6.4, 0.13, 0.87, 89.4]
queries = [["USD", "CNY"], ["CNY", "EUR"], ["EUR", "GBP"], ["GBP", "INR"]]

print(Solution().calcEquation(equations, queries))

Technically, you don't have to manually add the values, if you don't want to. We can safely remove the values variable:

import collections
import re


class Solution:
    def calcEquation(self, equations, queries):
        memo = collections.defaultdict(dict)
        for equation in equations:
            num, val, den = re.findall(
                r'^\s*([A-Z]{3})\s*=\s*([0-9.]+)\s*([A-Z]{3})\s*$', equation)[0]

            val = float(val)
            memo[num][num] = memo[den][den] = 1.
            memo[num][den] = val
            memo[den][num] = 1 / val

        for key in memo:
            for val in memo[key]:
                for i in memo[key]:
                    memo[val][i] = memo[val][key] * memo[key][i]

        return [memo[num].get(den, -1.) for num, den in queries]


equations = ['USD = 6.4CNY', 'CNY = 0.13 EUR', 'EUR = 0.87 GBP', 'GBP = 89.4 INR']
queries = [["USD", "CNY"], ["CNY", "EUR"], ["EUR", "GBP"], ["GBP", "INR"]]

print(Solution().calcEquation(equations, queries))

Outputs

[6.399999999999987, 0.12999999999999973, 0.8699999999999983, 89.39999999999993]

RegEx Circuit

jex.im visualizes regular expressions:

enter image description here

If you wish to simplify/update/explore the expression, it's been explained on the top right panel of regex101.com. You can watch the matching steps or modify them in this debugger link, if you'd be interested. The debugger demonstrates that how a RegEx engine might step by step consume some sample input strings and would perform the matching process.

user_65533280
Related