_{Это был вдохновлен теперь удалены CS.SE вопрос .}

задача

Учитывая две непустые входные строки A и B, выведите наименьшее расстояние от A до палиндрома, который содержит B в качестве подстроки. Расстояние определяется количеством замен символов ( расстояние Хэмминга ).

ограничения

• Разумный вклад: существует палиндром. Это означает, что | A | ≥ | B |.
• A и B содержат только нижние символы ASCII, строчные и прописные различаются (как и все остальные символы).
• Если ваш язык не может работать с символами ASCII, вы также можете использовать целые числа (или какой-либо другой разумный тип данных) и можете ограничить диапазон до 128 элементов.
• Вы можете получить ввод из стандартного ввода, аргументов функции, аргументов командной строки и т. Д.
• Вы можете дать результат на стандартный вывод, возвращаемое значение и т. Д.
• Вам не нужно давать рабочий палиндром, достаточно наименьшего расстояния до одного.

Примеры

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

счет

Это код гольф, выигрывает самый короткий код в байтах.

Pyth, 19 байт

hSmsnVQd/#z_I#^+Qzl

демонстрация

Экстремальный подход грубой силы. Создайте все строки соответствующей длины с символами в любой строке, отфильтруйте по палиндромам и для содержания второго ввода, отобразите расстояние Хэмминга от первой строки, выведите наименьшее.

Объяснение:

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 байт

hSmsnVQdf}zTsmm+hc2KsXcd+Bklz1z_hc2PKh-lQlz_B

Попробуйте онлайн. Тестирование.

Я до сих пор не совсем доволен тем, как это получилось. Но, по крайней мере, сейчас довольно сложно понять без объяснения причин. (Успех, наверное?)

объяснение

• Взять в A как Qи B, как z.
• m… _BQВычислите следующее для A и его обратного d:
  • m... h-ldlzРассчитать следующее для всех kот 0 до len(A) - len(B)включительно:
    • +BklzПолучить пару k, k + len(B).
    • cdСплит dпо этим показателям.
    • X… 1zЗаменить вторую (среднюю) часть на B.
    • KsОбъединить кусочки и сохранить в K. B теперь вставляется в положение kв A или наоборот.
    • hc2Разделите полученную строку на две части и оставьте первую часть. Это дает половину строки с возможным средним символом.
    • hc2PKУдалите последний символ и сделайте то же разделение, сохранив первый кусок. Это дает половину строки без возможного среднего символа.
    • +... _Добавьте обратную сторону более короткой части к более длинной части. Теперь у нас есть палиндром.
• s Объединить результаты для А и его обратного.
• f}zT Удалите все строки, которые не содержат B.
• mВычислите следующее для всех полученных строк d:
  • nVQd Получите парное неравенство с A. Это дает True для пар, которые необходимо изменить.
  • sПодведите итог списка. Это дает расстояние Хемминга.
• hS Возьми минимальный результат.

JavaScript (Firefox 30+), 152 146 байт

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

Метод грубой силы: создайте каждое возможное перекрытие A и B, превратите каждое в палиндром, вычислите расстояния Хэмминга от A и возьмите наименьшее из полученных расстояний.

Вероятно, можно было бы играть в гольф немного больше ...

Тестовый фрагмент

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>