Levenshtein Your Source

Question

The Levenshtein edit distance between two strings is the minimum possible number of insertions, deletions, or substitutions to convert one word into another word. In this case, each insertion, deletion and substitution has a cost of 1.

For example, the distance between roll and rolling is 3, because deletions cost 1, and we need to delete 3 characters. The distance between toll and tall is 1, because substitutions cost 1.

Stolen from original Levenshtein question

Your task is to calculate the Levenshtein edit difference between an input string and your source. This is tagged quine, so cheating quines (for example, reading your source code) are not allowed.

Rules

• The input will be non-empty and will be composed of ASCII, unless your source contains non-ASCII, in which case the input may include Unicode. Regardless, the Levenshtein distance will be measured in characters, not bytes.

• The output is the minimum Levenshtein edit distance of the input and your source.

This is code-golf, so shortest answer, in bytes, wins.

Answer 1

Python 2 + sequtils, 101 bytes

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

Answer 2

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

Try it online!

This is just the usual quine in Python, mixed with the Levenshtein algorithm from this answer. Note that it gets quite extremely (thanks to Mr. Xcoder :P) slow.

Answer 3

Haskell, 210 bytes

main=interact$show.((x++show x)%);x@(a:c)%y@(b:d)|a==b=c%d|1>0=1+minimum[x%d,c%y,c%d];x%y=length$x++y;x="main=interact$show.((x++show x)%);x@(a:c)%y@(b:d)|a==b=c%d|1>0=1+minimum[x%d,c%y,c%d];x%y=length$x++y;x="

Try it online!

Computes the levenshtein distance modified from here. (I wrote the code there too) This is combined with a standard quine mechanism. Not much special here.

If you want to play around with it I suggest making edits towards the end of the string. The algorithm is more or less \$O(n+m^4)\$ where \$n\$ is the location of the difference between the input and the source, and \$m\$ is the length of the string after the first difference. So if you add a character to the front of this the compute time is exponential with the length of input and you won't see your result on tio.

Answer 4

Vyxal D, 10 bytes

`:qp꘍`:qp꘍

Try it Online!

Thanks to Aaron Miller for this one.

`:qp `:qp  # Standard quine
    ꘍    ꘍ # Levenshtein distance

Vyxal D, 13 bytes

`q\`:Ė\`+꘍`:Ė

Try it Online!

`q\`:Ė\`+ `:Ė # Standard eval quine (see https://codegolf.stackexchange.com/a/232956/100664)
         ꘍    # Leveshtein distance with input

10 bytes in Vyxal 2.6, whiich hasn't been released yet

Answer 5

JavaScript, 113 bytes

This is a valid 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'));

Idea stolen from other answer.

Answer 6

Python 3.8 (pre-release), 135 bytes

exec(s:="l=lambda a,b:min(l(A:=a[1:],B:=b[1:])-(a[0]==b[0]),l(A,b),l(a,B))+1if b>''<a else len(a+b);print(l('exec(s:=%r)'%s,input()))")

Try it online!

took my solution of levenstein distance (https://codegolf.stackexchange.com/a/233868/103772) and adapted it to a quine. It is very (very) slow but it works