CODEWITHSUNDEEP
prologsat
Rúben Dias
Rúben Dias

Reputation: 469

Lion and Unicorn with Prolog SAT Solver

Would a Prolog SAT solver have an advantage in solving this riddle:

When Alice entered the forest of forgetfulness, she did not forget everything, only certain things. She often forgot her name, and the most likely thing for her to forget was the day of the week. Now, the lion and the unicorn were frequent visitors to this forest. These two are strange creatures. The lion lies on Mondays, Tuesdays, and Wednesdays and tells the truth on the other days of the week. The unicorn, on the other hand, lies on Thursdays, Fridays, and Saturdays, but tells the truth on the other days of the week.

One day Alice met the lion and the unicorn resting under a tree. They made the following statements:

Lion: Yesterday was one of my lying days.
Unicorn: Yesterday was one of my lying days.

From these statements, Alice, who was a bright girl, was able to deduce the day of the week. What was it?

Performance advantage over a solution like here (Free Access):

The lion and the unicorn met PROLOG
Bruce Ramsey - 1986
https://dl.acm.org/doi/10.1145/382278.382395

Upvotes: 0

Views: 176

Answers (2)

brebs
brebs

Reputation: 4456

Preventing a separate lookup for yesterday_today:

lying_day(lion, mon, tue).
lying_day(lion, tue, wed).
lying_day(lion, wed, thu).

lying_day(unicorn, thu, fri).
lying_day(unicorn, fri, sat).
lying_day(unicorn, sat, sun).

lion_unicorn(Today) :-
    animal_consistent(lion, Yesterday, Today),
    animal_consistent(unicorn, Yesterday, Today).

animal_consistent(Animal, Yesterday, Today) :-
    lying_day(Animal, Yesterday, Today),
    % Telling truth
    \+ lying_day(Animal, Today, _).
animal_consistent(Animal, Yesterday, Today) :-
    % Lying
    lying_day(Animal, Today, _),
    \+ lying_day(Animal, Yesterday, Today).

Results in swi-prolog:

?- time(lion_unicorn(D)).
% 11 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 1104529 Lips)
D = thu ;
% 13 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 1176364 Lips)
false.

?- time((between(1, 1000000, _), lion_unicorn(_), fail; true)).
% 21,000,001 inferences, 1.183 CPU in 1.184 seconds (100% CPU, 17755003 Lips)

Upvotes: 1

brebs
brebs

Reputation: 4456

Preventing execution of yesterday_today twice:

lying_day(lion, mon).
lying_day(lion, tue).
lying_day(lion, wed).

lying_day(unicorn, thu).
lying_day(unicorn, fri).
lying_day(unicorn, sat).

yesterday_today(mon, tue).
yesterday_today(tue, wed).
yesterday_today(wed, thu).
yesterday_today(thu, fri).
yesterday_today(fri, sat).
yesterday_today(sat, sun).
yesterday_today(sun, mon).

lion_unicorn(Today) :-
    animal_consistent_day(lion, Yesterday, Today),
    % Don't call yesterday_today again, for performance
    animal_consistent(unicorn, Yesterday, Today).

animal_consistent_day(Animal, Yesterday, Today) :-
    % Delay yesterday_today, for performance
    lying_day(Animal, Yesterday),
    yesterday_today(Yesterday, Today),
    % Telling truth
    \+ lying_day(Animal, Today).
animal_consistent_day(Animal, Yesterday, Today) :-
    % Lying
    lying_day(Animal, Today),
    yesterday_today(Yesterday, Today),
    \+ lying_day(Animal, Yesterday).

animal_consistent(Animal, Yesterday, Today) :-
    lying_day(Animal, Yesterday),
    % Telling truth
    \+ lying_day(Animal, Today).
animal_consistent(Animal, Yesterday, Today) :-
    % Lying
    lying_day(Animal, Today),
    \+ lying_day(Animal, Yesterday).

Results in swi-prolog:

?- time(lion_unicorn(D)).
% 14 inferences, 0.000 CPU in 0.000 seconds (71% CPU, 1219406 Lips)
D = thu ;
% 16 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 1453224 Lips)
false.

?- time((between(1, 1000000, _), lion_unicorn(_), fail; true)).
% 27,000,001 inferences, 1.314 CPU in 1.316 seconds (100% CPU, 20540412 Lips)

Upvotes: 1

Related Questions