Golf A Free Lunch

Question

Find a maximally profitable sequence of exchanges given an exchange rate table.

---

As an example consider the currencies Ariary (your home currency), Baht, Cedi, and Denar where the rate from one to another (after any transaction rate has been levied) is given by the (row, column) entry in the exchange rate table below:

                       TO
       A          B          C          D

   A   0.9999     1.719828   4.509549   0.709929

F  B   0.579942   0.9999     2.619738   0.409959
R
O  C   0.219978   0.379962   0.9999     0.149985
M
   D   1.39986    2.429757   6.409359   0.9999

Obviously exchanging A for A is not a great idea as this desk will happily charge you for doing nothing.

Less obviously, but true with this table, exchanging A for any other currency and then exchanging back again is a loss maker:

via B: 1.719828 × 0.579942 = 0.997400489976
via C: 4.509549 × 0.219978 = 0.992001569922
via D: 0.709929 × 1.39986  = 0.99380120994

However, exchanging A to D then D to B then B back to A does profit (given enough capital not to succumb to rounding):

0.709929 × 2.429757 × 0.579942 = 1.0003738278192194

One could repeatedly take this "free lunch" while the opportunity exists.

But an even more enticing chain exists here, namely A to D then D to C then C to B and finally B back to A:

0.709929 × 6.409359 × 0.379962 × 0.579942 = 1.0026612752037345

---

Challenge Details

Given an exchange rate table in any reasonable format which fixes the meaning of the home-currency (e.g. 1^st row and 1^st column are always the home-currency)
(or given such a table and a home-currency index)
find a* maximal arbitrage sequence of exchanges starting and ending with the home currency as indexes into the currency list without repeating the use of any exchange (i.e. a Y->X exchange may follow an X->Y one, but an X->Y may not follow an X->Y).

If no such profitable opportunity exists yield an empty list, or some other result not confusable with an identified opportunity.
- e.g. for the above example (A->D,D->C,C->B,B->A):

• using 0-indexing one might return [[0,3],[3,2],[2,1],[1,0]] or [0,3,2,1,0]
• using 1-indexing one might return [[1,4],[4,3],[3,2],[2,1]] or [1,4,3,2,1]

Other formats are fine so long as there is no ambiguity.
- One thing to watch out for is that it is possible for the best opportunity to be a single transaction from home->home (a foolish desk). If you decide to go with excluding the home currency index from both ends of the flat option above (i.e. [3,2,1] or [4,3,2]) and an empty list for "no opportunity" then make sure the home->home is not also an empty list.

* If multiple equally profitable valid opportunities happen to exist, return any of them, some of them, or all of them.

^{The Bellman-Ford algorithm is one way to approach this, but probably not the best suited for golf.}

Test Cases

Inputs shown are in the arrangement used in the example, and the results shown use 0-indexing to list the to-currency-indices (when an opportunity exists the home currency is at the trailing end only; no opportunity is an empty list).

[[0.999900, 1.719828, 4.509549, 0.709929],
 [0.579942, 0.999900, 2.619738, 0.409959],
 [0.219978, 0.379962, 0.999900, 0.149985],
 [1.399860, 2.429757, 6.409359, 0.999900]]  ->  [3, 2, 1, 0]

[[0.9999, 1.5645, 0.9048, 1.0929],
 [0.6382, 0.9999, 0.5790, 0.6998],
 [1.1051, 1.7269, 0.9999, 1.2087],
 [0.9131, 1.4288, 0.8262, 0.9999]]  ->  [1, 2, 0]

[[0.9999, 1.4288, 0.8262, 0.9131],
 [0.6998, 0.9999, 0.5790, 0.6382],
 [1.2087, 1.7269, 0.9999, 1.1051],
 [1.0929, 1.5645, 0.9048, 0.9999]]  ->  [1, 2, 3, 1, 0]

[[1.002662, 1.719828, 4.509549, 0.709929],
 [0.579942, 0.999900, 2.619738, 0.409959],
 [0.219978, 0.379962, 0.999900, 0.149985],
 [1.399860, 2.429757, 6.409359, 0.999900]]  ->  [3, 2, 1, 0, 0]

