Please solve this with logic:

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?

I got the puzzle from a discussion here,
which was about Prolog versus Theorem Proving:

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

This gives immediately the following database:

yesterday(monday , sunday ).
yesterday(tuesday , monday ).
yesterday(wednesday, tuesday ).
yesterday(thursday , wednesday).
yesterday(friday , thursday ).
yesterday(saturday , friday ).
yesterday(sunday , saturday ).

lies(lion, monday ).
lies(lion, tuesday ).
lies(lion, wednesday).

lies(unicorn, thursday).
lies(unicorn, friday ).
lies(unicorn, saturday).

Now what?

Picking up an idea by @jamesnvc , abstracting a pattern
behind lying_day_lie_or_nonlying_day_truth/3 into something
with more meta calls:

contrary(S, T) :- S, \+ T.
contrary(S, T) :- \+ S, T.

solve(D) :- yesterday(D, Y),
contrary(lies(lion, D), lies(lion, Y)),
contrary(lies(unicorn, D), lies(unicorn, Y)).

Here some benchmark:

/* SWI-Prolog 9.1.17 */
?- time((between(1,1000000,_), solve(_), fail; true)).
% 45,999,999 inferences, 2.719 CPU in 2.712 seconds (100% CPU, 16919540 Lips)
true.

/* Dogelog Player 1.1.3, Java */
?- time((between(1,1000000,_), solve(_), fail; true)).
% Zeit 9282 ms, GC 0 ms, Lips 10019403, Uhr 06.11.2023 16:34
true.

/* GNU Prolog 1.5.0 */
?- between(1,1000000,_), solve(_), fail; true.
(10782 ms) yes

Quite amazing the speed of SWI-Prolog, here I can only beat GNU Prolog
with my new Dogelog Player for Java. Mostlikely an argument in favor of inlining
negation as failure somehow, as SWI-Prolog does. Only lets do it correctly!

Mild Shock schrieb am Montag, 6. November 2023 um 16:43:13 UTC+1:
> I got the puzzle from a discussion here,
> which was about Prolog versus Theorem Proving:
>
> The lion and the unicorn met PROLOG
> Bruce D. Ramsey, 1986 - Free Access
> https://dl.acm.org/doi/10.1145/382278.382395
>
> This gives immediately the following database:
>
> yesterday(monday , sunday ).
> yesterday(tuesday , monday ).
> yesterday(wednesday, tuesday ).
> yesterday(thursday , wednesday).
> yesterday(friday , thursday ).
> yesterday(saturday , friday ).
> yesterday(sunday , saturday ).
>
> lies(lion, monday ).
> lies(lion, tuesday ).
> lies(lion, wednesday).
>
> lies(unicorn, thursday).
> lies(unicorn, friday ).
> lies(unicorn, saturday).
>
> Now what?

Its also a test case where my sys_trans_allowed/1 is totally useless. But
I guess this is a problem of my sys_trans_allowed/1, maybe we can make an
exception for \+ A where A is a variable and arrive at something useful?

If A is a variable, and if we would replace it by (A->fail; true) this would
be compiled with call(A), and thus give a correct translation of negation as
failure again. Its a similar special case like call/1 has the special case that

at runtime call(A) with A variable throws an exception to avoid call/1
wrapping at infinitum and that the Prolog interpreter runs into nirvana.
So the revised sys_trans_allowed/1 would read as follows:

/* Version 2.0 */
sys_trans_allowed(V) :- var(V), !.
sys_trans_allowed(A) :- sys_trans_allowed2(A).

sys_trans_allowed2(V) :- var(V), !, fail.
sys_trans_allowed2((A,B)) :- sys_trans_allowed2(A), sys_trans_allowed2(B).
sys_trans_allowed2((A;B)) :- sys_trans_allowed2(A), sys_trans_allowed2(B).
sys_trans_allowed2((A->B)) :- sys_trans_allowed2(A), sys_trans_allowed2(B).
sys_trans_allowed2(A) :- callable(A).

But I guess a little more is needed. Namely make (A->fail; true) cheap.

