Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
A prolog program to solve the problem presented at
:- 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('', Json, []),
atom_json_term(Json, json(Prices), []), % convert the json atom to a prolog term and extract the list of prices
abolish(price/3), % clear any old price facts from the database
assert_prices(Prices), % update the database with current prices
% now get the set of all solutions for the predicate
% build_chain/3, and build a list of the results
setof(chain(Symbols, Profit), build_chain(MaxLength, Symbols, Profit), Chains),
% print the results
%! assert_prices(+List) is det
% Adds the list of prices to the dynamic database.
assert_prices([SymbolPair = Price | Rest]) :-
atomic_list_concat([From, To], '_', SymbolPair),
atom_number(Price, Num),
assertz(price(From, To, Num)),
%! build_chain(+MaxLength, -Symbols, -Profit) is nondet
% Finds a profitable chain
build_chain(MaxLength, Symbols, Profit) :-
price(Dest, Next, _), Dest \= Next, % pick a starting symbol (ignore repeats), with backtracking
build_chain(MaxLength, Dest, [Dest], 1.0, Symbols, Profit).
%! build_chain(+Count, Dest, SymbolsIn, ProfitIn, SymbolsOut, ProfitOut)
% Finds a possible next link in the chain, checks to see if it's a loop, otherwise recurses.
build_chain(0, _, _, _, _, _) :- !, fail. % stop backtracking when we hit our maximum length
build_chain(Count, Dest, SymbolsIn, ProfitIn, SymbolsOut, ProfitOut) :-
price(A, B, P), % find a price record (backtracking over all of them)
append(_, [A], SymbolsIn), % make sure the chain connects
Profit is ProfitIn * P, % calculate our profit
(B = Dest % do we have a loop?
-> Profit > 1.0, % is it profitable?
append(SymbolsIn, [B], SymbolsOut), % if so, then we're done
ProfitOut = Profit
; \+ member(B, SymbolsIn), % if not a loop, make sure we don't repeat interior symbols
append(SymbolsIn, [B], SymbolsNext), % add B to a temp list
NextCount is Count - 1, % and recurse, decrementing our counter
build_chain(NextCount, Dest, SymbolsNext, Profit, SymbolsOut, ProfitOut)).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment