The Power of Prolog

Post by cousin_it » Tue, May 22, 2018, 11:57 AM UTC

kccqzy wrote: post #47

One of the coolest things I've seen is to use Prolog with CLP(FD) to solve the 7-11 problem. The problem basically says the sum of the prices of four items is $7.11, and the product is $7.11 too (no rounding); find the prices of these four items. This can be solved in two lines of code that gives the (unique) solution in a second. Not even my expensive Mathematica can do this! ?- use_module(library(clpfd)). true. ?-…

    p = 711
    q = 711000000
    for a in range(1, 1 + p // 4):
      if q % a == 0:
        for b in range(a, 1 + (p - a) // 3):
          if q % (a * b) == 0:
            for c in range(b, 1 + (p - a - b) // 2):
              d = p - a - b - c
              if a * b * c * d == q:
                print (a, b, c, d)

Post by anentropic » Tue, May 22, 2018, 12:39 PM UTC

triska wrote: post #17

pjmlp wrote: post #9

One of my favorite languages, pity that is has had even harder time than Lisp getting mainstream acceptance.

I once asked my Prolog instructor why this all takes so long. His reply: "How well are you prepared for the next ISO meeting?" At that point, I realized that if you prepare yourself in earnest for, say, the standardization process, or even to accomplish any concrete improvement in Prolog systems (such as better indexing, more advanced constraints, faster garbage collection etc.), then there is so much to do that ther…

Post by tom_mellior » Tue, May 22, 2018, 1:22 PM UTC

cousin_it wrote: post #121

kccqzy wrote: post #47

One of the coolest things I've seen is to use Prolog with CLP(FD) to solve the 7-11 problem. The problem basically says the sum of the prices of four items is $7.11, and the product is $7.11 too (no rounding); find the prices of these four items. This can be solved in two lines of code that gives the (unique) solution in a second. Not even my expensive Mathematica can do this! ?- use_module(library(clpfd)). true. ?-…

This Python code does a full search and finds the unique solution instantly: p = 711 q = 711000000 for a in range(1, 1 + p // 4): if q % a == 0: for b in range(a, 1 + (p - a) // 3): if q % (a * b) == 0: for c in range(b, 1 + (p - a - b) // 2): d = p - a - b - c if a * b * c * d == q: print (a, b, c, d) Does Prolog do the same pruning? Alternatively, it could be dumber (omit some of the pruning that my code does) or s…

    xkcd_ugly(A, B, C, D) :-
        P = 711,
        Q = 711000000,
        Max_A is 1 + P // 4,
        between(1, Max_A, A),
        Q mod A =:= 0,
        Max_B is 1 + (P - A) // 3,
        between(A, Max_B, B),
        Q mod (A * B) =:= 0,
        Max_C is 1 + (P - A - B) // 2,
        between(B, Max_C, C),
        D is P - A - B - C,
        A * B * C * D =:= Q.

    ?- time(xkcd_ugly(A, B, C, D)).
    % 383,992 inferences, 0.056 CPU in 0.056 seconds (100% CPU, 6825328 Lips)
    A = 120,
    B = 125,
    C = 150,
    D = 316 ;
    % 3,274 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 1229464 Lips)
    false.

Post by tom_mellior » Tue, May 22, 2018, 1:27 PM UTC

pjc50 wrote: post #115

Prolog: just say no. (To explain the joke, one of the main problems with Prolog is that solutions which cannot be unified just emit a "no" with no further explanation, making large Prolog setups hard to debug)

    Q: How many Prolog programmers does it take to change a lightbulb?
    A: no

Post by pwaivers » Tue, May 22, 2018, 1:48 PM UTC

andromeduck wrote: post #104

Prolog loses a lot of its magic when you realize it's just DFS the language.