/* 

  Arbitrage loop problem in Picat.

  This program shows some different approaches and examples for
  detecting arbitrage loops (and don't care about broker's fees etc).

  The most general approaches are
    go7/0 and go8/0
  which uses
    arbitrage_loop4/1
    profit4/6


  First versions where inspired by Dan Goldin's Prolog code at
  http://dangoldin.com/2013/06/07/fun-with-prolog-priceonomics-puzzle/

  Problem description and some examples from
  http://priceonomics.com/jobs/puzzle/
  """
  Daily trading volume in currency exchange markets often exceeds $1 
  trillion. With the advent of new crypto-currencies, your knowledge of 
  algorithms, and a good pair of sound-canceling headphones, you're 
  convinced that there could be some profitable arbitrage opportunities to 
  exploit.

  Sometimes, these currency pairs drift in a way that creates arbitrage 
  loops where you can convert through a certain sequence of currencies 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 US and the 
  exchange data below:

			TO 		
		USD 	EUR 	JPY 	BTC
	USD 	- 	0.7779 	102.4590 	0.0083
  FROM 	EUR 	1.2851 	- 	131.7110 	0.01125
	JPY 	0.0098 	0.0075 	- 	0.0000811
	BTC 	115.65 	88.8499 	12325.44 	-

  Trade $100 to €77.79
  Trade €77.79 to .8751375 BTC
  Trade .8751375 BTC for $101.20965.
  """

  Notes: 
    - Picat don't support HTTP calls right now, so I just went to 
          http://fx.priceonomics.com/v1/rates/
      and extracted the entries.
    - This program don't care at all about such reality stuff like
      broker's fee etc.
    - This program is for fun and not for profit. :-)


  Also, see
    - https://en.wikipedia.org/wiki/Triangular_arbitrage
    - "Two-Currency, Three-Currency and Multi-Currency Arbitrage"
      http://www.fem.uniag.sk/mefi/pdf/arbitraz.pdf

  A warning:
  From Triangular Arbitrage
  http://www.nusinvest.com/wp-content/uploads/2013/01/Triangular-Arbitrage.pdf
  """
  As a matter of fact, triangular arbitrage opportunities do actually exist in 
  the forex trading market. However, it is important to note that these opportunities 
  are very rare and often exist only for a few seconds. Why? One has to realize 
  that these arbitrage opportunities will not last forever. Once people start to 
  engage in these profit taking activities, the market will correct itself and bring 
  the foreign exchange rate to the equivalent level. Furthermore, with the presence 
  of several high-frequency-trading (HFT) firms today, which uses advance and 
  complicated computer programs to execute trades automatically, the time for the market to
  correct itself is made a lot faster as compared to a century ago. These complex computer
  soft wares are programmed to specifically sift out such arbitraging opportunities and will
  profit from these imbalance at the very split second that these opportunities present
  themselves.
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import util.

main => go.

%
% Arbitrage loops (chains) of length 3 using fail/0.
% This is straight port of the Prolog code at
%   http://dangoldin.com/2013/06/07/fun-with-prolog-priceonomics-puzzle/
% 
go ?=>
  profit(First, Second, Profit),
  Profit > 1.0,
  print('usd '),
  print(first=First), print(' '),
  print(second=Second), print(' '), print(usd),print(' '), 
  println(profit=Profit), 
  fail,
  nl.

go => true.

%
% Loops of length 4 using the same approach as go/0, 
% i.e. using fail to generate all chains.
% 
go2 ?=>
  profit2(First, Second, Third, Profit),
  Profit > 1.0,
  write('usd '),
  write(First), write(' '),
  write(Second), write(' '),
  write(Third), write(' usd '),
  write(Profit), nl, fail,
  nl.

go2 => true.

%
% A little more general approach than go/0 and go2/0
%
go3 ?=>
  Start = usd,
  Len = 4,
  profit3(Start,Len,Currencies,Profit),
  println([Currencies,Profit]),
  fail,
  nl.

go3 => true.

%
% Check all possible chains and show the most protifable,
% using findall/2 instead of fail/0.
%
go4 =>
  currencies(All),
  MaxProfit = 0,
  MaxArb = [],
  foreach(Len in 2..4, Start in All)
     writeln([len=Len,start=Start]),
     Chains=findall([Chain,Profit],profit3(Start,Len,Chain,Profit)),
     foreach([Chain,Profit] in Chains) 
       println([Chain,Profit]),
       if Profit > MaxProfit then
          println(newMax=[Profit,Chain]),
          MaxProfit := Profit,
          MaxArb := Chain
       end
    end
  end,
  println([maxArb=MaxArb,maxProfit=MaxProfit]),
  nl.

%
% Slighly more general version, with parsing of the rates.
%
% From http://fx.priceonomics.com/v1/rates/ (in JSON format)
%
go5 => 
  % Manual changed to conform to Picat's syntax of lists/strings.
  X=["USD_JPY: 114.7002817", "USD_USD: 1.0000000", "JPY_EUR: 0.0066797", "BTC_USD: 111.6923455", 
     "JPY_BTC: 0.0000714", "USD_EUR: 0.8708395", "EUR_USD: 1.3780821", "EUR_JPY: 141.1955858", 
     "JPY_USD: 0.0085868", "BTC_BTC: 1.0000000", "EUR_BTC: 0.0120654", "BTC_JPY: 11433.5226075", 
     "JPY_JPY: 1.0000000", "BTC_EUR: 82.3871099", "EUR_EUR: 1.0000000", "USD_BTC: 0.0092938"],

  Cs = [$exchange(From,To,Rate.parse_term()) : 
           C in X,
           [FromTo,Rate] = split(C,":"),
           [From,To] = split(FromTo,"_"),
           From != To],
  println(Cs),

  cl_facts(Cs), % add them

  currencies(All),
  MaxProfit = 0,
  MaxArb = [],
  foreach(Len in 2..4, Start in All)
     println([len=Len,start=Start]),
     Chains=findall([Chain,Profit],profit3(Start,Len,Chain,Profit)) ->
       foreach([Chain,Profit] in Chains) 
          println([Chain,Profit]),
          if Profit > MaxProfit then
             println(newMax=[Profit,Chain]),
             MaxProfit := Profit,
             MaxArb := Chain
          end
       end
     ;
       true
  end,
  println([maxArb=MaxArb,maxProfit=MaxProfit]),
  nl.

%
% Different approach:
% Using an "exhange matrix" (i.e. a hash table) instead and 
% the general arbitrage_loop4/1.
%
go6 => 
  % Manual changed to conform to Picat's syntax of lists/strings.
  X=["USD_JPY: 114.7002817", "USD_USD: 1.0000000", "JPY_EUR: 0.0066797", "BTC_USD: 111.6923455", 
     "JPY_BTC: 0.0000714", "USD_EUR: 0.8708395", "EUR_USD: 1.3780821", "EUR_JPY: 141.1955858", 
     "JPY_USD: 0.0085868", "BTC_BTC: 1.0000000", "EUR_BTC: 0.0120654", "BTC_JPY: 11433.5226075", 
     "JPY_JPY: 1.0000000", "BTC_EUR: 82.3871099", "EUR_EUR: 1.0000000", "USD_BTC: 0.0092938"],

  Exchange = new_map(),
  foreach(C in X)  
     [FromTo,Rate] = split(C,":"),
     [From,To] = split(FromTo,"_"),
     Exchange.put([From,To], Rate.parse_term())
  end,
  println(exchange=Exchange),

  arbitrage_loop4(Exchange),

  nl.

%
% Example from 
% "Triangular Arbitrage in Forex Market"
% http://www.nusinvest.com/wp-content/uploads/2013/01/Triangular-Arbitrage.pdf
% page 2
%
go7 => 
  Exchange = new_map([ 
                     [eur,usd]=1.1837,
                     [eur,gbp]=0.7231,
                     [gbp,usd]=1.6388,
                     [usd,eur]=1/1.1837,
                     [gbp,eur]=1/0.7231,
                     [usd,gbp]=1/1.6388
                     ]),
  arbitrage_loop4(Exchange),
  nl.

% 
% Example from
% "Two-Currency, Three-Currency and Multi-Currency Arbitrage"
% http://www.fem.uniag.sk/mefi/pdf/arbitraz.pdf
% page 17
%
% Result (example):
% """
% newMax=[1.010302582169334,[aud,dkk,eur,aud]]
% newMax=[1.010496754437378,[aud,nzd,eur,aud]]
% newMax=[1.010586305727208,[aud,sek,eur,aud]]
% newMax(tie)=[1.010586305727208,[eur,aud,sek,eur]]
% newMax=[1.010821556965591,[aud,nzd,sek,eur,aud]]
% newMax=[1.010994979070738,[aud,usd,sek,eur,aud]]
% newMax(tie)=[1.010994979070738,[usd,sek,eur,aud,usd]]
% newMax(tie)=[1.010994979070738,[eur,aud,usd,sek,eur]]
% newMax(tie)=[1.010994979070738,[sek,eur,aud,usd,sek]]
% newMax=[1.011018346802945,[aud,nzd,usd,sek,eur,aud]]
% newMax=[1.011018346802945,[nzd,usd,sek,eur,aud,nzd]]
% newMax=[1.011110812688754,[aud,nzd,dkk,usd,sek,eur,aud]]
% newMax(tie)=[1.011110812688754,[dkk,usd,sek,eur,aud,nzd,dkk]]
% newMax(tie)=[1.011110812688754,[nzd,dkk,usd,sek,eur,aud,nzd]]
% newMax(tie)=[1.011110812688754,[usd,sek,eur,aud,nzd,dkk,usd]]
% newMax(tie)=[1.011110812688754,[eur,aud,nzd,dkk,usd,sek,eur]]
% [maxArb=[aud,nzd,dkk,usd,sek,eur,aud],maxProfit=1.011110812688754]
% Real profit where we start with 1000 AUD: 1000*1.011111-1000 = 11.110813 AUD
% """
go8 =>
   Exchange = new_map([
                       [sek,usd]=10.54,
                       [dkk,usd]=8.2449,
                       [dkk,sek]=0.7819,
                       [nzd,usd]=2.3941,
                       [nzd,sek]=0.2271,
                       [nzd,dkk]=0.2904,
                       [eur,usd]=1.1073,
                       [eur,sek]=0.1050,
                       [eur,dkk]=0.1343,
                       [eur,nzd]=0.4625,
                       [aud,usd]=1.9296,        
                       [aud,sek]=0.1830,
                       [aud,dkk]=0.2340,
                       [aud,nzd]=0.8060,
                       [aud,eur]=1.7246
                      ]),
    foreach([From,To]=Rate in Exchange) 
       Exchange.put([To,From],1/Rate)
    end,
    Currencies = Exchange.keys().flatten().sort_remove_dups(),
    println(currencies=Currencies),

    foreach(C1 in Currencies) 
      foreach(C2 in Currencies)
        if C1 == C2 then
          printf("%3.5f, ", 0)
        else
          printf("%3.5f, ", Exchange.get([C1,C2]))
        end
      end,
      nl
    end,

    arbitrage_loop4(Exchange),

    nl.

%
% Random
%
go9 =>
   garbage_collect(200_000_000),
   N = 9,
   _ = random2(),
   Exchange = new_map([ ["C" ++ From.to_string(),"C" ++ To.to_string()]=R : 
                          From in 1..N, To in 1..N, From != To, R = (1+random() mod 200) / 10.0]),
   foreach([From,To]=Rate in Exchange) 
      Exchange.put([To,From],1/Rate)
   end,
   foreach(From in 1..N)
     foreach(To in 1..N)
        if From == To then
           printf("%3.5f ", 0)
        else
           printf("%3.5f ", Exchange.get(["C"++From.to_string(),"C"++To.to_string()]))
        end
     end,
     nl
   end,
   nl,
   arbitrage_loop4(Exchange),
   nl.


%
% Completely different approach, using all permutations instead.
% Random tests.
%
go10 => 
    % Real currencies per 2015-11-20 (via Frink)
    % USD,EUR,JPY,BTC
    Exchange =
    {
       {0,          0.93916996158794857105,   122.78993466347576556,  0.0031086407779062682633},
       {1.06477,    0,                        130.74095175414900566,  0.0033099874410912572587},
       {0.00814412, 0.0076487128675676437165, 0,                      0.000025317143532161997489},
       {321.684,    302.11594992345764813,    39498.926833101673355,  0}
    },
    Currencies = ["USD","EUR","JPY","BTC"],

    Start = 1000,
    profit5(Exchange,Currencies,Start),

    nl.

%
% Real currencies per 2015-11-21 via this Frink program
%   use samples/bitcoin.frink
%   currencies = [USD,SEK,EUR,JPY,BTC,GBP,NOK,DKK,ITL,FIM]
%   for c1 = currencies
%   {
%     for c2 = currencies
%     {
%       print[c1->c2]
%       print[", "]
%     }
%     println[]
%   }
%
go11 =>
    Exchange =
    {
    {1, 8.7223501500244225804, 0.93915232111496163563, 122.78993466347576556, 0.0030808855697481684135, 0.6582411795681937862, 8.6583085128489298331, 7.0071192331408711251, 1818.4463194646494036, 5.5839405868721556803}, 
    {0.114648, 1.0, 0.1076719353111881216, 14.07762042929816957, 0.00035321736880048801227, 0.0754660347551342812, 0.99265775438110410751, 0.80335220584113459275, 208.48123363398312482, 0.64018762040371890444}, 
    {1.06479, 9.2874712162445049194, 1.0, 130.74549453032236041, 0.003280496145812152245, 0.70088862559241706161, 9.219280321396411997, 7.4611104882560681653, 1936.2634565027640385, 5.9457240974956026468}, 
    {0.00814399, 0.071034732398297397251, 0.007648447111637036411, 0.99999999999999999996, 0.000025090701271173386078, 0.0053607095839915745129, 0.070513177945556556071, 0.057065908963506923034, 14.809408641256910096, 0.045475556300080967139}, 
    {324.582, 2831.11785639522713, 304.83193869213647762, 39855.402572940290937, 0.99999999999999999999, 213.65323854660347551, 2810.3310937175313431, 2274.3847749313302315, 590234.94326447483272, 1812.446603568138035}, 
    {1.5192, 13.250994347917102784, 1.4267602062378497168, 186.54246874075238304, 0.0046804813575614174538, 1.0, 13.153702292720094202, 10.645215538987611413, 2762.5836485306953739, 8.4831225395761789095}, 
    {0.115496, 1.0073965529272207103, 0.10846833647949360907, 14.181746293892797019, 0.00035582995976363445909, 0.076024223275408109531, 1.0, 0.80929424295083805146, 210.02327611288914752, 0.64492280202138649245}, 
    {0.142712, 1.2447840346102853953, 0.13402830605095840494, 17.523597155693953455, 0.00043967934142990061063, 0.093938915218536071616, 1.2356445244856964743, 1.0, 259.51411114343904569, 0.79689532903369908145}, 
    {0.00054992, 0.0047965947945014304654, 0.00051645864442753970267, 0.067524640870138592997, 0.000001694240592515912774, 0.00036197998946814112691, 0.0047613770173858834938, 0.0038533550086888278491, 1.0, 0.0030707206075327358517},
    {0.179085, 1.5620420766171237178, 0.16818809342687290452, 21.989835449208557475, 0.00055174039225835074033, 0.1178811216429699842, 1.5505731800235505992, 1.2548699478670329054, 325.65645912132673844, 1.0}

   },
    Currencies = ["USD","SEK","EUR","JPY","BTC","GBP","NOK","DKK","ITL","FIM"],
    Start = 1000,
    profit5(Exchange,Currencies,Start)
,
    nl.




%
% Exchange: Matrix of exchange rates
% Currencies: Names of the currencies
% Start: The start amount (in first currency)
%
% Using all permutations of range 1..length(Exchange)
%
profit5(Exchange,Currencies,Start) =>

    N = Exchange.len,

    MapC = new_map([I=C: {C,I} in zip(Currencies,1..N)]),
    foreach(Row in Exchange)
      println(Row.to_list())
    end,
    nl,

    Map2 = new_map(),
    foreach(M in 1..N)
      println(m=M),
      foreach(Perm in permutations(1..M))
        % calculate the profit
        P2 = Perm ++ [Perm[1]],
        Profit = [Exchange[P2[I],P2[I+1]] : I in 1..M].prod(),
        if Profit > 1 then
          Map2.put(Profit,Map2.get(Profit,[])++[Perm])
        end
      end
    end,

    MaxProfit = max(keys(Map2)),
    println(maxProfit=MaxProfit),
    nl,
    foreach(Cs=E in Map2, Cs=MaxProfit)
      println(e=E),
      println(lens=[EE.len : EE in E]),
      nl,
      foreach(C in Map2.get(Cs))
         LenC = C.len,
         CC = C ++ [C[1]],
         println([MapC.get(CCC) : CCC in CC]),
         println([Exchange[C[I],C[I+1]] : I in 1..LenC-1] ++ [Exchange[LenC,1]]),
         nl
      end,
      nl
    end,

    Start = 1000,
    printf("Real profit: %f - %f = %f\n",MaxProfit*Start,Start,MaxProfit*Start-Start),
    nl.


               
random_currency_matrix(N,Max,Div) = Matrix =>
  Matrix1 = new_array(N,N),
  bind_vars(Matrix1,0),

  foreach(From in 1..N,To in 1..N, From < To)
     Matrix1[From,To] := 0.01 + frand()*Max, % (1+random() mod Max) / Div,
     Matrix1[To,From] := 1/Matrix1[From,To] % + frand() % *Max
  end,
  Matrix = Matrix1.




%
% These are the exchange rates show at
% http://dangoldin.com/2013/06/07/fun-with-prolog-priceonomics-puzzle/
%
% Results (from go/0)
% usd eur jpy usd 1.0040882716200001
% usd eur btc usd 1.0120965187500002
% usd btc jpy usd 1.0025512896

index(-,-,-)
exchange(usd,eur,0.7779).
exchange(usd,jpy,102.459).
exchange(usd,btc,0.0083).
exchange(eur,usd,1.2851).
exchange(eur,jpy,131.711).
exchange(eur,btc,0.01125).
exchange(jpy,usd,0.0098).
exchange(jpy,eur,0.0075).
exchange(jpy,btc,0.0000811).
exchange(btc,usd,115.65).
exchange(btc,eur,88.8499).
exchange(btc,jpy,12325.44).

%
% Another example from 
% http://fx.priceonomics.com/v1/rates/ (per 2013-11-09 09:18)
%
% Max profit:
% Interestingly the best loop is just USD <-> EUR <-> USD
%    [[usd,eur,usd],1.2023634238308] 
%    [[eur,usd,eur],1.2023634238308]
% 
% Here are the possible profits (> 1.0)
% [[usd,eur,usd],1.2023634238308] 
% [new,1.2023634238308,[usd,eur,usd]]
% [[eur,usd,eur],1.2023634238308]
% [[jpy,eur,jpy],1.02915192590145]
% [[usd,eur,jpy,usd],1.108615335990782]
% [[eur,usd,jpy,eur],1.108641505563778]
% [[jpy,usd,eur,jpy],1.108615335990782]
% [[btc,usd,eur,btc],1.119786041425115]
% [[usd,eur,btc,jpy,usd],1.031551157856315]
% [[eur,btc,usd,jpy,eur],1.032500871424996]
% [[jpy,usd,eur,btc,jpy],1.031551157856315]
% [[btc,usd,jpy,eur,btc],1.032500871424996]
% [maxArb=[usd,eur,usd],maxProfit=1.2023634238308]
%
% However, if we allow repeating the currencies, then there are 
% better loops:
% [maxArb=[jpy,eur,usd,eur,jpy],maxProfit=1.237414633268929]
% [maxArb=[jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,eur,jpy],maxProfit=1.520888986922179]
% ...
% maxArb=[jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,jpy,eur,usd,eur,jpy],maxProfit=33.560740000202571]

%
% index(-,-,-)
% exchange(usd,jpy,110.3716895).
% exchange(jpy,eur,0.0070005).
% exchange(btc,usd,106.3737613).
% exchange(jpy,btc,0.0000748).
% exchange(usd,eur,0.8379756).
% exchange(eur,usd,1.4348430).
% exchange(eur,jpy,147.0112029).
% exchange(jpy,usd,0.0089991).
% exchange(eur,btc,0.0125623).
% exchange(btc,jpy,10889.0792695).
% exchange(btc,eur,78.4639871).
% exchange(usd,btc,0.0089430).
%

%
% Get the currencies
%
currencies(Currencies) => 
   Currencies = findall(C, exchange(C,_,_)).remove_dups().


%
% Calculate profit for a usd->x->y->usd currency chain.
%
profit(First,Second,Profit) =>
    exchange(usd,First,P1),
    exchange(First,Second,P2),
    exchange(Second,usd,P3),
    Profit is P1 * P2 * P3.

%
% Calculate profit for a usd->x->y->z->usd currency chain.
%
profit2(First,Second, Third,Profit) =>
    exchange(usd,First,P1),
    exchange(First,Second,P2),
    exchange(Second,Third,P3),
    exchange(Third,usd,P4),
    Profit is P1 * P2 * P3 * P4.

%
% A more general approach:
%   For any Start currency of any length (Len)
%   we greate an arbitrage loop (for positive profit).
%
profit3(Start,Len, Chain,Profit) =>
    Chain = new_list(Len+1),
    Chain[1] := Start,
    Profit1 := 1,
    currencies(All),
    println(all=All),
    foreach(I in 2..Len)
       % we just care about the currencies we haven't had before
       Left = difference(All,Chain.slice(1,I-1)),
       member(Chain[I],Left),
       exchange(Chain[I-1],Chain[I],P),
       Profit1 := Profit1 * P
    end,
    exchange(Chain[Len],Start,P2),
    Chain[Len+1] := Start,
    Profit1 := Profit1 * P2,
    %Profit1 > 1.0,
    Profit = Profit1.

%
% Using a exchange matrix instead.
%
profit4(Start,Len, All,Matrix,Currencies,Profit) =>
    Currencies = new_list(Len+1),
    Currencies[1] := Start,
    Profit1 := 1,
    foreach(I in 2..Len)
       Left = difference(All,Currencies.slice(1,I-1)),
       member(Currencies[I],Left),
       Profit1 := Profit1 * Matrix.get([Currencies[I-1],Currencies[I]])
    end,
    Currencies[Len+1] := Start,
    Profit1 := Profit1 * Matrix.get([Currencies[Len],Start]),
    Profit1 > 1.0, % comment this for showing unprofitable chains as well
    Profit = Profit1.

%
% General loop for the "matrix" version.
%
% Exchange is a map containing the different exchange rates
%    [From,To]=Rate
%
arbitrage_loop4(Exchange) =>

  All = [From : [From,_] in Exchange.keys()].remove_dups(), 
  MaxProfit = 0,
  MaxArb = [],
  foreach(Len in 2..All.length, Start in All)
     Chains=findall([Chain,Profit],profit4(Start,Len,All,Exchange,Chain,Profit)),
     foreach([Chain,Profit] in Chains) 
        % println([Chain,Profit]),
        if Profit = MaxProfit then
           println('newMax(tie)'=[Profit,Chain])
       end,
        if Profit > MaxProfit then
           println(newMax=[Profit,Chain]),
           MaxProfit := Profit,
           MaxArb := Chain
       end
     end
  end,
  println([maxArb=MaxArb,maxProfit=MaxProfit]),

  % We start with Init units (and don't care about broker costs etc.)
  Init = 1000,
  Currency = MaxArb.first().to_string().to_uppercase(),
  printf("Real profit where we start with %d %w: %d*%f-%d = %f %w\n", Init,Currency,Init,MaxProfit,Init,Init*MaxProfit-Init,Currency ),
  nl.


% C is the relative complement of A w.r.t. B (A-B)
difference(A,B) = C =>
    C = [X : X in A, not member(X,B)].