Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# anilpai/currency_arbitrage.py

Created Sep 18, 2019
Currency Arbitrage using Bellman Ford Algorithm
 from typing import Tuple, List from math import log rates = [ [1, 0.23, 0.25, 16.43, 18.21, 4.94], [4.34, 1, 1.11, 71.40, 79.09, 21.44], [3.93, 0.90, 1, 64.52, 71.48, 19.37], [0.061, 0.014, 0.015, 1, 1.11, 0.30], [0.055, 0.013, 0.014, 0.90, 1, 0.27], [0.20, 0.047, 0.052, 3.33, 3.69, 1], ] currencies = ('PLN', 'EUR', 'USD', 'RUB', 'INR', 'MXN') def negate_logarithm_convertor(graph: Tuple[Tuple[float]]) -> List[List[float]]: ''' log of each rate in graph and negate it''' result = [[-log(edge) for edge in row] for row in graph] return result def arbitrage(currency_tuple: tuple, rates_matrix: Tuple[Tuple[float, ...]]): ''' Calculates arbitrage situations and prints out the details of this calculations''' trans_graph = negate_logarithm_convertor(rates_matrix) # Pick any source vertex -- we can run Bellman-Ford from any vertex and get the right result source = 0 n = len(trans_graph) min_dist = [float('inf')] * n pre = [-1] * n min_dist[source] = source # 'Relax edges |V-1| times' for _ in range(n-1): for source_curr in range(n): for dest_curr in range(n): if min_dist[dest_curr] > min_dist[source_curr] + trans_graph[source_curr][dest_curr]: min_dist[dest_curr] = min_dist[source_curr] + trans_graph[source_curr][dest_curr] pre[dest_curr] = source_curr # if we can still relax edges, then we have a negative cycle for source_curr in range(n): for dest_curr in range(n): if min_dist[dest_curr] > min_dist[source_curr] + trans_graph[source_curr][dest_curr]: # negative cycle exists, and use the predecessor chain to print the cycle print_cycle = [dest_curr, source_curr] # Start from the source and go backwards until you see the source vertex again or any vertex that already exists in print_cycle array while pre[source_curr] not in print_cycle: print_cycle.append(pre[source_curr]) source_curr = pre[source_curr] print_cycle.append(pre[source_curr]) print("Arbitrage Opportunity: \n") print(" --> ".join([currencies[p] for p in print_cycle[::-1]])) if __name__ == "__main__": arbitrage(currencies, rates) # Time Complexity: O(N^3) # Space Complexity: O(N^2)

### CodeForcer commented Sep 13, 2020

 This results in seemingly impossible trips: ``````Arbitrage Opportunity: RUB --> INR --> PLN --> RUB Arbitrage Opportunity: USD --> MXN --> USD --> RUB --> INR --> EUR --> PLN Arbitrage Opportunity: USD --> MXN --> USD --> PLN `````` In everything except the first trip the starting and ending currencies are different. Can you please explain why this is happening? Thanks
to join this conversation on GitHub. Already have an account? Sign in to comment