Welcome, Borger.

The Arbitrage Puzzle

Introduction

Daily trading volume in currency exchange markets often exceeds $1 trillion. With the advent of crypto-currency pairs, your knowledge of algorithms, and a good set of noise-canceling headphones, you’re convinced there are some profitable arbitrage opportunities to capitalize on.

Sometimes these new currency pairs drift in a way that creates an arbitrage path where you can convert coins through a certain sequence to return a profit in your base currency. This is referred to as an arbitrage loop.

For example, you could do the following trades with €100 and the exchange data below:

1. Trade €100 for 102.11 DAI
2. Trade 102.11 DAI for 0.00438158 BTC
3. Trade 0.00438158 BTC for €101.20965

In this puzzle, you’ll be working in a market where prices are set independently of supply and demand. Luckily, the currency exchange broker is a close friend of ours, so all trading costs are waived. Your mission is to write a program that efficiently finds the best arbitrage opportunities.

Data source

To access real-time exchange rates, use our API: https://api.swissborg.io/website/v1/challenge/rates

You can easily get a preview of the API response using curl:

1curl -s https://api.swissborg.io/website/v1/challenge/rates | jq

The output will look like the JSON below, where BTC-BORG is the quantity of BORG that you can purchase for 1 BTC:

1{
2    "BTC-BTC": "1.0000000000",
3    "BTC-BORG": "116352.2654440156",
4    "BTC-DAI": "23524.1391553039",
5    "BTC-EUR": "23258.8865583847",
6    "BORG-BTC": "0.0000086866",
7    "BORG-BORG": "1.0000000000",
8    "BORG-DAI": "0.2053990550",
9    "BORG-EUR": "0.2017539914",
10    "DAI-BTC": "0.0000429088",
11    "DAI-BORG": "4.9320433378",
12    "DAI-DAI": "1.0000000000",
13    "DAI-EUR": "0.9907652193",
14    "EUR-BTC": "0.0000435564",
15    "EUR-BORG": "5.0427577751",
16    "EUR-DAI": "1.0211378960",
17    "EUR-EUR": "1.0000000000"
18}

These are real-time market prices that have been slightly modified algorithmically to present arbitrage opportunities. Rates are updated every 10 seconds. You only have to pull the data once per run of your algorithm.

Task

Given these exchange rates and the promise of riches, write a program that discovers arbitrage opportunities. You can use any technique you’d like, but we like solutions that would scale with larger sets of currencies.

Full implementation of the core algorithm is encouraged, packaged as a Scala script, and executable by Scala CLI (cf. documentation).

Please also include:

• An algorithmic complexity analysis
• A note about BORG and what are its key features

Getting started

You're encouraged to take a look at Scala CLI and install it.

We provided a small Scala code template that you can retrieve at https://api.swissborg.io/website/v1/challenge/template. Please use it and keep it as it is.

Feel free to use curl or wget to get started:

1curl https://api.swissborg.io/website/v1/challenge/template > main.sc

Submitting

Simply send your script in a single .zip file by replying to the email you received.
Please do not publish your solution on a public repository.

Good luck and be awesome!