Odległość edycji Levenshteina między dwoma ciągami to minimalna możliwa liczba wstawek, usunięć lub podstawień w celu konwersji jednego słowa na inne. W takim przypadku każde wstawienie, usunięcie i zastąpienie kosztuje 1.

Na przykład odległość między rolli rollingwynosi 3, ponieważ usunięcie kosztuje 1, a my musimy usunąć 3 znaki. Odległość między tolli tallwynosi 1, ponieważ zamiana kosztuje 1.

Skradzione z oryginalnego pytania Levenshteina

Twoim zadaniem jest obliczenie różnicy edycji Levenshteina między łańcuchem wejściowym a źródłem. To jest znakowany Quine , więc oszukiwanie quines (na przykład czytanie kodu źródłowego) są nie dozwolone.

Zasady

• Dane wejściowe będą niepuste i będą się składały z ASCII, chyba że źródło zawiera inne niż ASCII, w którym to przypadku dane wejściowe mogą zawierać Unicode. Niezależnie od tego odległość Levenshteina będzie mierzona w znakach, a nie w bajtach.

• Dane wyjściowe to minimalna odległość edycji Levenshteina dla wejścia i źródła.

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.

Python 2 + sequtils , 101 bajtów

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

Python 2 , 278 258 bajtów

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

Wypróbuj online!

Jest to zwykła quine w Pythonie, zmieszana z algorytmem Levenshtein z tej odpowiedzi . Zauważ, że robi się bardzo ekstremalnie (dzięki Mr. Xcoder: P) spowolnienie.

JavaScript, 113 bajtów

To jest poprawny quine.

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'));

Pomysł skradziony z innej odpowiedzi.