{{ message }}

Instantly share code, notes, and snippets.

anilpai/currency_arbitrage.py

Created Sep 18, 2019
Currency Arbitrage using Bellman Ford Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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