RabbitFarm

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given two sets with unique numbers. Write a script to figure out if they are disjoint.

Solution

:-initialization(main).

conflicts(List0, List1):-
    member(X, List0),
    member(X, List1).

disjoint(List0, List1):-
    \+ conflicts(List0, List1).

main:-
    ((disjoint([1, 2, 5, 3, 4], [4, 6, 7, 8, 9]), write(1)); (write(0))),
    nl,
    ((disjoint([1, 3, 5, 7, 9], [0, 2, 4, 6, 8]), write(1)); (write(0))),
    nl,
    halt. 

Sample Run

$ gplc prolog/ch-1.p 
$ prolog/ch-1   
0
1

Notes

The conflcts/2 predicate establishes whether or not if there is any overlapping elements in the two lists. To establish whether the sets are disjoint disjoint/2 examines the negation of this result.

Remember, Prolog only backtracks on failure and not success. This fits nicely for what we want. We only care if the lists have any overlap whatsoever. So using backtracking conflicts/2 will backtrack for all members of List0 until it either succeeds in finding an element that is also in List1 or, if none, fails completely indicating a disjoint set. Since we actually consider the discovery of disjoint sets a success we negate the result with \+ in disjoint/2.

Part 2

You are given a list of intervals. Write a script to determine conflicts between the intervals.

Solution

:-initialization(main).

conflicts(Intervals, Conflicts):-
    conflicts(Intervals, Conflicts, []).
conflicts([_|[]], Conflicts, ConflictsAccum):-
    sort(ConflictsAccum, Conflicts).
conflicts([H|T], Conflicts, ConflictsAccum):-
    last(T, Last),
    append(Intervals, [Last], T),
    append([H], Intervals, CompareIntervals),
    comparisons(Last, CompareIntervals, HasConflicts),
    append(ConflictsAccum, HasConflicts, ConflictsAccumUpdated),
    conflicts(CompareIntervals, Conflicts, ConflictsAccumUpdated).

comparisons(Interval, CompareIntervals, Conflicts):-
    comparisons(Interval, CompareIntervals, Conflicts, []).
comparisons(_, [], Conflicts, Conflicts).
comparisons(Interval, [[H0|T0]|T], Conflicts, ConflictsAccum):-
    [I|J] = Interval,
    I >= H0,
    I =< T0,
    comparisons([I|J], T, Conflicts, [Interval|ConflictsAccum]).
comparisons([I|J], [_|T], Conflicts, ConflictsAccum):-
    comparisons([I|J], T, Conflicts, ConflictsAccum).

main:-
    conflicts([[1, 4], [3, 5], [6, 8], [12, 13], [3, 20]], Conflicts0),
    write(Conflicts0), nl,
    conflicts([[3, 4], [5, 7], [6, 9], [10, 12], [13, 15]], Conflicts1),
    write(Conflicts1), nl,
    halt.

Sample Run

$ gplc prolog/ch-2.p
$ prolog/ch-2
[[3,5],[3,20]]
[[6,9]]

Notes

The examples given in the problem statement are with the [minimum, maximum] intervals sorted by the maximum value. This makes the problem a bit easier since then we need only check to see if, when working down the sorted list, if the minimum is in one of the other intervals.

This is mostly all handled using recursion which keeps with the nature of the examples in the problem statement. This is fine, and obviously works, but after having worked out the details of finding a solution it seems there is room to make this more, well, logical?

Preferring reasoning over recursion as a principle of Prolog development seems to be reasonable (pun intended!). Here we might, for example, arrange the intervals in Key-Value pairs stored in the Prolog database and make better use of built in backtracking. But even that would include a little extra work as we would need to sort the pairs by value and ultimately the same number of lines of code would be written as shown here, it would just arguably be a bit more Prological.

Sometimes the best solution to a problem is only discovered after working on it for a bit using alternative means!

References

Challenge 127

Disjoint Sets