Mild Shock schrieb am Montag, 6. November 2023 um 16:47:40 UTC+1:
> Picking up an idea by @jamesnvc , abstracting a pattern
> behind lying_day_lie_or_nonlying_day_truth/3 into something
> with more meta calls:
>
> contrary(S, T) :- S, \+ T.
> contrary(S, T) :- \+ S, T.
>
> solve(D) :- yesterday(D, Y),
> contrary(lies(lion, D), lies(lion, Y)),
> contrary(lies(unicorn, D), lies(unicorn, Y)).
>
> Here some benchmark:
>
> /* SWI-Prolog 9.1.17 */
> ?- time((between(1,1000000,_), solve(_), fail; true)).
> % 45,999,999 inferences, 2.719 CPU in 2.712 seconds (100% CPU, 16919540 Lips)
> true.
>
> /* Dogelog Player 1.1.3, Java */
> ?- time((between(1,1000000,_), solve(_), fail; true)).
> % Zeit 9282 ms, GC 0 ms, Lips 10019403, Uhr 06.11.2023 16:34
> true.
>
> /* GNU Prolog 1.5.0 */
> ?- between(1,1000000,_), solve(_), fail; true.
> (10782 ms) yes
>
> Quite amazing the speed of SWI-Prolog, here I can only beat GNU Prolog
> with my new Dogelog Player for Java. Mostlikely an argument in favor of inlining
> negation as failure somehow, as SWI-Prolog does. Only lets do it correctly!
> Mild Shock schrieb am Montag, 6. November 2023 um 16:43:13 UTC+1:
> > I got the puzzle from a discussion here,
> > which was about Prolog versus Theorem Proving:
> >
> > The lion and the unicorn met PROLOG
> > Bruce D. Ramsey, 1986 - Free Access
> > https://dl.acm.org/doi/10.1145/382278.382395
> >
> > This gives immediately the following database:
> >
> > yesterday(monday , sunday ).
> > yesterday(tuesday , monday ).
> > yesterday(wednesday, tuesday ).
> > yesterday(thursday , wednesday).
> > yesterday(friday , thursday ).
> > yesterday(saturday , friday ).
> > yesterday(sunday , saturday ).
> >
> > lies(lion, monday ).
> > lies(lion, tuesday ).
> > lies(lion, wednesday).
> >
> > lies(unicorn, thursday).
> > lies(unicorn, friday ).
> > lies(unicorn, saturday).
> >
> > Now what?

Ok I was comparing apples with oranges when I looked
at SWI-Prolog and other Prolog systems. Since SWI-Prolog
creates a multi-argument index, which explains the speed:

?- jiti_list(lies).
Predicate Indexed Buckets Speedup Flags
============================================================================
user:lies/2 2 8 6.0
true.

Can I manually switch off this index for a fairer comparison?
Whats even the logic behind choosing this index. Thats
a quite an amazing choice sind the call of lies/2 is ground.

Mild Shock schrieb am Montag, 6. November 2023 um 17:03:16 UTC+1:
> Its also a test case where my sys_trans_allowed/1 is totally useless. But
> I guess this is a problem of my sys_trans_allowed/1, maybe we can make an
> exception for \+ A where A is a variable and arrive at something useful?
>
> If A is a variable, and if we would replace it by (A->fail; true) this would
> be compiled with call(A), and thus give a correct translation of negation as
> failure again. Its a similar special case like call/1 has the special case that
>
> at runtime call(A) with A variable throws an exception to avoid call/1
> wrapping at infinitum and that the Prolog interpreter runs into nirvana.
> So the revised sys_trans_allowed/1 would read as follows:
>
> /* Version 2.0 */
> sys_trans_allowed(V) :- var(V), !.
> sys_trans_allowed(A) :- sys_trans_allowed2(A).
>
> sys_trans_allowed2(V) :- var(V), !, fail.
> sys_trans_allowed2((A,B)) :- sys_trans_allowed2(A), sys_trans_allowed2(B).
> sys_trans_allowed2((A;B)) :- sys_trans_allowed2(A), sys_trans_allowed2(B).
> sys_trans_allowed2((A->B)) :- sys_trans_allowed2(A), sys_trans_allowed2(B).
> sys_trans_allowed2(A) :- callable(A).
>
> But I guess a little more is needed. Namely make (A->fail; true) cheap.
> Mild Shock schrieb am Montag, 6. November 2023 um 16:47:40 UTC+1:
> > Picking up an idea by @jamesnvc , abstracting a pattern
> > behind lying_day_lie_or_nonlying_day_truth/3 into something
> > with more meta calls:
> >
> > contrary(S, T) :- S, \+ T.
> > contrary(S, T) :- \+ S, T.
> >
> > solve(D) :- yesterday(D, Y),
> > contrary(lies(lion, D), lies(lion, Y)),
> > contrary(lies(unicorn, D), lies(unicorn, Y)).
> >
> > Here some benchmark:
> >
> > /* SWI-Prolog 9.1.17 */
> > ?- time((between(1,1000000,_), solve(_), fail; true)).
> > % 45,999,999 inferences, 2.719 CPU in 2.712 seconds (100% CPU, 16919540 Lips)
> > true.
> >
> > /* Dogelog Player 1.1.3, Java */
> > ?- time((between(1,1000000,_), solve(_), fail; true)).
> > % Zeit 9282 ms, GC 0 ms, Lips 10019403, Uhr 06.11.2023 16:34
> > true.
> >
> > /* GNU Prolog 1.5.0 */
> > ?- between(1,1000000,_), solve(_), fail; true.
> > (10782 ms) yes
> >
> > Quite amazing the speed of SWI-Prolog, here I can only beat GNU Prolog
> > with my new Dogelog Player for Java. Mostlikely an argument in favor of inlining
> > negation as failure somehow, as SWI-Prolog does. Only lets do it correctly!
> > Mild Shock schrieb am Montag, 6. November 2023 um 16:43:13 UTC+1:
> > > I got the puzzle from a discussion here,
> > > which was about Prolog versus Theorem Proving:
> > >
> > > The lion and the unicorn met PROLOG
> > > Bruce D. Ramsey, 1986 - Free Access
> > > https://dl.acm.org/doi/10.1145/382278.382395
> > >
> > > This gives immediately the following database:
> > >
> > > yesterday(monday , sunday ).
> > > yesterday(tuesday , monday ).
> > > yesterday(wednesday, tuesday ).
> > > yesterday(thursday , wednesday).
> > > yesterday(friday , thursday ).
> > > yesterday(saturday , friday ).
> > > yesterday(sunday , saturday ).
> > >
> > > lies(lion, monday ).
> > > lies(lion, tuesday ).
> > > lies(lion, wednesday).
> > >
> > > lies(unicorn, thursday).
> > > lies(unicorn, friday ).
> > > lies(unicorn, saturday).
> > >
> > > Now what?

What the heck, one can even write ultrafast
parsers with SAT (some bit encoding)?

> Long live SMT. Long live meta-programming
This article describes why and how I wrote absolut; a Rust
crate for automating a common pattern of constructing
SIMD byte-wise lookup tables. I learned about this technique
while studying the Parsing Gigabytes of JSON per Second
paper by Geoff Langdale & Daniel Lemire.
https://fuzzypixelz.com/blog/absolut/

Mild Shock schrieb am Samstag, 11. November 2023 um 19:40:21 UTC+1:
> Could ChatGPT, the automatic programming Robot,
> help develop a solution with a SAT solver for XOR in mind?
>
> My idea currently, use 3 variables X,Y,Z for weekday:
>
> X,Y,Z weekday
> 0,0,0 monday
> 0,0,1 tuesday
> 0,1,0 wednesday
> 0,1,1 thursday
> 1,0,0 friday
> 1,0,1 saturday
> 1,1,0 sunday
>
> Or maybe somebody, a human, did it already this way.
> Mild Shock schrieb am Samstag, 11. November 2023 um 18:33:50 UTC+1:
> > Just for the fun of it, also benchmarking,
> > was expecting same behaviour as contrary2:
> >
> > contrary5(S, T) :- \+ (forall(S,T), forall(T,S)).¨
> >
> > Not so good because forall/2 isn’t handled as a “control construct”,
> > whereas (\+)/1 is handled as a “control construct” and inlined.
> > Maybe this is the reason:
> >
> > /* contrary5 */
> > ?- time((between(1,1000000,_), solve(_), fail; true)).
> > % 65,999,999 inferences, 2.812 CPU in 2.813 seconds (100% CPU, 23466666 Lips)
> > true.
> >
> > So contrary is the XOR, i.e. ~(A ↔ B) == ~((A → B) & (B → A)).
> > What can a constraint programming system do to the Lion and Unicorn
> > example. Are there not special SAT solvers who are good in XOR?

Ok, I was using a SAT solver in a little unorthodox way.
Used it as a compiler for a formula, so that I got:

yesterday(0,0,0,1,1,0).
yesterday(0,0,1,0,0,0).
yesterday(0,1,0,0,0,1).
yesterday(0,1,1,0,1,0).
yesterday(1,0,0,0,1,1).
yesterday(1,0,1,1,0,0).
yesterday(1,1,0,1,0,1).

two_liars(T1,T2,T3,Y1,Y2,Y3) :-
T1=\=Y1,
T1=:=(T1/\Y2) xor (T1/\Y3) xor (Y2/\Y3),
Y1=:=(T2/\T3) xor (T2/\Y1) xor (T3/\Y1),
T1=\=(T1/\T2) xor (T1/\T3) xor T2 xor (T2/\T3) xor T3,
Y1=\=(Y1/\Y2) xor (Y1/\Y3) xor Y2 xor (Y2/\Y3) xor Y3.

solve_for(T1,T2,T3) :-
yesterday(T1,T2,T3,Y1,Y2,Y3),
two_liars(T1,T2,T3,Y1,Y2,Y3).

Works fine:

/* SWI-Prolog 9.1.17, optimise=false */
?- time(solve_for(T1,T2,T3)).
% 16 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
T1 = 1,
T2 = T3, T3 = 0 ;
% 10 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
false.

But I guess I always miss launching SWI-Prolog with optimise=true,
and the version I am using has default optimise=false.
Because I get these varying results:

/* SWI-Prolog 9.1.17, optimise=false */
?- time((between(1, 1000000, _), solve_for(T1,T2,T3), fail; true)).
% 22,999,999 inferences, 2.016 CPU in 2.016 seconds
(100% CPU, 11410852 Lips)

/* SWI-Prolog 9.1.17, optimise=true */
?- time((between(1, 1000000, _), solve_for(T1,T2,T3), fail; true)).
% 9,999,999 inferences, 1.203 CPU in 1.199 seconds
(100% CPU, 8311687 Lips)
Whereas in Dogelog Player I have now practically always
optimise=true, which then gives me the following:

/* Dogelog Player 1.1.4, JDK 8 */
?- time((between(1, 1000000, _), solve_for(T1,T2,T3), fail; true)).
% Zeit 1892 ms, GC 0 ms, Lips 13213582, Uhr 13.11.2023 23:54

Mild Shock schrieb am Dienstag, 14. November 2023 um 00:11:37 UTC+1:
> Ok, I was using a SAT solver in a little unorthodox way.
> Used it as a compiler for a formula, so that I got:
>
> yesterday(0,0,0,1,1,0).
> yesterday(0,0,1,0,0,0).
> yesterday(0,1,0,0,0,1).
> yesterday(0,1,1,0,1,0).
> yesterday(1,0,0,0,1,1).
> yesterday(1,0,1,1,0,0).
> yesterday(1,1,0,1,0,1).
>
> two_liars(T1,T2,T3,Y1,Y2,Y3) :-
> T1=\=Y1,
> T1=:=(T1/\Y2) xor (T1/\Y3) xor (Y2/\Y3),
> Y1=:=(T2/\T3) xor (T2/\Y1) xor (T3/\Y1),
> T1=\=(T1/\T2) xor (T1/\T3) xor T2 xor (T2/\T3) xor T3,
> Y1=\=(Y1/\Y2) xor (Y1/\Y3) xor Y2 xor (Y2/\Y3) xor Y3.
>
> solve_for(T1,T2,T3) :-
> yesterday(T1,T2,T3,Y1,Y2,Y3),
> two_liars(T1,T2,T3,Y1,Y2,Y3).
>
> Works fine:
>
> /* SWI-Prolog 9.1.17, optimise=false */
> ?- time(solve_for(T1,T2,T3)).
> % 16 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
> T1 = 1,
> T2 = T3, T3 = 0 ;
> % 10 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
> false.

