prologturbo-prolog

Turbo Prolog: Create a palindrome by adding the smallest number of characters to the list


There is a code on Turbo Prolog that creates a palindrome from the entire input list.

Need to make the palindrome is built by adding the least characters to the list.

For example, we entered a list [1, 2, 3, 4, 3] and at the exit instead of [1, 2, 3, 4, 3, 4, 3, 2, 1] It should work out [1, 2, 3, 4, 3, 2, 1] ( that is, the program should add the missing elements to the palindrome, rather than building it from the entire entered list)

HELP

This code creates a palindrome from the entire input list:

domains
  list = integer*
 
predicates
  readlist(list).
  extend_to_palindrome(list, list).
  reverse(list, list).
  append(list, list, list).
  suffix(list, list).
 
clauses
  readlist([Head|Tail]) :-
    readint(Head), !,
    readlist(Tail).
  readlist([]).
 
  reverse([], []).
  reverse([H|T], Reversed) :-
    reverse(T, ReversedTail),
    append(ReversedTail, [H], Reversed).
 
  append([], List, List).
  append([H|T], List2, [H|Result]) :-
    append(T, List2, Result).
 
  suffix(List, Suffix) :-
    append([], Suffix, List).
 
  extend_to_palindrome(List, Result) :-
    suffix(List, Suffix),
    reverse(Suffix, [_|TrimmedReversedSuffix]),
    append(List, TrimmedReversedSuffix, Result).
 
goal
  write("Enter elements: "), nl,
  readlist(List),
  extend_to_palindrome(List, Palindrome),
  write("Palindrome: "), write(Palindrome), nl.

Solution

  • reverse(Suffix, [_|TrimmedReversedSuffix]) - in SWI Prolog the _ can only be a single thing; if that is the same in Turbo Prolog this will not trim different amounts, and will not search for shorter or longer answers.

    extend_to_palindrome/2 does not test if the list is a palindrome, so it can not check other possible solutions.

    In this example code, I use append/3 with backtracking to search a variable amount from the Left of the list, reverse it and then use append again, and use reverse to test if the result is a palindrome (reversing it doesn't change it).

    Ls = [1,2,3,4,3],
    
    append(Left, _, Ls)            % take variable amount from left,
    
    reverse(Left, Right),          % reverse it,
    append(Ls, Right, Result),     % stick it to the right.
    
    reverse(Result, Result)        % it must make a palindrome.
    

    This will try appending [], [1], [2,1], [3,2,1], [4,3,2,1], [3,4,3,2,1] and pick out the ones which make a palindrome, shortest first.