A money-transfer desk has a list of quotes. Each quote is a tuple (a, b, r) meaning "one unit of a converts into r units of b". Every quote also works backwards: one unit of b converts into 1 / r units of a.
You want to turn source into target through a chain of conversions and end up with as many units of target as possible per unit of source. Write
def best_rate(quotes: list[tuple[str, str, float]], source: str, target: str) -> float
returning the largest product of rates over all conversion chains from source to target.
Rules:
- A chain may not visit the same currency twice. Quotes can contain profitable loops, and without this rule the answer could be unbounded; your search must not run forever on them.
- The same pair may be quoted more than once (in either direction). Each quote is a separate option.
- If
source == target, the answer is1.0(convert nothing), even if the currency never appears in a quote. - If
targetcan't be reached fromsource(or either currency is unknown), return-1.0. - All rates are positive. Results are compared with a relative tolerance of
1e-9.
Constraints: at most 9 distinct currencies and 60 quotes, so trying every simple chain is fine, as long as you back out of each branch correctly.
quotes = [("EUR", "USD", 1.10), ("USD", "JPY", 150.0), ("EUR", "JPY", 160.0)]
best_rate(quotes, "EUR", "JPY") # 165.0 via USD beats the direct 160.0
best_rate(quotes, "JPY", "EUR") # 1/150 * 1/1.10 = 0.00606... vs 1/160 = 0.00625 -> 0.00625
best_rate(quotes, "EUR", "GBP") # -1.0
best_rate(quotes, "GBP", "GBP") # 1.0
Show hint
Build an adjacency list with both directions, then DFS from source, carrying the running product and a visited set. Add a currency to visited before recursing into it and remove it afterwards, so other branches may still pass through it.