{"id":1533,"date":"2013-06-07T20:50:07","date_gmt":"2013-06-08T03:50:07","guid":{"rendered":"http:\/\/balafon.net\/?p=1533"},"modified":"2013-06-07T20:50:07","modified_gmt":"2013-06-08T03:50:07","slug":"fun-with-prolog","status":"publish","type":"post","link":"https:\/\/balafon.net\/?p=1533","title":{"rendered":"Fun with Prolog"},"content":{"rendered":"

Saw a post<\/a> about currency arbitrage<\/a> in Prolog on Hacker News<\/a>, and wrote a more general solution<\/a>:<\/p>\n

\r\n:- use_module(library(lists)).\r\n:- use_module(library('http\/http_client')).\r\n:- use_module(library('http\/json')).\r\n\r\n%! find_chains(+MaxLength) is semidet\r\n%\r\n% Prints possible profitable conversion chains.\r\n\r\nfind_chains(MaxLength) :-\r\n  http_get('http:\/\/fx.priceonomics.com\/v1\/rates\/', Json, []),\r\n  atom_json_term(Json, json(Prices), []), % convert the json atom to a prolog term and extract the list of prices\r\n  abolish(price\/3),                       % clear any old price facts from the database\r\n  assert_prices(Prices),                  % update the database with current prices\r\n\t\r\n  % now get the set of all solutions for the predicate \r\n  % build_chain\/3, and build a list of the results\r\n  setof(chain(Symbols, Profit), build_chain(MaxLength, Symbols, Profit), Chains),\r\n\t\r\n  % print the results\r\n  write(Chains).\r\n\r\n%! assert_prices(+List) is det\r\n% \r\n% Adds the list of prices to the dynamic database.\r\n%\r\nassert_prices([]).\r\nassert_prices([SymbolPair = Price | Rest]) :-\r\n  atomic_list_concat([From, To], '_', SymbolPair),\r\n  atom_number(Price, Num),\r\n  assertz(price(From, To, Num)),\r\n  assert_prices(Rest).\r\n\r\n%! build_chain(+MaxLength, -Symbols, -Profit) is nondet\r\n%\r\n% Finds a profitable chain\r\n\r\nbuild_chain(MaxLength, Symbols, Profit) :-\r\n  price(Dest, Next, _), Dest \\= Next, % pick a starting symbol (ignore repeats), with backtracking\r\n  build_chain(MaxLength, Dest, [Dest], 1.0, Symbols, Profit).\r\n\r\n%! build_chain(+Count, Dest, SymbolsIn, ProfitIn, SymbolsOut, ProfitOut)\r\n%\r\n% Finds a possible next link in the chain, checks to see if it's a loop, otherwise recurses.\r\n\r\nbuild_chain(0, _, _, _, _, _) :- !, fail.    % stop backtracking when we hit our maximum length\r\n\r\nbuild_chain(Count, Dest, SymbolsIn, ProfitIn, SymbolsOut, ProfitOut) :-\r\n  price(A, B, P),                            % find a price record (backtracking over all of them)\r\n  append(_, [A], SymbolsIn),                 % make sure the chain connects\r\n  Profit is ProfitIn * P,                    % calculate our profit\r\n\t\r\n  (B = Dest                                  % do we have a loop?\r\n    ->  Profit > 1.0,                        % is it profitable?\r\n        append(SymbolsIn, [B], SymbolsOut),  % if so, then we're done\r\n        ProfitOut = Profit\r\n\t\t\r\n    ;   \\+ member(B, SymbolsIn),             % if not a loop, make sure we don't repeat interior symbols\r\n        append(SymbolsIn, [B], SymbolsNext), % add B to a temp list\r\n        NextCount is Count - 1,              % and recurse, decrementing our counter\r\n        build_chain(NextCount, Dest, SymbolsNext, Profit, SymbolsOut, ProfitOut)).\r\n\t\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Saw a post about currency arbitrage in Prolog on Hacker News, and wrote a more general solution: :- use_module(library(lists)). :- use_module(library(‘http\/http_client’)). :- use_module(library(‘http\/json’)). %! find_chains(+MaxLength) is semidet % % Prints possible profitable conversion chains. find_chains(MaxLength) :- http_get(‘http:\/\/fx.priceonomics.com\/v1\/rates\/’, Json, []), atom_json_term(Json, json(Prices), []), % convert the json atom to a prolog term and extract the list … Continue reading “Fun with Prolog”<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,3],"tags":[175,174],"class_list":["post-1533","post","type-post","status-publish","format-standard","hentry","category-computing","category-journal","tag-bitcoin","tag-prolog"],"_links":{"self":[{"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/posts\/1533","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/balafon.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1533"}],"version-history":[{"count":7,"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/posts\/1533\/revisions"}],"predecessor-version":[{"id":1540,"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/posts\/1533\/revisions\/1540"}],"wp:attachment":[{"href":"https:\/\/balafon.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1533"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/balafon.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1533"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/balafon.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1533"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}