4 ms·
Fun with Prolog: Priceonomics Puzzle
- pessimizer 13y agoIf 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?
- dangoldin 13y agoOP 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.
- sltkr 13y agoI 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 '.
- dangoldin 13y agoThanks 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.
- wwweston 13y ago> Do they even call them functions in Prolog? Doesn't seem appropriate. Nope. "Predicate" is the term you're looking for.
- octernion 13y agoI 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.
- dangoldin 13y agoGlad 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.
- curiousdannii 13y agoMy 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!
- fusiongyro 13y agoYou 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].
- darksaints 13y agoThe prolog solution is cool, but I would have solved it with a bellman ford algorithm.
- fixxer 13y agoAgreed, Bellman-Ford is a more efficient solution.
- omarish 13y agoYup, 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 agoI 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 agoI thought you would want the most negative cycle, which would be NP-hard to find.
- bumbledraven 13y agoBellman-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.
- deleted 13y ago[deleted]
- ruv 13y agoYou 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 .
- dangoldin 13y agoThanks 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.