[[1.002662, 1.719828, 4.509549, 0.709929],
 [0.579942, 1.002604, 2.619738, 0.409959],
 [0.219978, 0.379962, 1.003000, 0.149985],
 [1.399860, 2.429757, 6.409359, 1.002244]]  ->  [3, 3, 2, 2, 1, 1, 0, 0]

[[0.9999, 1.4288, 0.8262, 0.9131],
 [0.6998, 0.9999, 0.5790, 0.6382],
 [1.2087, 1.7269, 1.0001, 1.1051],
 [1.0929, 1.4974, 0.9048, 0.9999]]  ->  [1, 2, 2, 0]

[[0.9999, 1.3262, 0.7262, 0.9131],
 [0.6998, 0.9999, 0.5490, 0.6382],
 [1.2087, 1.7269, 0.9999, 1.2051],
 [1.0929, 1.5645, 0.9048, 0.9999]]  ->  [3, 2, 3, 1, 0]

[[0.9999, 1.5645, 0.9048, 0.5790],
 [0.6382, 0.9999, 0.5790, 0.3585],
 [1.1051, 1.7269, 0.9999, 0.6391],
 [1.7271, 2.6992, 1.5645, 0.9999]]  ->  [1, 2, 0]  and/or  [3, 2, 0]

[[0.9999, 1.2645, 0.7048, 0.3790],
 [0.4382, 0.9999, 0.3790, 0.1585],
 [1.0001, 1.5269, 1.0001, 0.4391],
 [1.5271, 2.4992, 1.3645, 0.9999]]  ->  []

[[0.9999, 1.2645, 0.7048, 0.3790],
 [0.4382, 0.9999, 0.3790, 0.1585],
 [0.9999, 1.5269, 1.4190, 0.4391],
 [1.5271, 2.4992, 1.3645, 0.9999]]  ->  [2, 2, 0]

---

This is code-golf so the shortest solution in bytes wins, but competition should be made intra-language too, so don't let code-golfing languages put you off submitting in your favourite one!

Answer 1

JavaScript (ES6), 122 113 103 bytes

Takes input as a transposed matrix with respect to the format described in the challenge. Returns a string describing the exchanges in (from,to) format.

a=>(g=(s,x=b=0,h='')=>a.map((r,y)=>~h.search(k=`(${x},${y})`)||g(s*r[x],y,h+k),x|s<b||(b=s,p=h)))(1)&&p

First test case: Try it online!

More test cases: Try it online!

Commented

a => (                  // given the exchange rate matrix a[][]
  g = (                 // g = recursive function taking:
    s,                  //   s = current amount of money
    x = b = 0,          //   x = ID of current currency, b = best result so far
    h = ''              //   h = exchange history, as a string
  ) =>                  //  
  a.map((r, y) =>       // for each row at position y in a[]:
    ~h.search(          //   if we can't find in h ...
      k = `(${x},${y})` //     ... the exchange key k from currency x to currency y
    ) ||                //   then:
    g(                  //   do a recursive call to g() with:
      s * r[x],         //     s = new amount obtained by applying the exchange rate
      y,                //     x = y
      h + k             //     h = h + k
    ),                  //   end of recursive call
    x | s < b ||        //   if x is our home currency and s is greater than or equal to b
    (b = s, p = h)      //   then set b to s and set p to h
  )                     // end of map()
)(1)                    // initial call to g() with s = 1
&& p                    // return p

Answer 2

Python 2, 143 125 124 bytes

lambda M:g(M)[1]
g=lambda M,s=[],p=1,x=0:max([(p,s)]*-~-x+[g(M,s+[(x,y)],p*M[x][y],y)for y in range(len(M))if(x,y)not in s])

Try it online!

Uses 0-based indexing (0 is the home currency); returns a list of tuples of the exchanges yielding the max payout.

The approach is brute force: via the recursion, we end up visiting every non-edge-repeating path starting at 0 (for n being the number of currencies, this gives a maximum depth of n^2). For the subset of these paths also ending with '0', we maximize the payoff.

Answer 3

Haskell, 175 bytes

e?l|e`elem`l=0|2>1=1
w[]=[]
w l=[maximum l];0!q=[q]
n!c@(v,i,(h,l))=do{j<-[0..3];c:((n-1)!(v*l!!i!!j*(i,j)?h,j,((i,j):h,l)))}
z l=w$filter(\(v,e,_)->v>1&&e==0)$12!(1,0,([],l))

Try it here