So how to use a SAT solver as a compiler. First model the problem
with library(clpb) as Boolean formulas.

lying_day(A, B, C, D, M) :- M = (
~A* ~B* ~C*D+
~A* ~B*C* ~D+
~A* ~B*C*D+
A*B* ~C* ~D+
A*B* ~C*D+
A*B*C* ~D).

two_liars(T1, T2, T3, Y1, Y2, Y3, ((M1#M2)*(M3#M4))) :-
lying_day(0, T1, T2, T3, M1),
lying_day(0, Y1, Y2, Y3, M2),
lying_day(1, T1, T2, T3, M3),
lying_day(1, Y1, Y2, Y3, M4).

Then look at the normalform:

?- two_liars(T1,T2,T3,_,_,_,M), sat(M).
sat(1#T2*T3#T2*_A#T3*_A#_A),
sat(T1=:=T1*_B#T1*_C#_B*_C),
sat(T1=\=_A),
sat(T1=\=T1*T2#T1*T3#T2#T2*T3#T3),
sat(_A=\=_A*_B#_A*_C#_B#_B*_C#_C).

Take the normalform, reorder the equations a little bit, fewer
variables first, and rewrite them into ISO core standard bitwise
operations, and then take profit.

Mild Shock schrieb am Dienstag, 14. November 2023 um 00:12:16 UTC+1:
> But I guess I always miss launching SWI-Prolog with optimise=true,
> and the version I am using has default optimise=false.
> Because I get these varying results:
> /* SWI-Prolog 9.1.17, optimise=false */
> ?- time((between(1, 1000000, _), solve_for(T1,T2,T3), fail; true)).
> % 22,999,999 inferences, 2.016 CPU in 2.016 seconds
> (100% CPU, 11410852 Lips)
>
> /* SWI-Prolog 9.1.17, optimise=true */
> ?- time((between(1, 1000000, _), solve_for(T1,T2,T3), fail; true)).
> % 9,999,999 inferences, 1.203 CPU in 1.199 seconds
> (100% CPU, 8311687 Lips)
> Whereas in Dogelog Player I have now practically always
> optimise=true, which then gives me the following:
>
> /* Dogelog Player 1.1.4, JDK 8 */
> ?- time((between(1, 1000000, _), solve_for(T1,T2,T3), fail; true)).
> % Zeit 1892 ms, GC 0 ms, Lips 13213582, Uhr 13.11.2023 23:54
> Mild Shock schrieb am Dienstag, 14. November 2023 um 00:11:37 UTC+1:
> > Ok, I was using a SAT solver in a little unorthodox way.
> > Used it as a compiler for a formula, so that I got:
> >
> > yesterday(0,0,0,1,1,0).
> > yesterday(0,0,1,0,0,0).
> > yesterday(0,1,0,0,0,1).
> > yesterday(0,1,1,0,1,0).
> > yesterday(1,0,0,0,1,1).
> > yesterday(1,0,1,1,0,0).
> > yesterday(1,1,0,1,0,1).
> >
> > two_liars(T1,T2,T3,Y1,Y2,Y3) :-
> > T1=\=Y1,
> > T1=:=(T1/\Y2) xor (T1/\Y3) xor (Y2/\Y3),
> > Y1=:=(T2/\T3) xor (T2/\Y1) xor (T3/\Y1),
> > T1=\=(T1/\T2) xor (T1/\T3) xor T2 xor (T2/\T3) xor T3,
> > Y1=\=(Y1/\Y2) xor (Y1/\Y3) xor Y2 xor (Y2/\Y3) xor Y3.
> >
> > solve_for(T1,T2,T3) :-
> > yesterday(T1,T2,T3,Y1,Y2,Y3),
> > two_liars(T1,T2,T3,Y1,Y2,Y3).
> >
> > Works fine:
> >
> > /* SWI-Prolog 9.1.17, optimise=false */
> > ?- time(solve_for(T1,T2,T3)).
> > % 16 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
> > T1 = 1,
> > T2 = T3, T3 = 0 ;
> > % 10 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
> > false.