Currency Arbitrage

Graph Algorithm Finance

You are given a list of currency conversion rates, each represented as a tuple in the form (from_currency, to_currency, rate). The conversion from one currency to another means that one unit of from_currency can be exchanged for the given rate units of to_currency.

An arbitrage opportunity exists if you can start with some amount of a currency, perform a series of exchanges, and end up with more of that currency than you originally had.

Your task is to write a program that determines whether an arbitrage opportunity exists given the list of conversion rates.

Input

  • A list (or array) of tuples/lists, where each tuple/list contains three elements: a string from_currency, a string to_currency, and a positive floating-point number rate.

Output

  • Return a boolean value: true if there exists an arbitrage opportunity, or false otherwise.

Example

Given the following list of conversion rates:

[
  ("USD", "EUR", 0.9),
  ("EUR", "GBP", 0.8),
  ("GBP", "USD", 1.5)
]

An arbitrage opportunity exists if you can start with some amount of USD, convert it to EUR, then to GBP, and finally back to USD in such a way that you end up with more USD than you started with.

Requirements

  • Your solution should efficiently determine the existence of an arbitrage opportunity.
  • Consider the problem from the standpoint of graph theory and appropriate algorithms.
  • Make sure your code is clean, well-documented, and handles possible edge cases.

Good luck!