Hacker News new | past | comments | ask | show | jobs | submit login

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



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-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.


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,+).


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)


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.


I thought you would want the most negative cycle, which would be NP-hard to find.


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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: