Plus petite distance de Hamming à un palindrome contenant une sous-chaîne

17

Cela a été inspiré par une question CS.SE maintenant supprimée .

Tâche

Étant donné deux chaînes d'entrée A et B non vides, affichez la plus petite distance entre A et un palindrome contenant B comme sous-chaîne. La distance est définie par le nombre de remplacements de personnages ( distance de Hamming ).

Restrictions

  • Entrée sensible: un palindrome existe. Cela signifie | A | ≥ | B |.
  • A et B ne contiennent que des caractères ASCII inférieurs, les minuscules et les majuscules sont distinctes (comme tous les autres caractères).
  • Si votre langue ne peut pas gérer les caractères ASCII, vous pouvez également utiliser des entiers (ou tout autre type de données raisonnable) et vous pouvez choisir de limiter la plage à 128 éléments.
  • Vous pouvez prendre des entrées de stdin, des arguments de fonction, des arguments de ligne de commande, etc.
  • Vous pouvez donner le résultat sur stdout, la valeur de retour, etc.
  • Vous n'avez pas besoin de donner un palindrome de travail, la plus petite distance à l'un suffit.

Exemples

A                   B            Output
thilloaoyreot       hello        4 (thelloaolleht)
benjonson           stack        9 (stackcats)
neversaynever!      odd          9 (neveroddoreven)
ppcggcpp            gg           0 (ppcggcpp)
stars               tat          1 (stats)

Notation

Il s'agit du code golf, le code le plus court en octets gagne.

code-golf string palindrome Communauté
la source

Réponses:

5

Pyth, 19 octets

hSmsnVQd/#z_I#^+Qzl

Manifestation

Approche par force brute extrême. Générez toutes les chaînes de la longueur appropriée avec des caractères dans l'une ou l'autre chaîne, filtrez les palindromes et pour contenir la deuxième entrée, mappez à la distance de hamming de la première chaîne, sortie la plus petite.

Explication:

hSmsnVQd/#z_I#^+Qzl
hSmsnVQd/#z_I#^+QzlQ     Variable introduction
                         Q = string A, z = string B.
               +Qz       Concatenate A and B
              ^   lQ     Form every string of length equal to len(A)using
                         characters from the concatenation.
             #           Filter on
           _I            Invariance under reversal (palindrome)
         #               Filter on
        / z              Nonzero occurences of B
  m                      Map to
    nV                   !=, vectorized over
      Qd                 A and the map input
   s                     Sum (gives the hamming weight)
hS                       Min
isaacg
la source
J'ai pensé à quelque chose comme ça, mais j'ai décidé que O ((m + n) ^ n) était trop O (mauvais). : D
PurkkaKoodari
3

Pyth, 45 octets

hSmsnVQdf}zTsmm+hc2KsXcd+Bklz1z_hc2PKh-lQlz_B

Essayez-le en ligne. Suite de tests.

Je ne suis toujours pas vraiment satisfait de la façon dont cela s'est passé. Mais au moins, c'est assez difficile à comprendre sans explication maintenant. (Succès, je suppose?)

Explication

  • Prenez A as Qet B as z.
  • m… _BQCalculez ce qui suit pour A et son inverse comme d:
    • m… h-ldlzCalculez ce qui suit pour tousk de 0 à len(A) - len(B)inclus:
      • +Bklz Obtenez la paire k, k + len(B) .
      • cd Divisé d ces indices.
      • X…1z Remplacez la deuxième partie (au milieu) par B.
      • KsConcaténer les pièces et enregistrer K. B est maintenant inséré à la positionk A ou à son revers.
      • hc2Divisez la chaîne résultante en deux et conservez la première pièce. Cela donne la moitié de la chaîne avec le caractère central possible.
      • hc2PKRetirez le dernier caractère et faites la même division, en gardant le premier morceau. Cela donne la moitié de la chaîne sans le caractère central possible.
      • +… _Ajoutez le revers de la pièce la plus courte à la pièce la plus longue. Nous avons maintenant un palindrome.
  • s Concatène les résultats pour A et son inverse.
  • f}zT Supprimez toutes les chaînes qui ne contiennent pas B.
  • m Calculez ce qui suit pour toutes les chaînes résultantes d :
    • nVQd Obtenez l'inégalité par paire avec A. Cela donne True pour les paires qui doivent être modifiées.
    • sAdditionnez la liste. Cela donne la distance de Hamming.
  • hS Prenez le résultat minimum.
PurkkaKoodari
la source
1

JavaScript (Firefox 30+), 152 146 octets

(A,B)=>Math.min(...[...Array(A[l='length']-B[l]+1)].map((_,i)=>[for(c of q=A.slice(j=t=0,i)+B+A.slice(i+B[l]))t+=(c!=A[j])+(c!=q[q[l]-++j])/2]|t))

Approche par force brute: générer chaque chevauchement possible de A et B, en faire chacun un palindrome, calculer les distances de Hamming à partir de A et prendre la plus petite des distances résultantes.

Peut-être pourrait-on jouer un peu plus au golf ...

Extrait de test

Afficher l'extrait de code

ETHproductions
la source