I have written the following code to check whether it is a palindrome or not. I have also created the logic to insert elements when the list is not a palindrome
reverse_list(Inputlist, Outputlist) :- reverse(Inputlist, [], Outputlist). reverse([], Outputlist, Outputlist). reverse([Head|Tail], List1, List2) :- reverse(Tail, [Head|List1], List2). printList([]). printList([X|List]) :- write(X), write(' '), printList(List). palindrome(List1) :- reverse_list(List1, List2), compareLists(List1, List1, List2, List2). compareLists(L1, [], [], L2) :- write("\nList is Palindrome"). compareLists(L1, [X|List1], [X|List2], L2) :- compareLists(L1, List1, List2, L2), !. compareLists(L1, [X|List1], [Y|List2], [Z|L2]) :- write("\nList is not Palindrome. "), append(L1, L2, L), printList(L). The code gives the correct output for
palindrome([a,b,c,a]). List is not Palindrome. a b c a c b a palindrome([a,b,c]). List is not Palindrome. a b c b a However, for an input such as
palindrome([a,b,c,b]). List is not Palindrome. a b c b c b a The optimal solution however should be
a b c b a What changes should I incorporate to be able to achieve this?
2 Answers
Answers 1
I think you need a predicate with two Args, In and Out :
pal([], []). pal([X], [X]). pal(In, Out) :- % first we check if the first and last letter are the same ( append([H|T], [H], In) % we must check that the middle is a palindrome -> pal(T, T1), append([H|T1], [H], Out) ; % if not, we remove the first letter % and we work with the rest In = [H|T], % we compute the palindrome from T pal(T,T1), % and we complete the palindrome to % fit the first letter of the input append([H|T1], [H], Out)). EDIT1 This code looks good but there is a bug for
? pal([a,b,c,a], P). P = [a, b, c, b, a] . Should be [a,b,c,a,c,b,a] I'll try to fix it.
EDIT2 Looks correct :
build_pal([H|T], Out):- pal(T,T1), append([H|T1], [H], Out). pal([], []). pal([X], [X]). pal(In, Out) :- ( append([H|T], [H], In) -> pal(T, T1), ( T = T1 -> append([H|T1], [H], Out) ; build_pal(In, Out)) ; build_pal(In, Out)). with output :
?- pal([a,b,c], P). P = [a, b, c, b, a] . ?- pal([a,b,a], P). P = [a, b, a] . ?- pal([a,b,c,b], P). P = [a, b, c, b, a] . ?- pal([a,b,c,a], P). P = [a, b, c, a, c, b, a] . ?- pal([a,b,a,c,a], P). P = [a, b, a, c, a, b, a] . Answers 2
The first 3 equations of a DCG capture the palindrome pattern. Add a fourth, covering the mismatch, to complete the specification:
p([]) --> []. p([T]) --> [T]. p([T|R]) --> [T], p(P), [T], {append(P,[T],R)}. p([T|R]) --> [T], p(P), {append(P,[T],R)}. ?- phrase(p(L), [a,b,c,b]). L = [a, b, c, b, a] ; L = [a, b, c, c, b, a] ; L = [a, b, c, b, c, b, a] ; L = [a, b, c, b, b, c, b, a] ; false. 
0 comments:
Post a Comment