Minimum insertions to make palindrome

Question

Today you will be doing another palindrome challenge!

So, your task today is to take a string, and determine the minimum amount of letters required to insert to turn it into a palindrome.

For example, let's take the string fishes.

In this, case the best way would be to add h if, so the result would be 3.

fishe s
     h if
---------
fishehsif

Now let's try with codegolf. Since there is a repeated o, we can just do:

  codeg  o lf
fl     ed c
-------------
flcodegedoclf

to get a result of 5.

Test cases

ppcg -> 2
codegolf -> 5
palindrome -> 9
stackexchange -> 8
programmingpuzzlesandcodegolf -> 20

Answer 1

Python, 112 bytes

d=lambda x,l,h:0if h<l else d(x,l+1,h-1)if x[l]==x[h]else-~min(d(x,l+1,h),d(x,l,h-1));e=lambda x:d(x,0,len(x)-1)

Very inefficient.

Try it online! You have to wait a minute for the last case to finish.

Call with e(<string>, 0, <length of string - 1>), like e("fishes", 0, 5)`.

Ungolfed (sort of) with explanation:

def minInsert(x, l, h):                # Declare func, arugments for x, l, h       # d=lambda x,l,h:
  if l >= h:                           # If l is the same or past h                #                 if h<l
    return 0                           #     then return 0                         #                0
  elif x[l] == x[h]:                   # If first and last character are the same  #                        else             if x[l]==x[h]
    return minInsert(x, l + 1, h - 1)  #     then return the min w/o first & last  #                             d(x,l+1,h-1)
  else:                                # If not, we shave off a character          #                                                      else
    a = minInsert(x, l, h - 1)         #     (last one)                            #                                                                d(x,l+1,h)
    b = minInsert(x, l + 1, h)         #     (first one)                           #                                                                           d(x,l,h-1)
    return min(a, b) + 1               #     and add one for the char we took off  #                                                          -~min(          ,          )

Answer 2

Pyth, 10 bytes

test suite.

l.-Qe@y_Qy

         y   All subsequences of the input (implicit), sorted by length
      y_Q    All subsequences of the reversed input, sorted by length
     @       Their setwise intersection: the common subsequences
    e        Last element: the longest common subsequence
 .-Q         Remove it bagwise from the input: the letters not in this LCS
l            The length of that

There's a few equivalent characterizations of the value we're after:

• The fewest insertions needed to make a palindrome
• The fewest deletions needed to make a palindrome
• Half the number of delete or insert operations needed to transform the string to its reverse
• The length of the input with its longest palindromic subsequence removed
• The length of the input, removing the longest common subsequence between it and its reverse. (The code uses this one.)

The common idea is the "skeleton" of letters in the input that are matched with letters of the input in the final product.

  codeg  o lf
   *  *  *
fl o  gedoc 

flcodegedoclf

This skeleton is always a palindrome, with letters matching to their reversed counterparts. Each non-skeleton letters is unmatched and must have its counterpart inserted.

A same-length alternative instead uses the fourth condition, the length of the input minus the length of its longest palindromic subsequence

l.-Qef_ITy

Link to test suite.

The part that's different is

f_ITy

    y   All subsequences of the input (implicit), sorted by length.
f       Filtered on:
 _IT     being invariant under reversal, i.e. a palindrome

For both, instead of removing the palindromic subsequence from the input and taking the length, we could instead subtract its length from the length of the input. Either one costs 4 bytes: -lQl vs l.-Q.

Answer 3

Brachylog, 9 bytes

⊆P↔P;?lᵐ-

Try it online!

This challenge really needed a Brachylog v2 answer, as insertion palindromization is so intuitive in that language.

Explanation

⊆P↔P really is what does palindromization by insertion (see this example)

⊆P           P is an ordered superset of the input
 P↔P         P reversed is P (i.e. P is a palindrome)
   P;?lᵐ     Compute the length of both P and the input
        -    Subtraction

Answer 4

05AB1E, 11 bytes

Uses CP-1252 encoding.

Âæsæäg¹g-Ä

Try it online! or as a Test suite

Explanation

              # implicit input
             # push a reversed copy
 æ            # compute powerset of the reversed string
  sæ          # compute powerset of the string
    äg       # get length of the longest common subset
      ¹g-     # subtract the length of the original string
         Ä    # take absolute value

Answer 5

C, 89 121 bytes

#define g(a) f(a,a+strlen(a)-1)
f(char*a,char*b){return a>=b?0:*a-*b?f(a+1,b)<f(a,b-1)?f(++a,b)+1:f(a,--b)+1:f(++a,--b);}

Shameless port of Oliver's answer, could not think of any shorter solution.

g calls f with the pointer to the first and the last char of a string (the last char is part of the string, not the '\0'). Gets even more inefficient because f is called two times for the min case.

Ungolfed:

f(char*a,char*b){
 return a>=b ? 0 :
   *a-*b ?    //if the pointed chars are not the same
     f(a+1,b)<f(a,b-1) ? f(a+1,b)+1 : f(a,b-1)+1    //min(f..,f..)+1
   : f(a+1,b-1);  //if they were the same, make it more narrow
 }

Usage:

int main(){
 char s[]="palindrome";
 printf("%d\n",g(s));
}

Answer 6

Brachylog v1, 13 bytes

,IrIs?:I:lar-

Try it online!

You can check the palindromes it finds with this code.

Explanation

I'm almost surprised this even works, seeing how ridiculously simple it is.

,IrI             I reversed is I (i.e. I is a palindrome)
   Is?           The Input is an ordered subset of I
     ?:I:la      The list [length(Input), length(I)]
           r-    Output = length(I) - length(Input)

This is guaranteed to find the smallest palindrome because IrI will generate strings of increasing length when backtracking, starting from the empty string.

This is not efficient enough to compute the last test case on TIO, because of the use of s - Ordered subset.

Answer 7

Batch, 234 232 bytes

@echo off
set n=99
call:l 0 %1
echo %n%
exit/b
:g
set/am=%1
if %m% lss %n% set/an=m
exit/b
:l
if "%2"=="" goto g
set s=%2
if %s:~,1%==%s:~-1% call:l %1 %s:~1,-1%&exit/b
call:l %1+1 %s:~1%
set s=%2
call:l %1+1 %s:~,-1%

Works by recursively trying to insert nonmatching characters at both ends, so very slow (I didn't try the last test case). Recursion limits mean that this only works for a limited string length anyway, so the 99 is somewhat arbitrary. I have to use call parameters as local variables as I couldn't get setlocal to work for me, which means that %1 parameter to the :l subroutine is an expression that evaluates to the number of insertions done so far.