La distance d'édition de Levenshtein entre deux chaînes est le nombre minimum possible d'insertions, de suppressions ou de substitutions pour convertir un mot en un autre mot. Dans ce cas, chaque insertion, suppression et substitution a un coût de 1.

Par exemple, la distance entre rollet rollingest 3, car les suppressions coûtent 1, et nous devons supprimer 3 caractères. La distance entre tollet tallest 1, car les substitutions coûtent 1.

Volé à la question originale de Levenshtein

Votre tâche consiste à calculer la différence d'édition Levenshtein entre une chaîne d'entrée et votre source. Il s'agit de quine étiqueté , donc les quines de triche (par exemple, la lecture de votre code source) ne sont pas autorisées.

Règles

• L'entrée sera non vide et sera composée d'ASCII, à moins que votre source ne contienne non ASCII, auquel cas l'entrée peut inclure Unicode. Quoi qu'il en soit, la distance Levenshtein sera mesurée en caractères, pas en octets.

• La sortie est la distance d'édition Levenshtein minimale de l'entrée et de votre source.

C'est le code-golf , donc la réponse la plus courte, en octets, gagne.

Python 2 + sequtils , 101 octets

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

Python 2 , 278 258 octets

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

Essayez-le en ligne!

Ceci est juste le quine habituel en Python, mélangé avec l'algorithme Levenshtein de cette réponse . Notez que cela devient assez extrêmement lent (grâce à M. Xcoder: P).

JavaScript, 113 octets

Ceci est un quine valide .

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ée volée d'une autre réponse.