Compute currency conversion via graph search

Given a list of currency pairs, e.g., [('USD','CAD'), ('CAD','EUR'), ...], and a parallel list of conversion ratios [1.1, 1.2, ...] where ratio r means 1 unit of the first currency converts to r units of the second, implement a function rate(src, dst) that returns the conversion ratio from src to dst, or -1 if no path exists. Specify your data structures, the search algorithm (e.g., build a directed graph and use DFS/BFS to find a path while multiplying edge weights), and analyze time and space complexity. Follow-up: if conversions are directional and not reciprocal, compute the best achievable rate from src to dst. Explain how to model this as a weighted directed graph and select an appropriate shortest-path algorithm (e.g., transform multiplicative weights with -log and use Dijkstra), and discuss handling cycles/arbitrage and floating-point precision.

Currency Conversion via Graph Search

You are given a list of directed currency pairs, e.g. [('USD','CAD'), ('CAD','EUR')], and a parallel list of conversion ratios, e.g. [1.1, 1.2], where a ratio r for pair (a, b) means 1 unit of a converts to r units of b.

Implement solution(pairs, ratios, src, dst) that returns the conversion ratio from src to dst following the directed edges, or -1.0 if no path exists. If src == dst the answer is 1.0.

Model the input as a directed graph (adjacency list mapping each currency to a list of (neighbor, ratio) edges) and run a BFS/DFS from src, multiplying edge weights along the path. Because conversions here are consistent, any src -> dst path yields the same product, so the first path found is a valid answer.

Return the product of ratios along a path from src to dst, or -1.0 if unreachable.

Constraints

• 0 <= number of pairs == len(ratios) <= 10^4
• Each ratio is a positive real number (ratio > 0).
• Currency codes are short non-empty strings.
• Edges are directed: a pair (a, b) does NOT imply an edge b -> a.
• If src == dst, return 1.0 even if the currency never appears in any pair.

Examples

Example 1

Input: ([['USD','CAD'],['CAD','EUR']], [2.0, 1.5], 'USD', 'EUR')
Output: 3.0

Explanation: USD->CAD (2.0) then CAD->EUR (1.5): 2.0 * 1.5 = 3.0.

Example 2

Input: ([['USD','CAD'],['CAD','EUR']], [2.0, 1.5], 'USD', 'CAD')
Output: 2.0

Explanation: Single direct edge USD->CAD with ratio 2.0.

Hints

1. Build an adjacency list: map each currency to a list of (neighbor, ratio) edges.
2. Run BFS or DFS from src, carrying the running product of ratios; stop when you reach dst.
3. Use a visited set to avoid cycles. In a consistent graph every src->dst path gives the same product, so the first one found is correct.
4. Handle the src == dst case (return 1.0) and the unreachable case (return -1.0) explicitly.

Best Achievable Currency Rate (Non-Reciprocal Conversions)

Follow-up: now conversions are genuinely directional and NOT reciprocal — the rate from A to B and the rate from B to A are independent, and there may be multiple routes between two currencies with different overall products. Among all paths from src to dst, return the BEST (maximum) achievable conversion ratio.

Implement solution(pairs, ratios, src, dst) that returns the maximum product of edge ratios over any simple path from src to dst, or -1.0 if no path exists. If src == dst, return 1.0.

Model the input as a weighted directed graph. To maximize a product of positive weights you can equivalently minimize the sum of -log(weight) and run a shortest-path algorithm (e.g. Dijkstra when all -log weights are non-negative, i.e. all ratios <= 1; Bellman-Ford for the general case, which also detects positive-product cycles / arbitrage). The reference implementation explores all simple paths (no node repeated) with DFS, which directly handles arbitrary ratios and naturally avoids infinite loops from cycles. Floating-point products should be compared with care in production; tests here use exactly representable values.

Constraints

• 0 <= number of pairs == len(ratios) <= number of edges in the graph.
• Each ratio is a positive real number; a->b and b->a may have unrelated ratios.
• Paths considered are simple (no repeated node), so cycles cannot inflate the product unboundedly.
• Return the maximum product over all simple src->dst paths, or -1.0 if dst is unreachable.
• If src == dst, return 1.0.

Examples

Example 1

Input: ([['USD','CAD'],['CAD','USD']], [2.0, 0.4], 'USD', 'CAD')
Output: 2.0

Explanation: Edges are non-reciprocal (USD->CAD is 2.0, CAD->USD is 0.4). Only the direct USD->CAD path reaches CAD, giving 2.0.

Example 2

Input: ([['A','B'],['A','C'],['C','B']], [2.0, 4.0, 3.0], 'A', 'B')
Output: 12.0

Explanation: Direct A->B = 2.0; detour A->C->B = 4.0 * 3.0 = 12.0. The maximum is 12.0.

Hints

1. Maximizing a product of positive weights is equivalent to minimizing the sum of -log(weight); a shortest-path framing falls out naturally.
2. If every ratio is <= 1 the -log weights are non-negative and Dijkstra works; otherwise some weights are negative and you need Bellman-Ford (which also detects arbitrage cycles).
3. A direct approach: DFS every simple path (track a visited set, multiply ratios, keep the running maximum at dst), backtracking by removing nodes from visited.
4. Restricting to simple paths is what makes the search terminate; a positive-product cycle would otherwise let the product grow without bound (arbitrage).