4 ms·

The prolog solution is cool, but I would have solved it with a bellman ford algorithm.

fixxer 13y ago
Agreed, Bellman-Ford is a more efficient solution.
omarish 13y ago
Yup, Bellman Ford is the algorithm we had in mind for this puzzle. It's similar to Dijkstra's algorithm, but deals with negative costs as well. (I work at Priceonomics)
- darksaints 13y ago
  I really like what you guys do. It is a great concept, and it sounds like a really fun domain to work in. I hope I didn't ruin the puzzle by blurting this out.
- Mgccl 13y ago
  I thought you would want the most negative cycle, which would be NP-hard to find.
bumbledraven 13y ago
Bellman-Ford deals with graphs in which the distance along a path is the sum of the distance of its component edges, but in this case the most natural path distance the product of the edge weights. An instance of the problem corresponds to a directed graph that has one node for each currency and a directed edge between every pair of distinct currencies. The weight of the edge from currency A to currency B is the value in row A, column B of the exchange data table. For instance, the weight of the EUR→JPY edge is 131.7110. We define the value of a directed simple cycle in the graph to be the product of its edge weights. For instance, the value of the USD→EUR→BTC→USD cycle is 0.7779 * 0.01125* 115.65 = 1.01209651875. An arbitrage opportunity is then a directed simple cycle with value > 1. I was stuck here until I came across the clever trick of using the logarithm, as pointed out on http://stackoverflow.com/questions/2282427/interesting-problem-currency-arbitrage http://stackoverflow.com/questions/2282427/interesting-probl... To apply Bellman-Ford to this problem we use the negative of the base-10 logarithm of each edge instead and use the sum of these new edge weights rather than the product in calculating the value of a cycle. (Any base will do, provided we use the same base for every edge.) For instance, the weight of the EUR→JPY edge is now considered to be -log(131.7110) =~ -2.1196, and thus the weight of the USD→EUR→BTC→USD cycle is now -log(0.7779) + -log(0.01125) + -log(115.65) =~ -0.00522. An arbitrage opportunity is then a directed simple cycle with negative weight, which can easily be detected by Bellman-Ford.
- Mgccl 13y ago
  Let's put some algebra/order into this... Bellman-Ford works for any totally ordered group (G,+), such that a+b<=a+c if b<=c. What logarithm does is just a order preserving homomorphism from (R,*) to (R,+).
  - deleted 13y ago
    [deleted]
dangoldin 13y ago
Yea - I wasn't going for optimal but just wanted to have some fun and decided to take a stab at using Prolog.

Agreed, Bellman-Ford is a more efficient solution.

Yup, Bellman Ford is the algorithm we had in mind for this puzzle. It's similar to Dijkstra's algorithm, but deals with negative costs as well. (I work at Priceonomics)

darksaints 13y ago
I really like what you guys do. It is a great concept, and it sounds like a really fun domain to work in. I hope I didn't ruin the puzzle by blurting this out.
Mgccl 13y ago
I thought you would want the most negative cycle, which would be NP-hard to find.

bumbledraven 13y ago

Bellman-Ford deals with graphs in which the distance along a path is the sum of the distance of its component edges, but in this case the most natural path distance the product of the edge weights. An instance of the problem corresponds to a directed graph that has one node for each currency and a directed edge between every pair of distinct currencies. The weight of the edge from currency A to currency B is the value in row A, column B of the exchange data table. For instance, the weight of the EUR→JPY edge is 131.7110. We define the value of a directed simple cycle in the graph to be the product of its edge weights. For instance, the value of the USD→EUR→BTC→USD cycle is 0.7779 * 0.01125* 115.65 = 1.01209651875. An arbitrage opportunity is then a directed simple cycle with value > 1. I was stuck here until I came across the clever trick of using the logarithm, as pointed out on http://stackoverflow.com/questions/2282427/interesting-problem-currency-arbitrage http://stackoverflow.com/questions/2282427/interesting-probl... To apply Bellman-Ford to this problem we use the negative of the base-10 logarithm of each edge instead and use the sum of these new edge weights rather than the product in calculating the value of a cycle. (Any base will do, provided we use the same base for every edge.) For instance, the weight of the EUR→JPY edge is now considered to be -log(131.7110) =~ -2.1196, and thus the weight of the USD→EUR→BTC→USD cycle is now -log(0.7779) + -log(0.01125) + -log(115.65) =~ -0.00522. An arbitrage opportunity is then a directed simple cycle with negative weight, which can easily be detected by Bellman-Ford.

Mgccl 13y ago
Let's put some algebra/order into this... Bellman-Ford works for any totally ordered group (G,+), such that a+b<=a+c if b<=c. What logarithm does is just a order preserving homomorphism from (R,*) to (R,+).
- deleted 13y ago
  [deleted]

dangoldin 13y ago

Yea - I wasn't going for optimal but just wanted to have some fun and decided to take a stab at using Prolog.