I'm new to prolog, I don't understand much of the language and I had already posted a question about Prolog before. Now I want to obtain, from a list of integers, the numbers in the interval that contains the largest amount of numbers in that list, in other words the maximum range. Example:
maxrange(X,Y,[1,3,2,7,4,5,6,9,8]).
X = 1, Y= 10.
maxrange(1,10,[1,3,2,7,4,5,6,9,8].
True.
maxrange(1,8,[1,3,2,7,4,5,6,9,8].
False.
Lists must contain all numbers between [X,Y) and must be the maximum interval.
Try this code:
maxrange(A, B, List) :-
maxranges(List, Ranges),
member(A-B, Ranges).
maxranges(List, Ranges) :-
sort(List, [Min|Sorted]),
maxranges_loop(Sorted, Min, Min, [], Ranges).
maxranges_loop([], A, B, Ranges, UpdatedRanges) :-
update(Ranges, A, B, UpdatedRanges).
maxranges_loop([X|Xs], A, B, Ranges, UpdatedRanges) :-
Bool is abs(sign(X - (B + 1))),
maxranges_case(Bool, X, Xs, A, B, Ranges, UpdatedRanges).
maxranges_case(0, X, Xs, A, _, Ranges, UpdatedRanges) :-
maxranges_loop(Xs, A, X, Ranges, UpdatedRanges).
maxranges_case(1, X, Xs, A, B, Ranges, UpdatedRanges) :-
maxranges_loop(Xs, X, X, Ranges, NewRanges),
update(NewRanges, A, B, UpdatedRanges).
update([], A, B0, [A-B]) :- B is B0+1.
update([A0-B0|Ranges], A, B, UpdatedRanges) :-
B1 is B+1,
Sign is sign((B1-A)-(B0-A0)),
update_case(Sign, [A0-B0|Ranges], A, B1, UpdatedRanges).
update_case( 0, Ranges, A, B, [A-B|Ranges]).
update_case(+1, _, A, B, [A-B]).
update_case(-1, Ranges, _, _, Ranges).
Examples:
?- maxrange(X, Y, [1,3,2,7,4,5,6,9,8]).
X = 1,
Y = 10.
?- maxrange(1, 10, [1,3,2,7,4,5,6,9,8]).
true.
?- maxrange(1, 8, [1,3,2,7,4,5,6,9,8]).
false.
?- maxrange(A, B, [1,2, 4,5,6,7, 9,10,11, 14,15,16,17]).
A = 4,
B = 8 ;
A = 14,
B = 18.
?- maxranges([1,2, 4,5,6,7, 9,10,11, 14,15,16,17], R).
R = [4-8, 14-18].
EXPLANATION
update_case/5 updates a list of maximum ranges, with respect to a new range [A..B), written in Prolog as A-B. If its first argument is 0, then the new range [A..B) is added to that list; if its first argument is +1, that list changes to a new list containing only the range [A..B); and, its first argument is -1, then that list is kept unchanged.?- update_case(0, [14-18], 5, 9, R).
R = [5-9, 14-18].
?- update_case(+1, [14-18], 1, 9, R).
R = [1-9].
?- update_case(-1, [14-18], 3, 7, R).
R = [14-18].
update/4 updates a list of maximum ranges with respect to a new range [A..B]. First, it transforms the closed range [A..B] into a corresponding right-open range [A..B+1). Then, if that list is empty, the predicate adds the new range to it. Otherwise, the predicate compares the range [A..B+1) with the first range in that list, say [A0..B0). The comparison is made by the expression Sign is sign((B+1-A)-(B0-A0). If both ranges are equal, then Sign is 0; if the first range is bigger than the second, then Sign is +1; and, if the first range is lesser than the second, then Sign is -1. The result of the comparision is used to call the predicate update_case/5.?- update([], 17, 19, R).
R = [17-20].
?- update([17-20], 11, 13, R). % equal
R = [11-14, 17-20].
?- update([11-14, 17-20], 5, 9, R). % bigger
R = [5-10].
?- update([5-10], 2, 3, R). % lesser
R = [5-10].
The predicate maxranges_loop/5 traverses a sorted list (without duplicates) and finds all ranges that are part of it. For each range found, the list of current maximum ranges is updated with a call to the predicate update/4.
The predicate maxranges/2 is just a wrapper to the predicate maxranges_loop/5, that ensures the list is sorted and does not contain duplicates.
The predicate maxrange/3 call maxranges/2 to get the list of maximum ranges and checks whether the range [A..B) belongs to it.