_{To był inspirowany przez teraz usunięte CS.SE pytanie .}

Zadanie

Biorąc pod uwagę dwa niepuste ciągi wejściowe A i B, wypisz najmniejszą odległość od A do palindromu zawierającego B jako podłańcuch. Odległość jest definiowana przez liczbę zamienników postaci ( odległość Hamminga ).

Ograniczenia

• Rozsądne wejście: istnieje palindrom. Oznacza to | A | ≥ | B |.
• A i B zawierają tylko małe znaki ASCII, małe i wielkie litery są odrębne (podobnie jak wszystkie inne znaki).
• Jeśli twój język nie radzi sobie ze znakami ASCII, możesz również użyć liczb całkowitych (lub innego rozsądnego typu danych) i możesz ograniczyć zakres do 128 elementów.
• Możesz pobierać dane wejściowe ze standardowego wejścia, argumentów funkcji, argumentów wiersza poleceń itp.
• Możesz podać wynik na stdout, zwrócić wartość itp.
• Nie musisz podawać działającego palindromu, wystarczy najmniejsza odległość do jednego.

Przykłady

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

Punktacja

To jest kod golfowy, wygrywa najkrótszy kod w bajtach.

Pyth, 19 bajtów

hSmsnVQd/#z_I#^+Qzl

Demonstracja

Podejście ekstremalnej brutalnej siły. Wygeneruj wszystkie ciągi o odpowiedniej długości ze znakami w jednym z ciągów, filtruj palindromy i dla drugiego wejścia, odwzoruj na hamowanie odległość od pierwszego ciągu, najmniejsze wyjście.

Wyjaśnienie:

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

Pyth, 45 bajtów

hSmsnVQdf}zTsmm+hc2KsXcd+Bklz1z_hc2PKh-lQlz_B

Wypróbuj online. Zestaw testowy.

Nadal nie jestem do końca zadowolony z tego, jak to się potoczyło. Ale przynajmniej trudno to teraz zrozumieć bez wyjaśnienia. (Chyba sukces?)

Wyjaśnienie

• Weź A Qi B jako z.
• m… _BQOblicz następujące dla A i jego odwrotności jako d:
  • m…h-ldlz Oblicz następujące dla wszystkich kod 0 do len(A) - len(B)włącznie:
    • +BklzZdobądź parę k, k + len(B).
    • cd Rozdzielać d na te indeksy.
    • X…1z Zamień drugą (środkową) część na B.
    • Ks Połącz elementy i oszczędzaj K . B jest teraz wstawiony w pozycji kw A lub na odwrocie.
    • hc2Podziel powstały ciąg na dwie części i zachowaj pierwszy kawałek. Daje to połowę łańcucha z możliwym środkowym znakiem.
    • hc2PKUsuń ostatnią postać i wykonaj ten sam podział, zachowując pierwszy kawałek. Daje to połowę łańcucha bez możliwego środkowego znaku.
    • +… _Dodaj odwrotność krótszego elementu do dłuższego elementu. Mamy teraz palindrom.
• s Połącz wyniki dla A i jego odwrotności.
• f}zT Usuń wszystkie ciągi, które nie zawierają B.
• m Oblicz następujące dla wszystkich wynikowych ciągów d :
  • nVQd Uzyskaj nierówność parami z A. Daje to wartość True dla par, które należy zmienić.
  • sZsumuj listę. To daje dystans Hamminga.
• hS Weź minimalny wynik.

JavaScript (Firefox 30+), 152 146 bajtów

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

Podejście z użyciem siły brutalnej: wygeneruj każde możliwe nakładanie się A i B, przekształć je w palindrom, oblicz odległości Hamminga od A i weź najmniejszą z powstałych odległości.

Prawdopodobnie można by grać w golfa trochę więcej ...

Testowy fragment kodu

f=(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))
g=(A,B)=>console.log("A:",A," B:",B," f(A,B):",f(A,B))

g("thilloaoyreot", "hello")
g("benjonson", "stack")
g("neversaynever!", "odd")
g("ppcggcpp", "gg")

<input id=A value="amanaplanacanalrussia">
<input id=B value="panama">
<button onclick="g(A.value,B.value)">Run</button>