Fun with Prolog: Priceonomics Puzzle | Hacker News Reader

Fun with Prolog: Priceonomics Puzzle

dangoldin.com

71 pointsdangoldin19 comments

I really enjoyed reading this - thanks for posting!

I had totally forgotten about Prolog, and I love how it essentially forces you to approach problems in an absolutely new manner (conceptually) than more traditional imperative programming.

Glad you enjoyed. It was pretty frustrating getting started when you know how easy some of the things are to do in other languages but once I got into it it felt great. You definitely start thinking about them at a different level although parts of it felt pretty functional/mathematical to me.

The other thing I realize now is how much easier it is to get started now with StackOverflow and Google being available. I remember having to go through tutorials and demos that came with the software or read books to learn new languages. Now there are so many resources out there.

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.

If it was Erlang, the reason that Prolog would be considered a variable would be the initial caps. is and sweet would be atoms (which are like names or labels) because of the lack of quotes and lack of initial caps. Prolog may convert atoms to strings when they're used in a string function (or that particular string function may convert atoms to strings.) Do they even call them functions in Prolog? Doesn't seem appropriate.

edit: also, single quotes in Erlang are a way of creating an initial cap atom, or an atom with special characters in it. Double quotes are used for strings. Might be the same.

edit: just checked, it's the same. And compound term?

OP here - someone left a comment on the blog who's clearly more knowledgeable than I am. I'm copying it here:

    The quotes are necessary if an atom starts with something
    other than a lower-case character. Any unquoted token
    that starts with an upper-case letter is a variable.

    As for atomic_list_concat, it's an optimized library
    function that requires the separator. It's certainly 
    possible to write an equivalent that is completely 
    flexible.

I think the predicate you wanted to demonstrate is called append/3, which works on list (while concat applies to atoms).

In Prolog, 'foo' constructs an atom, which is equivalent to foo without any quotes (but the quotes are useful to construct atoms with spaces, with digits, starting with a capital letter, etc.)

However, if you want to manipulate atoms as text, you typically want to use strings instead, which are literally lists of character codes in Prolog, and can be entered as double quotes. For example, "ABC" = [65,66,67]. To convert between strings and atoms dynamically, use atom_chars/2.

For example:

  ?- append("Prolog is", " awesome", Z), atom_chars(A,Z).
  Z = [80, 114, 111, 108, 111, 103, 32, 105, 115|...],
  A = 'Prolog is awesome'.

  ?- append("Prolog is", Y, "Prolog is awesome"), atom_chars(A,Y).
  Y = [32, 97, 119, 101, 115, 111, 109, 101],
  A = ' awesome'.

  ?- append(X, "is awesome", "Prolog is awesome"), atom_chars(A,X).
  X = [80, 114, 111, 108, 111, 103, 32],
  A = 'Prolog '.

Thanks for the explanation. It's such a neat idea that inputs and outputs can be interchangeable. Opens up approaches that are very different than the standard ones. The append predicate is definitely a better example so thanks for sharing.

> Do they even call them functions in Prolog? Doesn't seem appropriate.

Nope. "Predicate" is the term you're looking for.

You mention doing it for variable length chains, It requires hardly more effort than hard coding the length, something like

    find_match(X, P) :-
        append([usd | _], [usd], X),
        profit(X, P),
        P > 1.

    profit([A, B], P) :- exchange(A, B, P).
    profit([A, B | T], P) :-
        exchange(A, B, P1),
        profit([B | T], P2),
        P is P1 * P2.
 
    # 1 ?- find_match(X, P).
    # X = [usd, jpy, usd],
    # P = 1.0040982 ;
    # X = [usd, eur, jpy, usd],
    # P = 1.0040882716200001 ;
    # X = [usd, eur, btc, usd],
    # P = 1.01209651875 ;
    # X = [usd, btc, jpy, usd],
    # P = 1.0025512896 ;
    # X = [usd, eur, usd, jpy, usd],
    # P = 1.003776175666278 .

Thanks for sharing this. The way these are defined reminds me of the way I'd be defining methods in SML - a base case and then a recursive one to deal with the tail.

My favourite part of Prolog is that if you ask it if something is in a list it will decide to add it to the list so that it can return true!

You must be referring to this:

    ?- member(what, X).
    X = [what|_G2122] ;
    X = [_G2121, what|_G2125] ...

If what you have isn't a variable, it is totally reasonable:

    ?- member(what, []).
    false.

This is because, lacking other evidence about what X might be, it can't distinguish between making an assertion about a new quantity ("there is a list X which 'what' is a member of") and a query ("is 'what' in the list?"). Making an assertion like that, however, is pretty normal. It's a perfectly reasonable declarative way to understand this behavior, it's just that this thinking is unusual, so it's weird.

Maybe this little demonstration will give the flavor of why you might want this:

    ?- length(X, 3), member(what, X).
    X = [what, _G942, _G945] ;
    X = [_G939, what, _G945] ;
    X = [_G939, _G942, what].

Reply on news.ycombinator.com