Prolog Time Overlap Woes

Question

Say I have this Knowledge Base:

free(ann,slot(time(8,0),time(9,0))).
free(ann,slot(time(10,0),time(11,0))).

free(bob,slot(time(7,0),time(8,30))).
free(bob,slot(time(10,0),time(11,0))).

free(carla,slot(time(8,0),time(9,0))).
free(carla,slot(time(10,0),time(10,15))).

So, after a lot of effort, I managed to write something that prints the first person who has availability during a specific slot with the following code:

meetone(Person, slot(time(BeginHour, BeginMinute), time(EndHour, EndMinute)))
:- free(Person, slot(time(BH, BM), time(EH, EM))),
   BH*60 + BM =< EndHour*60 + EndMinute,
   EH*60 + EM >= BeginHour*60 + BeginMinute.

main :- (meetone(Person,slot(time(7,15),time(7,20))); halt),
       write(Person),
       nl,
       halt.

:- initialization(main).

This prints bob, the expected result.

Here's where it gets complicated (at least for me). Let's say I want to find out all the time slots everyone in the Knowledge Base has in common. The following code demonstrates how I ultimately want to call this:

people([ann,bob,carla]).

meet :- ???

main :- (setof(Slot,meet(Slot),Slots); halt),
        write(Slots),
        nl,
        halt.

:- initialization(main).

Here's some vague pseudocode that I think might accomplish what I'm looking for, but I'm not experienced enough to get it working.

1. Start with the first person's free slots.
2. Recursively traverse the rest of the list of people, finding the overlapping times.
3. Slots can be verified to overlap using something similar to meetone; following this verification, the max of the two slot's begin times and the min of the two end times can be used to find the exact overlapping period.
4. Print the final list of slots.

The final output would show slots of 8:00 - 8:30 and 10:00 - 10:15. Any help in accomplishing this would be greatly appreciated.

Answer 1

Prolog has some syntactic features that, imho, really help writing understandable code. Then here is your question, taking advantage from operators to gain readability:

free(ann, 08:00 > 09:00).
free(ann, 10:00 > 11:00).

free(bob, 07:00 > 08:30).
free(bob, 10:00 > 11:00).

free(carla, 08:00 > 09:00).
free(carla, 10:00 > 10:15).

meetone(Person, Slot) :- free(Person, SlotP), contains(SlotP, Slot).

contains(Slot1, Slot2) :-
   timepoints(Slot1, B1, E1),
   timepoints(Slot2, B2, E2),
   B1 =< E2, E1 >= B2.

timepoints(BH:BM > EH:EM, B, E) :-
   B is BH*60 + BM,
   E is EH*60 + EM.

main :- setof(Person, meetone(Person, 7:15 > 7:20), Available),
    maplist(writeln, Available).

I attempted to introduce two utilities, kind of reusable code: contains/2 and timepoints/3. Having such snippets could help while writing more complex logic...

Running this code, I get

?- main.
bob
true.

now coming to your main question:

Let's say I want to find out all the time slots everyone in the Knowledge Base has in common

I would start writing a common_timeslot/3, explaining (computing) what's expected:

common_timeslot(S1, S2, Common) :-
   timepoints(S1, B1, E1),
   timepoints(S2, B2, E2), 
   % do you mean intersection by common ?
   ...

otherwise, consider only identity

common_timeslot(S, S, S).

Having defined this one, all commons can be found with

main :-
    setof(Sc/P/Q, Sp^Sq^(
        free(P, Sp), free(Q, Sq), Q \= P,
        common_timeslot(Sp, Sq, Sc)
    ), Commons),
    maplist(writeln, Commons).

that yields

?- main.
(8:0>9:0)/ann/carla
(8:0>9:0)/carla/ann
(10:0>11:0)/ann/bob
(10:0>11:0)/bob/ann
true.

edit accounting for mat comment, now I post the entire program

free(ann, 08:00 < 09:00).
free(ann, 10:00 < 11:00).

free(bob, 07:00 < 08:30).
free(bob, 10:00 < 11:00).

free(carla, 08:00 < 09:00).
free(carla, 10:00 < 10:15).

meetone(Person, Slot) :- free(Person, SlotP), contains(SlotP, Slot).

contains(Slot1, Slot2) :-
   timepoints(Slot1, B1, E1),
   timepoints(Slot2, B2, E2),
   B1 =< E2, E1 >= B2.

timepoints(BH:BM < EH:EM, B, E) :-
    (   ( var(B), var(E) )
    ->  B is BH * 60 + BM,
        E is EH * 60 + EM
    ;   BH is B // 60,
        BM is floor(B mod 60),
        EH is E // 60,
        EM is floor(E mod 60)
    ).

% common_timeslot(S, S, S).
common_timeslot(S1,S2,S) :-
    timepoints(S1,B1,E1),
    timepoints(S2,B2,E2),
    B is max(B1,B2),
    E is min(E1,E2),
    B < E,
    timepoints(S,B,E).

% base case: C passed all commonality test
check_common(C, [], C).

% S is the current common, to be checked for availability on person P
check_common(S, [P|Ps], C) :-
    free(P, Sp),
    common_timeslot(S, Sp, Ct),
    check_common(Ct, Ps, C).

main :- setof(P, S^free(P,S), [FirstP|Others]),
    forall(free(FirstP, S), (
        check_common(S, Others, C),
        writeln(FirstP:C)
    )).

that yields

?- main.
ann: (8:0<8:30)
ann: (10:0<10:15)
true.

The main change is that timepoints/3 is now 'bidirectional'. Then I introduced common_timeslot/3 as you explained in your comment.

I think you could appreciate that those small syntactic abstractions help to have a clean 'applicative' logic. Of course, forall/2, or setof/3, are builtins that you need to learn about to gain more proficiency in Prolog.