¡Hoy harás otro desafío de palíndromo!

Entonces, su tarea hoy es tomar una cadena y determinar la cantidad mínima de letras necesarias para insertar para convertirlo en un palíndromo.

Por ejemplo, tomemos la cadena fishes.

En este caso, la mejor manera sería agregar h if, por lo que el resultado sería 3.

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

Ahora intentemos con codegolf. Como hay una repetición o, solo podemos hacer:

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

para obtener un resultado de 5.

Casos de prueba

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

Pyth, 10 bytes

Banco de pruebas.

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

Hay algunas caracterizaciones equivalentes del valor que buscamos:

• La menor cantidad de inserciones necesarias para hacer un palíndromo
• La menor cantidad de eliminaciones necesarias para hacer un palíndromo
• La mitad del número de operaciones de eliminación o inserción necesarias para transformar la cadena a su reverso
• La longitud de la entrada con su subsecuencia palindrómica más larga eliminada
• La longitud de la entrada, eliminando la subsecuencia común más larga entre ella y su reverso. (El código usa este).

La idea común es el "esqueleto" de letras en la entrada que coinciden con las letras de la entrada en el producto final.

  codeg  o lf
   *  *  *
fl o  gedoc 

flcodegedoclf

Este esqueleto es siempre un palíndromo, con letras que coinciden con sus contrapartes invertidas. Cada letra no esqueleto no tiene comparación y debe tener su contraparte insertada.

Una alternativa de la misma longitud utiliza la cuarta condición, la longitud de la entrada menos la longitud de su subsecuencia palindrómica más larga

l.-Qef_ITy

Enlace a la suite de prueba.

La parte que es diferente es

f_ITy

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

Para ambos, en lugar de eliminar la subsecuencia palindrómica de la entrada y tomar la longitud, podríamos restar su longitud de la longitud de la entrada. Cualquiera de los dos costos: 4 bytes -lQlvs l.-Q.

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)

Muy ineficiente

Pruébalo en línea! Tienes que esperar un minuto hasta que termine el último caso.

Llame con e(<string>, 0, <length of string - 1>), como e ("peces", 0, 5) `.

Ungolfed (más o menos) con explicación:

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(          ,          )

05AB1E , 11 bytes

Utiliza la codificación CP-1252 .

Âæsæäg¹g-Ä

Pruébalo en línea! o como un conjunto de pruebas

Explicación

              # 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

Brachylog , 9 bytes

⊆P↔P;?lᵐ-

Pruébalo en línea!

Este desafío realmente necesitaba una respuesta Brachylog v2, ya que la inserción de palindromización es muy intuitiva en ese idioma.

Explicación

⊆P↔Prealmente es lo que hace la palindromización por inserción (ver este ejemplo )

⊆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

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);}

Puerto descarado de la respuesta de Oliver , no podía pensar en una solución más corta.

gllama fcon el puntero al primer y último carácter de una cadena (el último carácter es parte de la cadena, no el '\0'). Se vuelve aún más ineficiente porque fse llama dos veces para el mincaso.

Sin golf:

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
 }

Uso:

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

Brachylog v1 , 13 bytes

,IrIs?:I:lar-

Pruébalo en línea!

Puede verificar los palíndromos que encuentra con este código .

Explicación

Casi me sorprende que esto incluso funcione, al ver lo ridículamente simple que es.

,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)

Esto está garantizado para encontrar el palíndromo más pequeño porque IrI generará cadenas de longitud creciente al retroceder, comenzando desde la cadena vacía.

Esto no es lo suficientemente eficiente como para calcular el último caso de prueba en TIO, debido al uso de s - Ordered subset.

Lote, 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%

Funciona intentando recursivamente insertar caracteres no coincidentes en ambos extremos, muy lento (no probé el último caso de prueba). Los límites de recursión significan que esto solo funciona para una longitud de cadena limitada de todos modos, por lo que 99es algo arbitrario. Tengo que usar callparámetros como variables locales, ya que no pude setlocaltrabajar para mí, lo que significa que el %1parámetro de la :lsubrutina es una expresión que evalúa el número de inserciones realizadas hasta ahora.