I need to do a turbo prolog program that removes all palindromes (includes crossed palindromes like 1 2 1 3 1) from the list.
I tried to do a program using the following algorithm:
For ex: 1 2 1 3 1 4 5 1
Create the list of all prefixes of the original list. It looks like [[1], [1,2], [1,2,1],…]
Create the list of palindromes that were cut from the list of all prefixes. That means we checked every single prefix if it’s palindrome and if it’s > 1. For this particular ex. it looks like [[1,2,1][1,3,1]]
Delete every element of the original list according to list of palindromes. That means if element exist in list of palindromes that it’ll be deleted. (There is the mistake) With this ex. it’ll output [4,5], but should [4,5,1]
Yesterday I talk to my professor and he said that we can index every element of the list, then index every element of palindrome, delete duplicates of indexes and then delete elements from the original list according to this indexes. But I don’t know how to do it.
So, I’ll be very happy if you will be able to help me guys🥺
Here is my code:
domains
int = integer
intl = int*
intll = intl*
predicates
read_list(intl)
reverse(intl, intl)
append(intll, intll, intll)
app(intl, intl, intl)
length(intl, int)
cut(intl, int, intl)
subseq(intl, int, int, intl)
prefixes(intl, int, intll)
all_sublists(intl, intll)
is_pal(intl)
all_pals(intll, intll)
all_palindroms(intl, intll)
belongs_to_sublist(int, intll)
filter_elements(intll, intl, intl)
member(int, intl)
clauses
read_list([Head|Tail]) :-
readint(Head), !,
read_list(Tail).
read_list([]).
reverse([], []).
reverse([H|T], X) :- reverse(T, Rt), app(Rt, [H], X).
append([], X, X).
append([H|T], X, [H|R]) :- append(T, X, R).
app([], X, X).
app([H|T], X, [H|R]) :- app(T, X, R).
length([], 0).
length([_|T], N) :- length(T, N1), N = N1 + 1.
cut(_, 0, []) :- !.
cut([H|T], L, [H|R]) :- L1 = L - 1, cut(T, L1, R).
subseq(X, 0, L, R) :- cut(X, L, R), !.
subseq([_|X], P, L, R) :- P1 = P - 1, subseq(X, P1, L, R).
prefixes(X, L, []) :- length(X, LX), L > LX, !.
prefixes(X, L, [R|T]) :- subseq(X, 0, L, R), L1 = L + 1, prefixes(X, L1, T).
all_sublists([], []).
all_sublists([H|T], Q) :- prefixes([H|T], 1, R), all_sublists(T, Z), append(R, Z, Q).
is_pal(X) :- reverse(X, Rx), X = Rx.
all_pals([], []).
all_pals([H|T], [H|R]) :- length(H, L), L > 1, is_pal(H), all_pals(T, R), !.
all_pals([_|T], R) :- all_pals(T, R).
all_palindroms(X, U) :- all_sublists(X, Sx), all_pals(Sx, U).
belongs_to_sublist(Element, [Sublist|_]) :-
member(Element, Sublist).
belongs_to_sublist(Element, [_|Sublists]) :-
belongs_to_sublist(Element, Sublists).
filter_elements(_, [], []).
filter_elements(Sublists, [H|T], [H|Filtered]) :-
not(belongs_to_sublist(H, Sublists)),
filter_elements(Sublists, T, Filtered).
filter_elements(Sublists, [H|T], Filtered) :-
belongs_to_sublist(H, Sublists),
filter_elements(Sublists, T, Filtered).
member(X, [X|_]).
member(X, [_|Tail]) :- member(X, Tail).
goal
write("Elements of list:"), nl,
read_list(List),
write("list:"), write(List), nl,
all_palindroms(List, Q), write("all palindromes in list: "), write(Q), nl,
filter_elements(Q, List, Res), write("without palindromes: "), write(Res).
As I don't have Turbo-Prolog on my computer, I solved the problem using SWI-Prolog. I suppose you can easily adapt this code to Turbo-Prolog.
palindromic_prefix(List, Prefix) :-
Prefix = [_,_|_],
append(Prefix, _, List),
reverse(Prefix, Prefix).
collect_palindromic_ranges([], _, []).
collect_palindromic_ranges([X|Xs], Index, Ranges) :-
( palindromic_prefix([X|Xs], Prefix)
-> length(Prefix, Length),
End is Index + Length - 1,
Ranges = [Index-End|Rest]
; Ranges = Rest),
Next is Index + 1,
collect_palindromic_ranges(Xs, Next, Rest).
exclude_palindromic_ranges([], _, _, []).
exclude_palindromic_ranges([X|Xs], Index, Ranges, Rest) :-
( member(Begin-End, Ranges),
between(Begin, End, Index)
-> Rest = Rest0
; Rest = [X|Rest0] ),
NextIndex is Index + 1,
exclude_palindromic_ranges(Xs, NextIndex, Ranges, Rest0).
remove_palindromic_sublists(List, Rest) :-
collect_palindromic_ranges(List, 1, Ranges),
exclude_palindromic_ranges(List, 1, Ranges, Rest).
Examples:
?- remove_palindromic_sublists([1,2,1,3,1,4,5,1], Rest).
Rest = [4, 5, 1].
?- remove_palindromic_sublists([0,1,2,1,3,3,1,4,5,1,5,6], Rest).
Rest = [0, 4, 6].
?- remove_palindromic_sublists([1,2,3,2,1], Rest).
Rest = [].
?- remove_palindromic_sublists([1,1,1], Rest).
Rest = [].
?- remove_palindromic_sublists([1,2,3], Rest).
Rest = [1, 2, 3].
The predicate palindromic_prefix(+List, -Prefix) succeds if, and only if, List has a palindrome Prefix:
?- palindromic_prefix([1,2,1,3,1,4,5,1], Prefix).
Prefix = [1, 2, 1] .
?- palindromic_prefix([2,1,3,1,4,5,1], Prefix).
false.
The predicate collect_palindromic_ranges(+List, +Index, -Ranges) collects all Ranges in List, indexed from Index, which contains palindromic sublists:
?- collect_palindromic_ranges([1,2,1,3,1,4,5,1], 1, Ranges).
Ranges = [1-3, 3-5].
The predicate exclude_palindromic_ranges(+List, +Index, +Ranges, -Rest) excludes all elements of List that are in one of the Ranges, indexed from Index:
?- List = [1,2,1,3,1,4,5,1], collect_palindromic_ranges(List, 1, Ranges), exclude_palindromic_ranges(List, 1, Ranges, Rest).
List = [1, 2, 1, 3, 1, 4, 5, 1],
Ranges = [1-3, 3-5],
Rest = [4, 5, 1].