A distância de edição de Levenshtein entre duas cadeias é o número mínimo possível de inserções, exclusões ou substituições para converter uma palavra em outra palavra. Nesse caso, cada inserção, exclusão e substituição tem um custo de 1.

Por exemplo, a distância entre rolle rollingé 3, porque as exclusões custam 1 e precisamos excluir 3 caracteres. A distância entre tolle tallé 1, porque as substituições custam 1.

Roubado da pergunta original de Levenshtein

Sua tarefa é calcular a diferença de edição de Levenshtein entre uma sequência de entrada e sua fonte. Isso é marcado como quine , portanto, trapacear quines (por exemplo, ler seu código-fonte) não é permitido.

Regras

• A entrada não ficará vazia e será composta de ASCII, a menos que sua fonte contenha não-ASCII; nesse caso, a entrada pode incluir Unicode. Independentemente, a distância de Levenshtein será medida em caracteres, não em bytes.

• A saída é a distância mínima de edição de Levenshtein da entrada e da sua fonte.

Isso é código-golfe , então a resposta mais curta, em bytes, vence.

Python 2 + sequtils , 101 bytes

from sequtils import*;_='from sequtils import*;_=%r;print edit(_%%_,input())';print edit(_%_,input())

Python 2 , 278 258 bytes

t=input();s,f='t=input();s,f=%r,lambda m,n:m or n if m*n<1else-~min(f(m-1,n),f(m,n-1),f(m-1,n-1)-((s%%s)[m-1]==t[n-1]));print f(len(s%%s),len(t))',lambda m,n:m or n if m*n<1else-~min(f(m-1,n),f(m,n-1),f(m-1,n-1)-((s%s)[m-1]==t[n-1]));print f(len(s%s),len(t))

Experimente online!

Esta é apenas a solução usual em Python, misturada com o algoritmo de Levenshtein desta resposta . Note-se que ele fica bastante extremamente (graças ao Sr. Xcoder: P) lento.

JavaScript, 113 bytes

Esta é uma solução válida .

f=t=>[...t].map((v,j)=>x=x.map((w,k)=>q=k--?Math.min(q,w,x[k]-(v==u[k]))+1:j+1),x=[...[,...u=`f=${f}`].keys()])|q

f=t=>[...t].map((v,j)=>x=x.map((w,k)=>q=k--?Math.min(q,w,x[k]-(v==u[k]))+1:j+1),x=[...[,...u=`f=${f}`].keys()])|q

console.log(f('f=t=>[...t].map((v,j)=>x=x.map((w,k)=>q=k--?Math.min(q,w,x[k]-(v==u[k]))+1:j+1),x=[...[,...u=`f=${f}`].keys()])|q'));
console.log(f('%'));
console.log(f('12345'));

Idéia roubada de outra resposta.