Hacker News Reader

Comment by _a_a_a_ | Hacker News Reader

"It is known that salesmen always tell the truth and engi- neers always tell lies. G and E are salesmen. C states that D is an engineer. A declares that B affirms that C asserts that D says that E insists that F denies that G is a sales- man. If A is an engineer, how many engineers are there?"

Now that is a curious puzzle in the sense that I can't think how to express it in Prolog. You'd need to assert the truth of assertions which implies quantifying over assertions, and Prolog doesn't allow that. I'm sure I'm making this much more complex than it need be, there has to be a much more straightforward way, any ideas please?

View on HN

The article suggests using Boolean logic, so let's apply it: One way to solve this is to introduce a Boolean variable for each of A,...,G, and to use 1 to denote that a statement is true, and also to denote that the corresponding person tells the truth. It then remains to relate the truth of each statement to the truthfulness of the person making the statement.

In Prolog, we can express these relations with CLP(B), constraint logic programming over Boolean variables:

    ?- use_module(library(clpb)).
       true.
    ?- sat(G),
       sat(E),
       sat(C =:= ~D),
       sat(A =:= (B =:= (C =:= (D =:= (E =:= (F =:= ~G)))))),
       sat(~A),
       labeling([A,B,C,D,E,F,G]).

Yielding 4 solutions that satisfy all constraints:

       G = 1, E = 1, C = 0, D = 1, A = 0, B = 0, F = 1
    ;  G = 1, E = 1, C = 0, D = 1, A = 0, B = 1, F = 0
    ;  G = 1, E = 1, C = 1, D = 0, A = 0, B = 0, F = 1
    ;  G = 1, E = 1, C = 1, D = 0, A = 0, B = 1, F = 0.

From this, it is clear that there are 3 engineers, in all possible situations consistent with the description.

If we omit the labeling/1 goal which enumerates all solutions, then we get a symbolic representation of all remaining constraints:

    G = 1, E = 1, A = 0, clpb:sat(C=:=D#B#F), clpb:sat(C=\=D).

From this, it is clear that there are at least 2 engineers in every solution: A (as stated in the description of the puzzle), and either C or D (but not both).

Tested with Scryer Prolog.

You're a treasure sir!

The thing I find especially interesting about these sorts of puzzles is the translation from the word problem to the logical formalism. It seems like a separate domain from solving the problem itself.

With Prolog, we can often very naturally map such puzzles to programs, or at least to declarative descriptions that can be easily interpreted by Prolog programs.

For instance, in this concrete case, with a suitable operator definition for the operator says, we can write:

    :- op(800, xfy, says).

    solution([A,B,C,D,E,F,G]) :-
            G = salesman,
            E = salesman,
            C says D = engineer,
            A = engineer,
            A says B says C says D says E says F says G = engineer.

It is then left to interpret the statements, which we can do for example with:

    :- use_module(library(dif)).

    engineer says Stmt :- false(Stmt).
    salesman says Stmt :- true(Stmt).

    false(A = B) :- dif(A, B).
    false(engineer says Stmt) :- true(Stmt).
    false(salesman says Stmt) :- false(Stmt).

    true(A = A).
    true(engineer says Stmt) :- false(Stmt).
    true(salesman says Stmt) :- true(Stmt).

Yielding:

    ?- solution(S).
       S = [engineer,engineer,engineer,salesman,salesman,salesman,salesman]
    ;  S = [engineer,salesman,engineer,salesman,salesman,engineer,salesman]
    ;  S = [engineer,engineer,salesman,engineer,salesman,salesman,salesman]
    ;  S = [engineer,salesman,salesman,engineer,salesman,engineer,salesman]
    ;  false.

That is most excellent, thank you

Reply on news.ycombinator.com