Aujourd'hui, vous allez relever un autre défi palindrome!

Donc, votre tâche aujourd'hui est de prendre une chaîne et de déterminer la quantité minimale de lettres à insérer pour la transformer en palindrome.

Par exemple, prenons la chaîne fishes.

Dans ce cas, la meilleure façon serait d'ajouter h if, donc le résultat serait 3.

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

Essayons maintenant avec codegolf. Puisqu'il y a une répétition o, on peut juste faire:

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

pour obtenir un résultat de 5.

Cas de test

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

Pyth, 10 octets

suite de tests.

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

Il y a quelques caractérisations équivalentes de la valeur que nous recherchons:

• Le moins d'insertions nécessaires pour faire un palindrome
• Le moins de suppressions nécessaires pour faire un palindrome
• La moitié du nombre d'opérations de suppression ou d'insertion nécessaires pour transformer la chaîne en son inverse
• La longueur de l'entrée avec sa plus longue sous-séquence palindromique supprimée
• La longueur de l'entrée, supprimant la sous-séquence commune la plus longue entre elle et son inverse. (Le code utilise celui-ci.)

L'idée commune est le "squelette" des lettres dans l'entrée qui sont appariées avec les lettres de l'entrée dans le produit final.

  codeg  o lf
   *  *  *
fl o  gedoc 

flcodegedoclf

Ce squelette est toujours un palindrome, avec des lettres correspondant à leurs homologues inversés. Chaque lettre non squelette est inégalée et doit avoir sa contrepartie insérée.

Une alternative de même longueur utilise à la place la quatrième condition, la longueur de l'entrée moins la longueur de sa sous-séquence palindromique la plus longue

l.-Qef_ITy

Lien vers la suite de tests.

La partie qui est différente est

f_ITy

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

Pour les deux, au lieu de supprimer la sous-séquence palindromique de l'entrée et de prendre la longueur, nous pourrions plutôt soustraire sa longueur de la longueur de l'entrée. Soit un coût de 4 octets: -lQlvs l.-Q.

Python, 112 octets

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)

Très inefficace.

Essayez-le en ligne! Vous devez attendre une minute pour que le dernier cas se termine.

Appelez avec e(<string>, 0, <length of string - 1>), comme e ("poissons", 0, 5) `.

Non golfé (en quelque sorte) avec explication:

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 octets

Utilise l' encodage CP-1252 .

Âæsæäg¹g-Ä

Essayez-le en ligne! ou comme suite de tests

Explication

              # 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 octets

⊆P↔P;?lᵐ-

Essayez-le en ligne!

Ce défi avait vraiment besoin d'une réponse Brachylog v2, car la palindromisation d'insertion est tellement intuitive dans cette langue.

Explication

⊆P↔Pest vraiment ce que fait la palindromisation par insertion (voir cet exemple )

⊆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 octets

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

Port sans vergogne de la réponse d' Oliver , ne pouvait pas penser à une solution plus courte.

gappelle favec le pointeur sur le premier et le dernier caractère d'une chaîne (le dernier caractère fait partie de la chaîne, pas le '\0'). Obtient encore plus inefficace car fest appelé deux fois pour le mincas.

Non 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
 }

Usage:

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

Brachylog v1 , 13 octets

,IrIs?:I:lar-

Essayez-le en ligne!

Vous pouvez vérifier les palindromes qu'il trouve avec ce code .

Explication

Je suis presque surpris que cela fonctionne même, vu à quel point c'est ridiculement simple.

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

Ceci est garanti pour trouver le plus petit palindrome car IrIgénérera des chaînes de longueur croissante lors du retour en arrière, à partir de la chaîne vide.

Ce n'est pas assez efficace pour calculer le dernier cas de test sur TIO, à cause de l'utilisation de s - Ordered subset.

Lot, 234 232 octets

@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%

Fonctionne en essayant récursivement d'insérer des caractères non correspondants aux deux extrémités, donc très lent (je n'ai pas essayé le dernier cas de test). Les limites de récursivité signifient que cela ne fonctionne que pour une longueur de chaîne limitée de toute façon, donc 99c'est quelque peu arbitraire. Je dois utiliser des callparamètres en tant que variables locales car je n'ai pas pu setlocaltravailler pour moi, ce qui signifie que le %1paramètre du :lsous-programme est une expression qui évalue le nombre d'insertions effectuées jusqu'à présent.